Erik D. Demaine

research

∙ 09/18/2023

2-Colorable Perfect Matching is NP-complete in 2-Connected 3-Regular Planar Graphs

The 2-colorable perfect matching problem asks whether a graph can be col...

0 Erik D. Demaine, et al. ∙

research

∙ 08/29/2023

When Can You Tile an Integer Rectangle with Integer Squares?

This paper characterizes when an m × n rectangle, where m and n are inte...

0 MIT CompGeom Group, et al. ∙

research

∙ 06/01/2023

Complexity of Motion Planning of Arbitrarily Many Robots: Gadgets, Petri Nets, and Counter Machines

We extend the motion-planning-through-gadgets framework to several new s...

0 Joshua Ani, et al. ∙

research

∙ 06/01/2023

Complexity of Simple Folding of Mixed Orthogonal Crease Patterns

Continuing results from JCDCGGG 2016 and 2017, we solve several new case...

0 Hugo Akitaya, et al. ∙

research

∙ 04/03/2023

Every Author as First Author

We propose a new standard for writing author names on papers and in bibl...

0 Erik D. Demaine, et al. ∙

research

∙ 03/27/2023

Complexity of Reconfiguration in Surface Chemical Reaction Networks

We analyze the computational complexity of basic reconfiguration problem...

0 Robert M. Alaniz, et al. ∙

research

∙ 02/02/2023

Complexity of Solo Chess with Unlimited Moves

We analyze Solo Chess puzzles, where the input is an n × n board contain...

0 Josh Brunner, et al. ∙

research

∙ 02/02/2023

This Game Is Not Going To Analyze Itself

We analyze the puzzle video game This Game Is Not Going To Load Itself, ...

0 Aviv Adler, et al. ∙

research

∙ 12/23/2022

Computational Complexity of Flattening Fixed-Angle Orthogonal Chains

Planar/flat configurations of fixed-angle chains and trees are well stud...

0 Erik D. Demaine, et al. ∙

research

∙ 11/26/2022

Lower Bounds on Retroactive Data Structures

We prove essentially optimal fine-grained lower bounds on the gap betwee...

0 Lily Chung, et al. ∙

research

∙ 11/21/2022

Celeste is PSPACE-hard

We investigate the complexity of the platform video game Celeste. We pro...

0 Lily Chung, et al. ∙

research

∙ 07/14/2022

PSPACE-Completeness of Reversible Deterministic Systems

We prove PSPACE-completeness of several reversible, fully deterministic ...

0 Erik D. Demaine, et al. ∙

research

∙ 06/08/2022

Reconfiguration of Non-crossing Spanning Trees

For a set P of n points in the plane in general position, a non-crossing...

0 Oswin Aichholzer, et al. ∙

research

∙ 04/07/2022

Flat Folding an Unassigned Single-Vertex Complex (Combinatorially Embedded Planar Graph with Specified Edge Lengths) without Flat Angles

A foundational result in origami mathematics is Kawasaki and Justin's si...

0 Lily Chung, et al. ∙

research

∙ 03/31/2022

The Legend of Zelda: The Complexity of Mechanics

We analyze some of the many game mechanics available to Link in the clas...

0 Jeffrey Bosboom, et al. ∙

research

∙ 02/02/2022

Orthogonal Fold Cut

We characterize the shapes that can be produced by "orthogonal fold ...

0 Joshua Ani, et al. ∙

research

∙ 01/28/2022

Unfolding Orthotubes with a Dual Hamiltonian Path

An orthotube consists of orthogonal boxes (e.g., unit cubes) glued face-...

0 Erik D. Demaine, et al. ∙

research

∙ 12/15/2021

ZHED is NP-complete

We prove that the 2017 puzzle game ZHED is NP-complete, even with just 1...

0 Sagnik Saha, et al. ∙

research

∙ 11/14/2021

Area-Optimal Simple Polygonalizations: The CG Challenge 2019

We give an overview of theoretical and practical aspects of finding a si...

0 Erik D. Demaine, et al. ∙

research

∙ 10/27/2021

An Efficient Reversible Algorithm for Linear Regression

This paper presents an efficient reversible algorithm for linear regress...

0 Erik D. Demaine, et al. ∙

research

∙ 09/30/2021

Rectangular Spiral Galaxies are Still Hard

Spiral Galaxies is a pencil-and-paper puzzle played on a grid of unit sq...

0 Erik D. Demaine, et al. ∙

research

∙ 09/09/2021

Any Regular Polyhedron Can Transform to Another by O(1) Refoldings

We show that several classes of polyhedra are joined by a sequence of O(...

0 Erik D. Demaine, et al. ∙

research

∙ 06/29/2021

Yin-Yang Puzzles are NP-complete

We prove NP-completeness of Yin-Yang / Shiromaru-Kuromaru pencil-and-pap...

0 Erik D. Demaine, et al. ∙

research

∙ 05/22/2021

Continuous Flattening of All Polyhedral Manifolds using Countably Infinite Creases

We prove that any finite polyhedral manifold in 3D can be continuously f...

0 Zachary Abel, et al. ∙

research

∙ 05/18/2021

Snipperclips: Cutting Tools into Desired Polygons using Themselves

We study Snipperclips, a computer puzzle game whose objective is to crea...

0 Zachary Abel, et al. ∙

research

∙ 03/11/2021

Hardness of Token Swapping on Trees

Given a graph where every vertex has exactly one labeled token, how can ...

0 Oswin Aichholzer, et al. ∙

research

∙ 01/16/2021

Strings-and-Coins and Nimstring are PSPACE-complete

We prove that Strings-and-Coins – the combinatorial two-player game gene...

0 Erik D. Demaine, et al. ∙

research

∙ 12/14/2020

Characterizing Universal Reconfigurability of Modular Pivoting Robots

We give both efficient algorithms and hardness results for reconfiguring...

0 Hugo A. Akitaya, et al. ∙

research

∙ 11/23/2020

Arithmetic Expression Construction

When can n given numbers be combined using arithmetic operators from a g...

0 Leo Alcock, et al. ∙

research

∙ 10/19/2020

Complexity of Retrograde and Helpmate Chess Problems: Even Cooperative Chess is Hard

We prove PSPACE-completeness of two classic types of Chess problems when...

0 Josh Brunner, et al. ∙

research

∙ 09/29/2020

Tetris is NP-hard even with O(1) rows or columns

We prove that the classic falling-block video game Tetris (both survival...

0 Sualeh Asif, et al. ∙

research

∙ 08/03/2020

Finding Closed Quasigeodesics on Convex Polyhedra

A closed quasigeodesic is a closed loop on the surface of a polyhedron w...

0 Erik D. Demaine, et al. ∙

research

∙ 07/31/2020

New Results in Sona Drawing: Hardness and TSP Separation

Given a set of point sites, a sona drawing is a single closed curve, dis...

0 Man-Kwun Chiu, et al. ∙

research

∙ 07/28/2020

Acutely Triangulated, Stacked, and Very Ununfoldable Polyhedra

We present new examples of topologically convex edge-ununfoldable polyhe...

0 Erik D. Demaine, et al. ∙

research

∙ 07/17/2020

Escaping a Polygon

Suppose an "escaping" player moves continuously at maximum speed 1 in th...

0 Zachary Abel, et al. ∙

research

∙ 06/08/2020

PSPACE-completeness of Pulling Blocks to Reach a Goal

We prove PSPACE-completeness of all but one problem in a large space of ...

0 Joshua Ani, et al. ∙

research

∙ 06/01/2020

Walking through Doors is Hard, even without Staircases: Proving PSPACE-hardness via Planar Assemblies of Door Gadgets

A door gadget has two states and three tunnels that can be traversed by ...

0 Joshua Ani, et al. ∙

research

∙ 06/01/2020

Negative Instance for the Edge Patrolling Beacon Problem

Can an infinite-strength magnetic beacon always “catch” an iron ball, wh...

0 Zachary Abel, et al. ∙

research

∙ 05/07/2020

Trains, Games, and Complexity: 0/1/2-Player Motion Planning through Input/Output Gadgets

We analyze the computational complexity of motion planning through local...

0 Joshua Ani, et al. ∙

research

∙ 04/08/2020

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 ...

0 Erik D. Demaine, et al. ∙

research

∙ 03/22/2020

1 x 1 Rush Hour with Fixed Blocks is PSPACE-complete

Consider n^2-1 unit-square blocks in an n × n square board, where each b...

0 Josh Brunner, et al. ∙

research

∙ 03/18/2020

Tatamibari is NP-complete

In the Nikoli pencil-and-paper game Tatamibari, a puzzle consists of an ...

0 Aviv Adler, et al. ∙

research

∙ 02/10/2020

Edge Matching with Inequalities, Triangles, Unknown Shape, and Two Players

We analyze the computational complexity of several new variants of edge-...

0 Jeffrey Bosboom, et al. ∙

research

∙ 10/22/2019

Folding Polyominoes with Holes into a Cube

When can a polyomino piece of paper be folded into a unit cube? Prior wo...

0 Oswin Aichholzer, et al. ∙

research

∙ 08/21/2019

Universal Reconfiguration of Facet-Connected Modular Robots by Pivots: The O(1) Musketeers

We present the first universal reconfiguration algorithm for transformin...

0 Hugo A. Akitaya, et al. ∙

research

∙ 08/21/2019

Existence and hardness of conveyor belts

An open problem of Manuel Abellanas asks whether every set of disjoint c...

0 Molly Baird, et al. ∙

research

∙ 06/30/2019

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...

0 Pei-Chuan Chen, et al. ∙

research

∙ 05/01/2019

Reconfiguring Undirected Paths

We consider problems in which a simple path of fixed length, in an undir...

0 Erik D. Demaine, et al. ∙

research

∙ 03/08/2019

Belga B-trees

We revisit self-adjusting external memory tree data structures, which co...

0 Erik D. Demaine, et al. ∙

research

∙ 01/24/2019

Infinite All-Layers Simple Foldability

We study the problem of deciding whether a crease pattern can be folded ...

0 Hugo A. Akitaya, et al. ∙

Erik D. Demaine

Featured Co-authors