About

Erik Demaine is a professor associated with the Department of Electrical Engineering and Computer Science at MIT. His research focuses on the theory and practice of algorithms, encompassing idealized mathematical procedures and the computer systems deployed by major tech companies to handle billions of user requests per day. His work involves leveraging computational, theoretical, and experimental tools to develop groundbreaking sensors, energy transducers, new physical substrates for computation, and systems that address shared human challenges. He is involved in the exploration of various research areas within electrical engineering and computer science, including algorithms, systems, and the intersection of artificial intelligence with decision-making. His contributions are integral to advancing understanding in these fields, contributing to the development of innovative computational techniques and systems.

Research topics

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

Selected publications

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

  Theoretical Computer Science · 2 citations

  • 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

• Tetris is Hard with Just One Piece Type

  arXiv (Cornell University) · 2026-03-10

  articleOpen access

  We analyze the computational complexity of Tetris clearing (determining whether the player can clear an initial board using a given sequence of pieces) and survival (determining whether the player can avoid losing before placing all the given pieces in an initial board) when restricted to a single polyomino piece type. We prove, for any tetromino piece type $P$ except for O, the NP-hardness of Tetris clearing and survival under the standard Super Rotation System (SRS), even when the input sequence consists of only a specified number of $P$ pieces. These surprising results disprove a 23-year-old conjecture on the computational complexity of Tetris with only I pieces (although our result is only for a specific rotation system). As a corollary, we prove the NP-hardness of Tetris clearing when the sequence of pieces has to be able to be generated from a $7k$-bag randomizer for any positive integer $k\geq 1$. On the positive side, we give polynomial-time algorithms for Tetris clearing and survival when the input sequence consists of only dominoes, assuming a particular rotation model, solving a version of a 9-year-old open problem. Along the way, we give polynomial-time algorithms for Tetris clearing and survival with $1\times k$ pieces (for any fixed $k$), provided the top $k-1$ rows are initially empty, showing that our I NP-hardness result needs to have filled cells in the top three rows.

  PublisherOA PDF

• Tetris Is Hard with Just One Piece Type

  Leibniz-Zentrum für Informatik (Schloss Dagstuhl) · 2026-01-01

  articleOpen access

  We analyze the computational complexity of Tetris clearing (determining whether the player can clear an initial board using a given sequence of pieces) and survival (determining whether the player can avoid losing before placing all the given pieces in an initial board) when restricted to a single polyomino piece type. We prove, for any tetromino piece type P except for O, the NP-hardness of Tetris clearing and survival under the standard Super Rotation System (SRS), even when the input sequence consists of only a specified number of P pieces. These surprising results disprove a 23-year-old conjecture on the computational complexity of Tetris with only I pieces (although our result is only for a specific rotation system). As a corollary, we prove the NP-hardness of Tetris clearing when the sequence of pieces has to be able to be generated from a 7k-bag randomizer for any positive integer k ≥ 1. On the positive side, we give polynomial-time algorithms for Tetris clearing and survival when the input sequence consists of only dominoes, assuming a particular rotation model, solving a version of a 9-year-old open problem. Along the way, we give polynomial-time algorithms for Tetris clearing and survival with 1 × k pieces (for any fixed k), provided the top k-1 rows are initially empty, showing that our I NP-hardness result needs to have filled cells in the top three rows.

  PublisherDOI

• A Bookworm Climbs up the Polynomial Hierarchy: Meta-Restoration Complexity in Arithmetic Puzzles

  Open MIND · 2026-01-01

  articleOpen access

  In arithmetic puzzles, a partially specified arithmetic expression must be completed to make the computation valid. Arithmetical restoration puzzles require filling in missing digits, while cryptarithms involve assigning digits to letters. The Japanese term mushikui-zan ("bookwormed arithmetic") commonly refers to arithmetical restorations, where we imagine the missing digits have been eaten by a bookworm. Puzzle creator Yousuke Ikeda proposed a new type of puzzle in which a previously designed bookwormed arithmetic with multiplication - known to have a unique solution - has itself been "bookwormed", that is, partially erased. The goal is to restore the specified blanks so that the resulting bookwormed puzzle again has a unique solution. We further generalize this framework: for each k ≥ 2, we define level-k puzzles as those in which type-k blanks must be filled to make the resulting level-(k{-}1) puzzle uniquely solvable. We study the level-k versions of the Boolean satisfiability problem, and show that they form a hierarchy of Σ^P_k-complete decision problems, tightly matching the levels of the polynomial hierarchy. As applications, we show that the level-k arithmetical restoration problem with multiplication is Σ^P_k-complete, as is the level-k cryptarithm problem. On the positive side, we show that level-2 arithmetical restoration puzzles with addition are solvable in polynomial time.

  PublisherOA PDFDOI

• Tetris is Hard with Just One Piece Type

  Open MIND · 2026-03-10

  preprintOpen access

  We analyze the computational complexity of Tetris clearing (determining whether the player can clear an initial board using a given sequence of pieces) and survival (determining whether the player can avoid losing before placing all the given pieces in an initial board) when restricted to a single polyomino piece type. We prove, for any tetromino piece type $P$ except for O, the NP-hardness of Tetris clearing and survival under the standard Super Rotation System (SRS), even when the input sequence consists of only a specified number of $P$ pieces. These surprising results disprove a 23-year-old conjecture on the computational complexity of Tetris with only I pieces (although our result is only for a specific rotation system). As a corollary, we prove the NP-hardness of Tetris clearing when the sequence of pieces has to be able to be generated from a $7k$-bag randomizer for any positive integer $k\geq 1$. On the positive side, we give polynomial-time algorithms for Tetris clearing and survival when the input sequence consists of only dominoes, assuming a particular rotation model, solving a version of a 9-year-old open problem. Along the way, we give polynomial-time algorithms for Tetris clearing and survival with $1\times k$ pieces (for any fixed $k$), provided the top $k-1$ rows are initially empty, showing that our I NP-hardness result needs to have filled cells in the top three rows.

  PublisherDOI

• Analysis of Huffman’s Hexagonal Column with Cusps

  Lecture notes in mechanical engineering · 2026-01-01

  book-chapter
  PublisherDOI

• Computing Flat-Folded States

  Lecture notes in mechanical engineering · 2026-01-01

  book-chapter
  PublisherDOI

• A Novel Reduction from #SAT to #2SAT Based on Symmetry: <i>Simply Drop the Large Clauses</i>

  Society for Industrial and Applied Mathematics eBooks · 2026-01-01

  book-chapter

  The counting problem #2sat is complete for #P under Turing (many-call) reductions, which dates back to the seminal work by Valiant from 1979. Arguably, this reduction is the opposite from being simple as it is a sophisticated chain of transformation from #sat, via several variations of the problem of computing the permanent, to the task of counting matchings in graphs, and then finally to #2sat. In contrast, we give a simple reduction that makes only two calls instead of polynomially many calls. Our reduction is based on the inclusion-exclusion principle from #sat to weighted #2sat with weights in \(\{-1, 1\}\). From there, we map the computation of such weighted model counting problems to the subtraction of two unweighted model counting problems using parity constraints. We can encode these parity constraints using almost solely binary clauses and very few clauses of size four. Then, thanks to the subtraction and the symmetry between the two formulas, these clauses of size four can simply be omitted without changing the overall result of the computation — thus leading to a surprisingly simple reduction from #sat to two calls of #2sat.

  PublisherDOI

• Folding a Strip of Paper into Shapes with Specified Thickness

  Lecture notes in mechanical engineering · 2026-01-01

  book-chapter
  PublisherDOI

• Algorithmic Transitions Between Parallel Pleats

  Lecture notes in mechanical engineering · 2026-01-01

  book-chapterSenior author
  PublisherDOI

Recent grants

• AF: Medium: Collaborative Research: General Frameworks for Approximation and Fixed-Parameter Algorithms

  NSF · $400k · 2012–2018

• BIGDATA: Collaborative Research: F: Making Big Data Accessible on Personal Devices: Big Network Algorithms, External Memory, and Data Streams

  NSF · $500k · 2015–2020

Frequent coauthors

• Martin L. Demaine

  292 shared

• Stefan Langerman

  112 shared

• Jayson Lynch

  104 shared

• Joseph O’Rourke

  Smith College

  103 shared

• Daniela Tulone

  Joint Research Centre

  83 shared

• Adam Hesterberg

  79 shared

• Ryuhei Uehara

  77 shared

• Sándor P. Fekete

  Technische Universität Braunschweig

  71 shared