E. Demaine

Most-cited papers

Unlocking history through automated virtual unfolding of sealed documents imaged by X-ray microtomography
Jana L. Dambrogio, Amanda Ghassaei, Daniel Starza Smith, Holly Jackson +7 more
2021Nature Communications36 citations Open access
Semantic Scholar
Hardness of Token Swapping on Trees
O. Aichholzer, E. Demaine, Matias Korman, J. Lynch +5 more
2021Embedded Systems and Applications22 citations
Semantic Scholar
Walking through Doors is Hard, even without Staircases: Proving PSPACE-hardness via Planar Assemblies of Door Gadgets
Joshua Ani, Jeffrey Bosboom, E. Demaine, Jenny Diomidova +2 more
2020Fun with Algorithms22 citations
Semantic Scholar
1 x 1 Rush Hour with Fixed Blocks is PSPACE-complete
Josh Brunner, Lily Chung, E. Demaine, D. Hendrickson +3 more
2020Fun with Algorithms18 citations
Semantic Scholar
Multidimensional Scaling: Approximation and Complexity
E. Demaine, Adam Hesterberg, Frederic Koehler, J. Lynch +1 more
2021International Conference on Machine Learning17 citations
Semantic Scholar
Area-Optimal Simple Polygonalizations: The CG Challenge 2019
E. Demaine, S. Fekete, Phillip Keldenich, Dominik Krupke +1 more
2021ACM Journal of Experimental Algorithmics16 citations Open access
Semantic Scholar
Tatamibari is NP-complete
Aviv Adler, Jeffrey Bosboom, E. Demaine, M. Demaine +2 more
2020Fun with Algorithms16 citations
Semantic Scholar
Reconfiguring Undirected Paths
E. Demaine, D. Eppstein, Adam Hesterberg, Kshitij Jain +3 more
2019Workshop on Algorithms and Data Structures16 citations Open access
Semantic Scholar
Computing Convex Partitions for Point Sets in the Plane: The CG: SHOP Challenge 2020
E. Demaine, S. Fekete, Phillip Keldenich, Dominik Krupke +1 more
2020arXiv.org15 citations
Semantic Scholar
Pushing Blocks via Checkable Gadgets: PSPACE-Completeness of Push-1F and Block/Box Dude
Hayashi Ani, Lily Chung, E. Demaine, Jenny Diomidova +2 more
2024Fun with Algorithms14 citations
Semantic Scholar
Toward a General Complexity Theory of Motion Planning: Characterizing Which Gadgets Make Games Hard.
E. Demaine, D. Hendrickson, J. Lynch
202014 citations
Semantic Scholar
Characterizing Universal Reconfigurability of Modular Pivoting Robots
H. Akitaya, E. Demaine, Andrei Gonczi, D. Hendrickson +6 more
2020International Symposium on Computational Geometry13 citations
Semantic Scholar
Reconfiguration of Non-crossing Spanning Trees
O. Aichholzer, Brad Ballinger, T. Biedl, Mirela Damian +6 more
2022arXiv.org11 citations Open access
Semantic Scholar
Tetris is NP-hard even with $O(1)$ rows or columns
Sualeh Asif, Michael J. Coulombe, E. Demaine, M. Demaine +3 more
2020Journal of Information Processing11 citations Open access
Semantic Scholar
Trains, Games, and Complexity: 0/1/2-Player Motion Planning through Input/Output Gadgets
Joshua Ani, E. Demaine, D. Hendrickson, J. Lynch
2020Workshop on Algorithms and Computation11 citations
Semantic Scholar
PSPACE-completeness of Pulling Blocks to Reach a Goal
Joshua Ani, Sualeh Asif, E. Demaine, Jenny Diomidova +4 more
2020Journal of Information Processing11 citations Open access
Semantic Scholar
Approximating the Canadian Traveller Problem with Online Randomization
E. Demaine, Yamming Huang, Chung-Shou Liao, K. Sadakane
2021Algorithmica10 citations Open access
Semantic Scholar
Tiling with Three Polygons is Undecidable
E. Demaine, S. Langerman
2024International Symposium on Computational Geometry8 citations
Semantic Scholar
PSPACE-Completeness of Reversible Deterministic Systems
E. Demaine, R. Hearn, D. Hendrickson, J. Lynch
2022Machines, Computations, and Universality8 citations Open access
Semantic Scholar
Yin-Yang Puzzles are NP-complete
E. Demaine, J. Lynch, Mikhail Rudoy, Yushi Uno
2021Canadian Conference on Computational Geometry8 citations
Semantic Scholar
Edge Matching with Inequalities, Triangles, Unknown Shape, and Two Players
Jeffrey Bosboom, Charlotte Chen, Lily Chung, Spencer Compton +11 more
2020Journal of Information Processing8 citations Open access
Semantic Scholar
Every Author as First Author
E. Demaine, M. Demaine
2023arXiv.org7 citations Open access
Semantic Scholar
Traversability, Reconfiguration, and Reachability in the Gadget Framework
Joshua Ani, E. Demaine, Yevhenii Diomidov, D. Hendrickson +1 more
2022Algorithmica7 citations Open access
Semantic Scholar
Complexity of Retrograde and Helpmate Chess Problems: Even Cooperative Chess is Hard
Josh Brunner, E. Demaine, D. Hendrickson, Julian Wellman
2020International Symposium on Algorithms and Computation7 citations
Semantic Scholar
Finding Closed Quasigeodesics on Convex Polyhedra
E. Demaine, Adam Hesterberg, Jason S. Ku
2020International Symposium on Computational Geometry7 citations
Semantic Scholar
Reconfiguration Algorithms for Cubic Modular Robots with Realistic Movement Constraints
MIT--NASA Space Robots Team, Josh Brunner, Kenneth C. Cheung, E. Demaine +4 more
2024Scandinavian Workshop on Algorithm Theory6 citations
Semantic Scholar
Tetris with Few Piece Types
Mit Hardness Group, E. Demaine, Holden Hall, Jeffery Li
2024Fun with Algorithms5 citations
Semantic Scholar
Kirigami Corrugations: Strong, Modular, and Programmable Plate Lattices
Alfonso Parra Rubio, Klara Mundilova, D. Preiss, E. Demaine +1 more
2023Volume 8: 47th Mechanisms and Robotics Conference (MR)5 citations
Semantic Scholar
The Legend of Zelda: The Complexity of Mechanics
Jeffrey Bosboom, Josh Brunner, Michael J. Coulombe, E. Demaine +3 more
2022arXiv.org5 citations Open access
Semantic Scholar
ASP-Completeness of Hamiltonicity in Grid Graphs, with Applications to Loop Puzzles
Mit Hardness Group, Josh Brunner, Lily Chung, E. Demaine +3 more
2024Fun with Algorithms4 citations
Semantic Scholar
You Can't Solve These Super Mario Bros. Levels: Undecidable Mario Games
E. Demaine, Holden Hall, Hayashi Layers, Ricardo Ruiz +1 more
2024Fun with Algorithms4 citations
Semantic Scholar
Complexity of Solo Chess with Unlimited Moves
Josh Brunner, Lily Chung, Michael J. Coulombe, E. Demaine +2 more
2023JCDCGGG4 citations Open access
Semantic Scholar
Complexity of Reconfiguration in Surface Chemical Reaction Networks
Robert M. Alaniz, Josh Brunner, Michael J. Coulombe, E. Demaine +8 more
2023DNA4 citations Open access
Semantic Scholar
Curved-Crease Origami Spirals Constructed from Reflected Cones
Klara Mundilova, E. Demaine, Robert J. Lang, Tomohiro Tachi
20234 citations
Semantic Scholar
On the effects of hierarchical self-assembly for reducing program-size complexity
Sarah Cannon, E. Demaine, M. Demaine, Sarah Eisenstat +5 more
2021Theoretical Computer Science4 citations Open access
Semantic Scholar
Scalable Equilibrium Computation in Multi-agent Influence Games on Networks
Fotini Christia, Michael J. Curry, C. Daskalakis, E. Demaine +5 more
2021AAAI Conference on Artificial Intelligence4 citations Open access
Semantic Scholar
2048 Without Merging
H. Akitaya, E. Demaine, Jason S. Ku, J. Lynch +1 more
2020Canadian Conference on Computational Geometry4 citations
Semantic Scholar
Recursed is not Recursive: A Jarring Result
E. Demaine, Justin Kopinsky, J. Lynch
2020International Symposium on Algorithms and Computation4 citations
Semantic Scholar
Folding Small Polyominoes into a Unit Cube
Kingston Yao Czajkowski, E. Demaine, M. Demaine, Kim Eppling +3 more
2020Canadian Conference on Computational Geometry4 citations
Semantic Scholar
Belga B-Trees
E. Demaine, J. Iacono, G. Koumoutsos, S. Langerman
2019Theory of Computing Systems4 citations Open access
Semantic Scholar
PSPACE-Hard 2D Super Mario Games: Thirteen Doors
Mit Hardness Group, Hayashi Ani, E. Demaine, Holden Hall +1 more
2024Fun with Algorithms3 citations
Semantic Scholar
Celeste is PSPACE-hard
Lily Chung, E. Demaine
2022arXiv.org3 citations Open access
Semantic Scholar
Palindrome Re ognition Using a Multidimensional Tape
T. Biedl, Jonathan F. Buss, E. Demaine, M. Demaine +1 more
20213 citations
Semantic Scholar
Acutely Triangulated, Stacked, and Very Ununfoldable Polyhedra
E. Demaine, M. Demaine, D. Eppstein
2020Canadian Conference on Computational Geometry3 citations
Semantic Scholar
Adventures in Maze Folding Art
E. Demaine, M. Demaine
2020Journal of Information Processing3 citations Open access
Semantic Scholar
Negative Instance for the Edge Patrolling Beacon Problem
Zachary Abel, H. Akitaya, E. Demaine, M. Demaine +4 more
2020JCDCGGG3 citations Open access
Semantic Scholar
Design of Circular-Arc Curved Creases of Constant Fold Angle
E. Demaine, M. Demaine, Klara Mundilova
20203 citations
Semantic Scholar
Simulation of programmable matter systems using active tile-based self-assembly
John Calvin Alumbaugh, Joshua J. Daymude, E. Demaine, Matthew J. Patitz +1 more
2019Natural Computing3 citations Open access
Semantic Scholar
Some Polycubes Have No Edge-Unzipping
E. Demaine, M. Demaine, D. Eppstein, J. O'Rourke
2019arXiv.org3 citations
Semantic Scholar
Complexity of Motion Planning of Arbitrarily Many Robots: Gadgets, Petri Nets, and Counter Machines
Joshua Ani, Michael J. Coulombe, E. Demaine, Jenny Diomidova +3 more
2023Symposium on Algorithmic Foundations of Dynamic Networks2 citations Open access
Semantic Scholar