Erik D. Demaine

Losing at Checkers is Hard

2018 · arXiv (Cornell University)

We prove computational intractability of variants of checkers: (1) deciding whether there is a move that forces the other player to win in one move is NP-complete; (2) checkers where players must always be able …

Unfolding Genus-2 Orthogonal Polyhedra with Linear Refinement

2016 · arXiv (Cornell University)

We show that every orthogonal polyhedron of genus at most 2 can be unfolded without overlap while using only a linear number of orthogonal cuts (parallel to the polyhedron edges). This is the first result …

Walking Through Doors Is Hard, Even Without Staircases: Proving PSPACE-Hardness via Planar Assemblies of Door Gadgets

2020 · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics)

A door gadget has two states and three tunnels that can be traversed by an agent (player, robot, etc.): the "open" and "close" tunnel sets the gadget’s state to open and closed, respectively, while the …

Tetris is NP-hard even with <i>O</i>(1) Rows or Columns

2020 · Journal of Information Processing

We prove that the classic falling-block video game Tetris (both survival and board clearing) remains NP-complete even when restricted to 8 columns, or to 4 rows, settling open problems posed over 15 years ago. Our …