About

Zachary Abel is a Principal Lecturer in the Department of Electrical Engineering and Computer Science at MIT. His research and teaching focus on computer science, with particular emphasis on artificial intelligence and decision-making. As a faculty member, he contributes to the development of systems that interact with the external environment through perception, communication, and action, while also learning, making decisions, and adapting to changing environments. His work is integral to advancing techniques for the analysis and synthesis of intelligent systems, combining theoretical and practical approaches to address complex challenges in AI and related fields.

Research topics

• Computer Science
• Mathematics
• Combinatorics
• Geometry
• Physics
• Discrete mathematics

Selected publications

• Who witnesses The Witness? Finding witnesses in The Witness is hard and sometimes impossible

  Theoretical Computer Science · 2 citations

  1st authorCorresponding
  • Computer Science
  • Combinatorics
  • Mathematics

  We analyze the computational complexity of the many types of pencil-and-paper-style puzzles featured in the 2016 puzzle video game The Witness. In all puzzles, the goal is to draw a simple path in a rectangular grid graph from a start vertex to a destination vertex. The different puzzle types place different constraints on the path: preventing some edges from being visited (broken edges); forcing some edges or vertices to be visited (hexagons); forcing some cells to have certain numbers of incident path edges (triangles); or forcing the regions formed by the path to be partially monochromatic (squares), have exactly two special cells (stars), or be singly covered by given shapes (polyominoes) and/or negatively counting shapes (antipolyominoes). We show that any one of these clue types (except the first) is enough to make path finding NP-complete ("witnesses exist but are hard to find"), even for rectangular boards. Furthermore, we show that a final clue type (antibody), which necessarily "cancels" the effect of another clue in the same region, makes path finding Σ2-complete ("witnesses do not exist"), even with a single antibody (combined with many anti/polyominoes), and the problem gets no harder with many antibodies. On the positive side, we give a polynomial-time algorithm for monomino clues, by reducing to hexagon clues on the boundary of the puzzle, even in the presence of broken edges, and solving "subset Hamiltonian path" for terminals on the boundary of an embedded planar graph in polynomial time.

  DOI

• Planar Graph Orientation Frameworks, Applied to KPlumber and Polyomino Tiling

  Open MIND · 2026-03-03

  preprint

  Given a graph, when can we orient the edges to satisfy local constraints at the vertices, where each vertex specifies which local orientations of its incident edges are allowed? This family of graph orientation problems is a special kind of SAT problem, where each variable (edge orientation) appears in exactly two clauses (vertex constraints) -- once positively and once negatively. We analyze the complexity of many natural vertex types (patterns of allowed vertex neighborhoods), most notably all sets of symmetric vertex types which depend on only the number of incoming edges. In many scenarios, including Planar and Non-Planar Symmetric Graph Orientation with constants, we give a full dichotomy characterizing P vs. NP-complete problem classes. We apply our results to obtain new polynomial-time algorithms, resolving a 20-year-old open problem about KPlumber; to simplify existing NP-hardness proofs for tiling with trominoes; and to prove new NP-completeness results for tiling with tetrominoes.

  DOI

• Planar Graph Orientation Frameworks, Applied to KPlumber and Polyomino Tiling

  arXiv (Cornell University) · 2026-03-03

  articleOpen access

  Given a graph, when can we orient the edges to satisfy local constraints at the vertices, where each vertex specifies which local orientations of its incident edges are allowed? This family of graph orientation problems is a special kind of SAT problem, where each variable (edge orientation) appears in exactly two clauses (vertex constraints) -- once positively and once negatively. We analyze the complexity of many natural vertex types (patterns of allowed vertex neighborhoods), most notably all sets of symmetric vertex types which depend on only the number of incoming edges. In many scenarios, including Planar and Non-Planar Symmetric Graph Orientation with constants, we give a full dichotomy characterizing P vs. NP-complete problem classes. We apply our results to obtain new polynomial-time algorithms, resolving a 20-year-old open problem about KPlumber; to simplify existing NP-hardness proofs for tiling with trominoes; and to prove new NP-completeness results for tiling with tetrominoes.

  PublisherOA PDF

• Who needs crossings?: Noncrossing linkages are universal, and deciding (global) rigidity is hard

  Journal of Computational Geometry (Carleton University) · 2025-05-29

  articleOpen access1st authorCorresponding

  We exactly settle the complexity of graph realization, graph rigidity, and graph global rigidity as applied to three types of graphs: "globally noncrossing" graphs, which avoid crossings in all of their configurations; matchstick graphs, with unit-length edges and where only noncrossing configurations are considered; and unrestricted graphs (crossings allowed) with unit edge lengths (or in the global rigidity case, edge lengths in $\{1,2\}$). We show that all nine of these questions are complete for the class $\exists\mathbb R$, defined by the Existential Theory of the Reals, or its complement $\forall\mathbb R$; in particular, each problem is (co)NP-hard. One of these nine results—that realization of unit-distance graphs is $\exists\mathbb R$-complete—was shown previously by Schaefer (2013), but the other eight are new. We strengthen several prior results. Matchstick graph realization was known to be NP-hard (Eades & Wormald 1990, or Cabello et al. 2007), but its membership in NP remained open; we show it is complete for the (possibly) larger class $\exists\mathbb R$. Global rigidity of graphs with edge lengths in $\{1,2\}$ was known to be coNP-hard (Saxe 1979); we show it is $\forall\mathbb R$-complete. The majority of the paper is devoted to proving an analog of Kempe's Universality Theorem---informally, "there is a linkage to sign your name"—for globally noncrossing linkages. In particular, we show that any polynomial curve $\phi(x,y)=0$ can be traced by a noncrossing linkage, settling an open problem from 2004. More generally, we show that the regions in the plane that may be traced by a noncrossing linkage are precisely the compact semialgebraic regions (plus the trivial case of the entire plane). Thus, no drawing power is lost by restricting to noncrossing linkages. We prove analogous results for matchstick linkages and unit-distance linkages as well.

  PublisherDOI

• Undecidability of Tiling with a Tromino

  ArXiv.org · 2025-09-09

  preprintOpen access

  Given a periodic placement of copies of a tromino (either L or I), we prove co-RE-completeness (and hence undecidability) of deciding whether it can be completed to a plane tiling. By contrast, the problem becomes decidable if the initial placement is finite, or if the tile is a domino instead of a tromino (in any dimension). As a consequence, tiling a given periodic subset of the plane with a given tromino (L or I) is co-RE-complete. We also prove co-RE-completeness of tiling the entire plane with two polyominoes (one of which is disconnected and the other of which has constant size), and of tiling 3D space with two connected polycubes (one of which has constant size). If we restrict to tiling by translation only (no rotation), then we obtain co-RE-completeness with one more tile: two trominoes for a periodic subset of 2D, three polyominoes for the 2D plane, and three connected polycubes for 3D space. Along the way, we prove several new complexity and algorithmic results about periodic (infinite) graphs. Notably, we prove that Periodic Planar (1-in-)3SAT-3, 3DM, and Graph Orientation are co-RE-complete in 2D and PSPACE-complete in 1D; we extend basic results in graph drawing to 2D periodic graphs; and we give a polynomial-time algorithm for perfect matching in bipartite periodic graphs.

  PublisherOA PDFDOI

• A universal in-place reconfiguration algorithm for sliding cube-shaped robots in a quadratic number of moves

  Journal of Computational Geometry (Carleton University) · 2025-12-16

  articleOpen access1st authorCorresponding

  In the modular robot reconfiguration problem, we are given $n$ cube-shaped modules (or robots) as well as two configurations, i.e., placements of the $n$ modules so that their union is face-connected. The goal is to find a sequence of moves that reconfigures the modules from one configuration to the other using "sliding moves", in which a module slides over the face or edge of a neighboring module, maintaining connectivity of the configuration at all times. For many years it has been known that certain module configurations in this model require at least $\Omega(n^2)$ moves to reconfigure between them, and works for any dimension $d\ge 3$. In this paper, we introduce the first universal reconfiguration algorithm—i.e., we show that any $n$-module configuration can reconfigure itself into any specified $n$-module configuration using just sliding moves. Our algorithm achieves reconfiguration in $O(n^2)$ moves, making it asymptotically tight. We also present a variation that reconfigures in-place, it ensures that throughout the reconfiguration process, all modules, except for one, will be contained in the union of the bounding boxes of the start and end configuration.

  PublisherOA PDFDOI

• When Can You Tile an Integer Rectangle with Integer Squares?

  arXiv (Cornell University) · 2023-08-29

  preprintOpen access

  This paper characterizes when an $m \times n$ rectangle, where $m$ and $n$ are integers, can be tiled (exactly packed) by squares where each has an integer side length of at least 2. In particular, we prove that tiling is always possible when both $m$ and $n$ are sufficiently large (at least 10). When one dimension $m$ is small, the behavior is eventually periodic in $n$ with period 1, 2, or 3. When both dimensions $m,n$ are small, the behavior is determined computationally by an exhaustive search.

  PublisherOA PDFDOI

• Snipperclips: Cutting tools into desired polygons using themselves

  Computational Geometry · 2021-05-14

  articleOpen access1st author
  PublisherOA PDFDOI

• Negative Instance for the Edge Patrolling Beacon Problem

  Lecture notes in computer science · 2021-01-01 · 1 citations

  preprintOpen access1st authorCorresponding
  PublisherOA PDFDOI

• Continuous flattening of all polyhedral manifolds using countably infinite creases

  Computational Geometry · 2021 · 5 citations

  1st authorCorresponding
  • Computer Science
  • Combinatorics
  • Mathematics
  PublisherOA PDFDOI

Frequent coauthors

• Erik D. Demaine

  56 shared

• Martin L. Demaine

  36 shared

• Adam Hesterberg

  26 shared

• Jayson Lynch

  20 shared

• Scott Duke Kominers

  17 shared

• Ryuhei Uehara

  14 shared

• Aman Gour

  11 shared

• Sándor P. Fekete

  Technische Universität Braunschweig

  11 shared

Labs

• EECS Communication LabPI

Education

• Ph.D., Electrical Engineering and Computer Science

  Massachusetts Institute of Technology

  2009

• M.S., Electrical Engineering and Computer Science

  Massachusetts Institute of Technology

  2005

• B.S., Electrical Engineering and Computer Science

  Massachusetts Institute of Technology

  2001