
YinYang Puzzles are NPcomplete
We prove NPcompleteness of YinYang / ShiromaruKuromaru pencilandpap...
read it

Continuous Flattening of All Polyhedral Manifolds using Countably Infinite Creases
We prove that any finite polyhedral manifold in 3D can be continuously f...
read it

Snipperclips: Cutting Tools into Desired Polygons using Themselves
We study Snipperclips, a computer puzzle game whose objective is to crea...
read it

Hardness of Token Swapping on Trees
Given a graph where every vertex has exactly one labeled token, how can ...
read it

StringsandCoins and Nimstring are PSPACEcomplete
We prove that StringsandCoins – the combinatorial twoplayer game gene...
read it

Characterizing Universal Reconfigurability of Modular Pivoting Robots
We give both efficient algorithms and hardness results for reconfiguring...
read it

Arithmetic Expression Construction
When can n given numbers be combined using arithmetic operators from a g...
read it

Complexity of Retrograde and Helpmate Chess Problems: Even Cooperative Chess is Hard
We prove PSPACEcompleteness of two classic types of Chess problems when...
read it

Tetris is NPhard even with O(1) rows or columns
We prove that the classic fallingblock video game Tetris (both survival...
read it

Finding Closed Quasigeodesics on Convex Polyhedra
A closed quasigeodesic is a closed loop on the surface of a polyhedron w...
read it

New Results in Sona Drawing: Hardness and TSP Separation
Given a set of point sites, a sona drawing is a single closed curve, dis...
read it

Acutely Triangulated, Stacked, and Very Ununfoldable Polyhedra
We present new examples of topologically convex edgeununfoldable polyhe...
read it

Escaping a Polygon
Suppose an "escaping" player moves continuously at maximum speed 1 in th...
read it

PSPACEcompleteness of Pulling Blocks to Reach a Goal
We prove PSPACEcompleteness of all but one problem in a large space of ...
read it

Walking through Doors is Hard, even without Staircases: Proving PSPACEhardness via Planar Assemblies of Door Gadgets
A door gadget has two states and three tunnels that can be traversed by ...
read it

Negative Instance for the Edge Patrolling Beacon Problem
Can an infinitestrength magnetic beacon always “catch” an iron ball, wh...
read it

Trains, Games, and Complexity: 0/1/2Player Motion Planning through Input/Output Gadgets
We analyze the computational complexity of motion planning through local...
read it

Computing Convex Partitions for Point Sets in the Plane: The CG:SHOP Challenge 2020
We give an overview of the 2020 Computational Geometry Challenge, which ...
read it

1 x 1 Rush Hour with Fixed Blocks is PSPACEcomplete
Consider n^21 unitsquare blocks in an n × n square board, where each b...
read it

Tatamibari is NPcomplete
In the Nikoli pencilandpaper game Tatamibari, a puzzle consists of an ...
read it

Edge Matching with Inequalities, Triangles, Unknown Shape, and Two Players
We analyze the computational complexity of several new variants of edge...
read it

Folding Polyominoes with Holes into a Cube
When can a polyomino piece of paper be folded into a unit cube? Prior wo...
read it

Universal Reconfiguration of FacetConnected Modular Robots by Pivots: The O(1) Musketeers
We present the first universal reconfiguration algorithm for transformin...
read it

Existence and hardness of conveyor belts
An open problem of Manuel Abellanas asks whether every set of disjoint c...
read it

Waiting is not easy but worth it: the online TSP on the line revisited
We consider the online traveling salesman problem on the real line (OLTS...
read it

Reconfiguring Undirected Paths
We consider problems in which a simple path of fixed length, in an undir...
read it

Belga Btrees
We revisit selfadjusting external memory tree data structures, which co...
read it

Infinite AllLayers Simple Foldability
We study the problem of deciding whether a crease pattern can be folded ...
read it

A General Theory of Motion Planning Complexity: Characterizing Which Gadgets Make Games Hard
We build a general theory for characterizing the computational complexit...
read it

Conic Crease Patterns with Reflecting Rule Lines
We characterize when two conic curved creases are compatible with each o...
read it

Rigid Foldability is NPHard
In this paper, we show that deciding rigid foldability of a given crease...
read it

Cookie Clicker
Cookie Clicker is a popular online incremental game where the goal of th...
read it

Know When to Fold 'Em: SelfAssembly of Shapes by Folding in Oritatami
An oritatami system (OS) is a theoretical model of selfassembly via co...
read it

Losing at Checkers is Hard
We prove computational intractability of variants of checkers: (1) decid...
read it

Computational Complexity of Motion Planning of a Robot through Simple Gadgets
We initiate a general theory for analyzing the complexity of motion plan...
read it

Structural Rounding: Approximation Algorithms for Graphs Near an Algorithmically Tractable Class
We develop a new framework for generalizing approximation algorithms fro...
read it

Reconfiguration of Satisfying Assignments and Subset Sums: Easy to Find, Hard to Connect
We consider the computational complexity of reconfiguration problems, in...
read it

Who witnesses The Witness? Finding witnesses in The Witness is hard and sometimes impossible
We analyze the computational complexity of the many types of penciland...
read it

Nearly Optimal Separation Between Partially And Fully Retroactive Data Structures
Since the introduction of retroactive data structures at SODA 2004, a ma...
read it

Computational Complexity of Generalized Push Fight
We analyze the computational complexity of optimally playing the twopla...
read it

Path Puzzles: Discrete Tomography with a Path Constraint is Hard
We prove that path puzzles with complete row and column informationor ...
read it

Polyhedral Characterization of Reversible Hinged Dissections
We prove that two polygons A and B have a reversible hinged dissection (...
read it

Coordinated Motion Planning: Reconfiguring a Swarm of Labeled Robots with Bounded Stretch
We present a number of breakthroughs for coordinated motion planning, in...
read it

Folding Polyominoes into (Poly)Cubes
We study the problem of folding a polyomino P into a polycube Q, allowin...
read it

Particle Computation: Complexity, Algorithms, and Logic
We investigate algorithmic control of a large swarm of mobile particles ...
read it

FineGrained I/O Complexity via Reductions: New lower bounds, faster algorithms, and a time hierarchy
This paper initiates the study of I/O algorithms (minimizing cache misse...
read it

PushPull Block Puzzles are Hard
This paper proves that pushpull block puzzles in 3D are PSPACEcomplete...
read it

Upward Partitioned Book Embeddings
We analyze a directed variation of the book embedding problem when the p...
read it

Inapproximability of the Standard Pebble Game and Hard to Pebble Graphs
Pebble games are singleplayer games on DAGs involving placing and movin...
read it

A simple proof that the (n^21)puzzle is hard
The 15 puzzle is a classic reconfiguration puzzle with fifteen uniquely ...
read it
Erik D. Demaine
is this you? claim profile
Professor of Electrical Engineering and Computer Science, Massachusetts Institute of Technology