Erik D. Demaine

ORCID

Publication Activity (10 Years)

Years Active: 1996-2024
Publications (10 Years): 271

Top Venues

Publications

MIT Hardness Group, Josh Brunner, Della H. Hendrickson, Lily Chung, Erik D. Demaine, Andy Tockman
ASP-Completeness of Hamiltonicity in Grid Graphs, with Applications to Loop Puzzles. CoRR (2024)
MIT Hardness Group, Josh Brunner, Lily Chung, Erik D. Demaine, Della H. Hendrickson, Andy Tockman
ASP-Completeness of Hamiltonicity in Grid Graphs, with Applications to Loop Puzzles. FUN (2024)
Rebecca Lin, Wenzhong Yan, Ankur Mehta, Erik D. Demaine
Routing Reconfigurations. SCF Adjunct (2024)
MIT CompGeom Group, Hugo A. Akitaya, Erik D. Demaine, Adam Hesterberg, Anna Lubiw, Jayson Lynch, Joseph O'Rourke, Frederick Stock
Super Guarding and Dark Rays in Art Galleries. CoRR (2024)
MIT-NASA Space Robots Team, Josh Brunner, Kenneth C. Cheung, Erik D. Demaine, Jenny Diomidova, Christine Gregg, Della H. Hendrickson, Irina Kostitsyna
Reconfiguration Algorithms for Cubic Modular Robots with Realistic Movement Constraints. SWAT (2024)
MIT Hardness Group, Erik D. Demaine, Holden Hall, Jeffery Li
Tetris with Few Piece Types. CoRR (2024)
Hayashi Ani, Josh Brunner, Erik D. Demaine, Jenny Diomidova, Timothy Gomez, Della H. Hendrickson, Yael Kirkpatrick, Jeffery Li, Jayson Lynch, Ritam Nag, Frederick Stock
Agent Motion Planning as Block Asynchronous Cellular Automata: Pushing, Pulling, Suplexing, and More. UCNC (2024)
MIT Hardness Group, Hayashi Ani, Erik D. Demaine, Holden Hall, Ricardo Ruiz, Naveen Venkat
You Can't Solve These Super Mario Bros. Levels: Undecidable Mario Games. FUN (2024)
MIT Hardness Group, Hayashi Ani, Erik D. Demaine, Holden Hall, Ricardo Ruiz, Naveen Venkat
You Can't Solve These Super Mario Bros. Levels: Undecidable Mario Games. CoRR (2024)
MIT Hardness Group, Hayashi Ani, Erik D. Demaine, Holden Hall, Matias Korman
PSPACE-Hard 2D Super Mario Games: Thirteen Doors. CoRR (2024)
MIT Hardness Group, Nithid Anchaleenukoon, Alex Dang, Erik D. Demaine, Kaylee Ji, Pitchayut Saengrungkongka
Complexity of 2D Snake Cube Puzzles. CoRR (2024)
Erik D. Demaine, Yael Kirkpatrick, Rebecca Lin
Graph Threading. ITCS (2024)
MIT Hardness Group, Erik D. Demaine, Holden Hall, Jeffery Li
Tetris with Few Piece Types. FUN (2024)
MIT-NASA Space Robots Team, Josh Brunner, Kenneth C. Cheung, Erik D. Demaine, Jenny Diomidova, Christine Gregg, Della H. Hendrickson, Irina Kostitsyna
Reconfiguration Algorithms for Cubic Modular Robots with Realistic Movement Constraints. CoRR (2024)
MIT Hardness Group, Hayashi Ani, Erik D. Demaine, Holden Hall, Matias Korman
PSPACE-Hard 2D Super Mario Games: Thirteen Doors. FUN (2024)
Erik D. Demaine, Yael Kirkpatrick, Rebecca Lin
Graph Threading with Turn Costs. CoRR (2024)
Joseph O'Rourke, Hugo A. Akitaya, Erik D. Demaine, Adam Hesterberg, Anna Lubiw, Jayson Lynch, Frederick Stock
Super Guarding and Dark Rays in Art Galleries. CCCG (2023)
Joshua Ani, Michael J. Coulombe, Erik D. Demaine, Yevhenii Diomidov, Timothy Gomez, Dylan H. Hendrickson, Jayson Lynch
Complexity of Motion Planning of Arbitrarily Many Robots: Gadgets, Petri Nets, and Counter Machines. SAND (2023)
Erik D. Demaine, Maarten Löffler, Christiane Schmidt
Rectangular Spiral Galaxies are still hard. Comput. Geom. 110 (2023)
Joshua Ani, Erik D. Demaine, Dylan H. Hendrickson, Jayson Lynch
Trains, games, and complexity: 0/1/2-player motion planning through input/output gadgets. Theor. Comput. Sci. 969 (2023)
Hugo A. Akitaya, Josh Brunner, Erik D. Demaine, Dylan H. Hendrickson, Victor Luo, Andy Tockman
Complexity of Simple Folding of Mixed Orthogonal Crease Patterns. CoRR (2023)
Robert M. Alaniz, Josh Brunner, Michael J. Coulombe, Erik D. Demaine, Yevhenii Diomidov, Ryan Knobel, Timothy Gomez, Elise Grizzell, Jayson Lynch, Andrew Rodriguez, Robert T. Schweller, Tim Wylie
Complexity of Reconfiguration in Surface Chemical Reaction Networks. CoRR (2023)
Joshua Ani, Erik D. Demaine, Yevhenii Diomidov, Dylan H. Hendrickson, Jayson Lynch
Traversability, Reconfiguration, and Reachability in the Gadget Framework. Algorithmica 85 (11) (2023)
Josh Brunner, Lily Chung, Michael J. Coulombe, Erik D. Demaine, Timothy Gomez, Jayson Lynch
Complexity of Solo Chess with Unlimited Moves. CoRR (2023)
Aviv Adler, Joshua Ani, Lily Chung, Michael J. Coulombe, Erik D. Demaine, Yevhenii Diomidov, Dylan H. Hendrickson, Jayson Lynch
This Game Is Not Going To Analyze Itself. CoRR (2023)
Robert M. Alaniz, Michael J. Coulombe, Erik D. Demaine, Bin Fu, Ryan Knobel, Timothy Gomez, Elise Grizzell, Andrew Rodriguez, Robert T. Schweller, Tim Wylie
Reconfiguration of Linear Surface Chemical Reaction Networks with Bounded State Change. CCCG (2023)
MIT CompGeom Group, Zachary Abel, Hugo A. Akitaya, Erik D. Demaine, Adam C. Hesterberg, Jayson Lynch
When Can You Tile an Integer Rectangle with Integer Squares? CoRR (2023)
Robert M. Alaniz, Josh Brunner, Michael J. Coulombe, Erik D. Demaine, Jenny Diomidova, Timothy Gomez, Elise Grizzell, Ryan Knobel, Jayson Lynch, Andrew Rodriguez, Robert T. Schweller, Tim Wylie
Complexity of Reconfiguration in Surface Chemical Reaction Networks. DNA (2023)
Erik D. Demaine, Martin L. Demaine, Yevhenii Diomidov, Tonan Kamata, Ryuhei Uehara, Hanyu Alice Zhang
(1) refoldings. Comput. Geom. 113 (2023)
Erik D. Demaine, Martin L. Demaine, Ryuhei Uehara
Developing a tetramonohedron with minimum cut length. Comput. Geom. 108 (2023)
Erik D. Demaine, Martin L. Demaine
Every Author as First Author. CoRR (2023)
Erik D. Demaine, Kritkorn Karntikoon, Nipun Pitimanaaree
2-Colorable Perfect Matching is NP-complete in 2-Connected 3-Regular Planar Graphs. CoRR (2023)
Joshua Ani, Michael J. Coulombe, Erik D. Demaine, Yevhenii Diomidov, Timothy Gomez, Dylan H. Hendrickson, Jayson Lynch
Complexity of Motion Planning of Arbitrarily Many Robots: Gadgets, Petri Nets, and Counter Machines. CoRR (2023)
Elena Arseneva, Erik D. Demaine, Tonan Kamata, Ryuhei Uehara
Discretization to Prove the Nonexistence of "Small" Common Unfoldings Between Polyhedra. CCCG (2022)
Joshua Ani, Lily Chung, Erik D. Demaine, Yevhenii Diomidov, Dylan H. Hendrickson, Jayson Lynch
Pushing Blocks via Checkable Gadgets: PSPACE-Completeness of Push-1F and Block/Box Dude. FUN (2022)
Lily Chung, Erik D. Demaine
Celeste is PSPACE-hard. CoRR (2022)
Joshua Ani, Erik D. Demaine, Dylan H. Hendrickson, Jayson Lynch
Trains, Games, and Complexity: 0/1/2-Player Motion Planning Through Input/Output Gadgets. WALCOM (2022)
Joshua Ani, Erik D. Demaine, Yevhenii Diomidov, Dylan H. Hendrickson, Jayson Lynch
Traversability, Reconfiguration, and Reachability in the Gadget Framework. CoRR (2022)
Erik D. Demaine, Hiro Ito, Jayson Lynch, Ryuhei Uehara
Computational Complexity of Flattening Fixed-Angle Orthogonal Chains. CCCG (2022)
Erik D. Demaine, Robert A. Hearn, Dylan H. Hendrickson, Jayson Lynch
PSPACE-Completeness of Reversible Deterministic Systems. CoRR (2022)
Lily Chung, Erik D. Demaine, Dylan H. Hendrickson, Victor Luo
Flat Folding an Unassigned Single-Vertex Complex (Combinatorially Embedded Planar Graph with Specified Edge Lengths) Without Flat Angles. SoCG (2022)
Erik D. Demaine, Hiro Ito, Jayson Lynch, Ryuhei Uehara
Computational Complexity of Flattening Fixed-Angle Orthogonal Chains. CoRR (2022)
Sagnik Saha, Erik D. Demaine
ZHED is NP-complete. CCCG (2022)
Lily Chung, Erik D. Demaine, Dylan H. Hendrickson, Victor Luo
Flat Folding an Unassigned Single-Vertex Complex (Combinatorially Embedded Planar Graph with Specified Edge Lengths) without Flat Angles. CoRR (2022)
Joshua Ani, Josh Brunner, Erik D. Demaine, Martin L. Demaine, Dylan H. Hendrickson, Victor Luo, Rachana Madhukara
Orthogonal Fold & Cut. CoRR (2022)
Erik D. Demaine, Robert A. Hearn, Dylan H. Hendrickson, Jayson Lynch
PSPACE-Completeness of Reversible Deterministic Systems. MCU (2022)
Hugo A. Akitaya, Erik D. Demaine, David Eppstein, Tomohiro Tachi, Ryuhei Uehara
Ununfoldable polyhedra with 6 vertices or 6 faces. Comput. Geom. 103 (2022)
Joshua Ani, Erik D. Demaine, Yevhenii Diomidov, Dylan H. Hendrickson, Jayson Lynch
Traversability, Reconfiguration, and Reachability in the Gadget Framework. WALCOM (2022)
Oswin Aichholzer, Erik D. Demaine, Matias Korman, Anna Lubiw, Jayson Lynch, Zuzana Masárová, Mikhail Rudoy, Virginia Vassilevska Williams, Nicole Wein
Hardness of Token Swapping on Trees. ESA (2022)
Lily Chung, Erik D. Demaine, Dylan H. Hendrickson, Jayson Lynch
Lower Bounds on Retroactive Data Structures. ISAAC (2022)
Erik D. Demaine, Kritkorn Karntikoon
Unfolding Orthotubes with a Dual Hamiltonian Path. CoRR (2022)
Akira Baes, Erik D. Demaine, Martin L. Demaine, Elizabeth Hartung, Stefan Langerman, Joseph O'Rourke, Ryuhei Uehara, Yushi Uno, Aaron Williams
Rolling Polyhedra on Tessellations. FUN (2022)
Lily Chung, Erik D. Demaine, Dylan H. Hendrickson, Jayson Lynch
Lower Bounds on Retroactive Data Structures. CoRR (2022)
Jeffrey Bosboom, Josh Brunner, Michael J. Coulombe, Erik D. Demaine, Dylan H. Hendrickson, Jayson Lynch, Elle Najt
The Legend of Zelda: The Complexity of Mechanics. CoRR (2022)
Oswin Aichholzer, Brad Ballinger, Therese Biedl, Mirela Damian, Erik D. Demaine, Matias Korman, Anna Lubiw, Jayson Lynch, Josef Tkadlec, Yushi Uno
Reconfiguration of Non-crossing Spanning Trees. CoRR (2022)
Hugo A. Akitaya, Erik D. Demaine, Matias Korman, Irina Kostitsyna, Irene Parada, Willem Sonke, Bettina Speckmann, Ryuhei Uehara, Jules Wulms
Compacting Squares: Input-Sensitive In-Place Reconfiguration of Sliding Squares. SWAT (2022)
Erik D. Demaine, Sándor P. Fekete, Phillip Keldenich, Dominik Krupke, Joseph S. B. Mitchell
Area-Optimal Simple Polygonalizations: The CG Challenge 2019. ACM J. Exp. Algorithmics 27 (2022)
Zachary Abel, Erik D. Demaine, Martin L. Demaine, Jason S. Ku, Jayson Lynch, Jin-ichi Itoh, Chie Nara
Continuous Flattening of All Polyhedral Manifolds using Countably Infinite Creases. CoRR (2021)
Hugo A. Akitaya, Esther M. Arkin, Mirela Damian, Erik D. Demaine, Vida Dujmovic, Robin Y. Flatland, Matias Korman, Belén Palop, Irene Parada, André van Renssen, Vera Sacristán
Universal Reconfiguration of Facet-Connected Modular Robots by Pivots: The O(1) Musketeers. Algorithmica 83 (5) (2021)
Vincent Bian, Erik D. Demaine, Rachana Madhukara
Edge-Unfolding Prismatoids: Tall or Rectangular Base. CoRR (2021)
Erik D. Demaine, Jayson Lynch, Mikhail Rudoy, Yushi Uno
Yin-Yang Puzzles are NP-complete. CoRR (2021)
Erik D. Demaine, Jayson Lynch, Jiaying Sun
An Efficient Reversible Algorithm for Linear Regression. ICRC (2021)
Hugo A. Akitaya, Brad Ballinger, Erik D. Demaine, Thomas C. Hull, Christiane Schmidt
Folding Points to a Point and Lines to a Line. CCCG (2021)
Vincent Bian, Erik D. Demaine, Rachana Madhukara
Edge-Unfolding Prismatoids: Tall or Rectangular Base. CCCG (2021)
Hugo A. Akitaya, Erik D. Demaine, Andrei Gonczi, Dylan H. Hendrickson, Adam Hesterberg, Matias Korman, Oliver Korten, Jayson Lynch, Irene Parada, Vera Sacristán
Characterizing Universal Reconfigurability of Modular Pivoting Robots. SoCG (2021)
Josh Brunner, Lily Chung, Erik D. Demaine, Dylan H. Hendrickson, Adam Hesterberg, Adam Suhl, Avi Zeff
1 X 1 Rush Hour with Fixed Blocks Is PSPACE-Complete. FUN (2021)
Oswin Aichholzer, Erik D. Demaine, Matias Korman, Jayson Lynch, Anna Lubiw, Zuzana Masárová, Mikhail Rudoy, Virginia Vassilevska Williams, Nicole Wein
Hardness of Token Swapping on Trees. CoRR (2021)
Erik D. Demaine, Jayson Lynch, Mikhail Rudoy, Yushi Uno
Yin-Yang Puzzles are NP-complete. CCCG (2021)
Oswin Aichholzer, Hugo A. Akitaya, Kenneth C. Cheung, Erik D. Demaine, Martin L. Demaine, Sándor P. Fekete, Linda Kleist, Irina Kostitsyna, Maarten Löffler, Zuzana Masárová, Klara Mundilova, Christiane Schmidt
Folding polyominoes with holes into a cube. Comput. Geom. 93 (2021)
Erik D. Demaine, Martin L. Demaine, Yevhenii Diomidov, Tonan Kamata, Ryuhei Uehara, Hanyu Alice Zhang
Any Regular Polyhedron Can Transform to Another by O(1) Refoldings. CCCG (2021)
Erik D. Demaine, Sándor P. Fekete, Phillip Keldenich, Dominik Krupke, Joseph S. B. Mitchell
Area-Optimal Simple Polygonalizations: The CG Challenge 2019. CoRR (2021)
Erik D. Demaine, Adam Hesterberg, Frederic Koehler, Jayson Lynch, John C. Urschel
Multidimensional Scaling: Approximation and Complexity. CoRR (2021)
Erik D. Demaine, John Iacono, Grigorios Koumoutsos, Stefan Langerman
Belga B-Trees. Theory Comput. Syst. 65 (3) (2021)
Erik D. Demaine, Adam Hesterberg, Frederic Koehler, Jayson Lynch, John C. Urschel
Multidimensional Scaling: Approximation and Complexity. ICML (2021)
Zachary Abel, Hugo A. Akitaya, Man-Kwun Chiu, Erik D. Demaine, Martin L. Demaine, Adam Hesterberg, Matias Korman, Jayson Lynch, André van Renssen, Marcel Roeloffzen
Snipperclips: Cutting tools into desired polygons using themselves. Comput. Geom. 98 (2021)
Erik D. Demaine, Maarten Löffler, Christiane Schmidt
Rectangular Spiral Galaxies are Still Hard. CoRR (2021)
Sagnik Saha, Erik D. Demaine
ZHED is NP-complete. CoRR (2021)
Joshua Ani, Jeffrey Bosboom, Erik D. Demaine, Yevhenii Diomidov, Dylan H. Hendrickson, Jayson Lynch
Walking Through Doors Is Hard, Even Without Staircases: Proving PSPACE-Hardness via Planar Assemblies of Door Gadgets. FUN (2021)
Erik D. Demaine, Yamming Huang, Chung-Shou Liao, Kunihiko Sadakane
Approximating the Canadian Traveller Problem with Online Randomization. Algorithmica 83 (5) (2021)
Zachary Abel, Erik D. Demaine, Martin L. Demaine, Jason S. Ku, Jayson Lynch, Jin-ichi Itoh, Chie Nara
Continuous flattening of all polyhedral manifolds using countably infinite creases. Comput. Geom. 98 (2021)
Aviv Adler, Jeffrey Bosboom, Erik D. Demaine, Martin L. Demaine, Quanquan C. Liu, Jayson Lynch
Tatamibari Is NP-Complete. FUN (2021)
Zachary Abel, Hugo A. Akitaya, Man-Kwun Chiu, Erik D. Demaine, Martin L. Demaine, Adam Hesterberg, Matias Korman, Jayson Lynch, André van Renssen, Marcel Roeloffzen
Snipperclips: Cutting Tools into Desired Polygons using Themselves. CoRR (2021)
Erik D. Demaine, Martin L. Demaine, Yevhenii Diomidov, Tonan Kamata, Ryuhei Uehara, Hanyu Alice Zhang
Any Regular Polyhedron Can Transform to Another by O(1) Refoldings. CoRR (2021)
Sarah Cannon, Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, David Furcy, Matthew J. Patitz, Robert T. Schweller, Scott M. Summers, Andrew Winslow
On the effects of hierarchical self-assembly for reducing program-size complexity. Theor. Comput. Sci. 894 (2021)
Erik D. Demaine, Yevhenii Diomidov
Strings-and-Coins and Nimstring are PSPACE-complete. CoRR (2021)
Fotini Christia, Michael J. Curry, Constantinos Daskalakis, Erik D. Demaine, John P. Dickerson, MohammadTaghi Hajiaghayi, Adam Hesterberg, Marina Knittel, Aidan Milliff
Scalable Equilibrium Computation in Multi-agent Influence Games on Networks. AAAI (2021)
Sualeh Asif, Michael J. Coulombe, Erik D. Demaine, Martin L. Demaine, Adam Hesterberg, Jayson Lynch, Mihir Singhal
(1) Rows or Columns. J. Inf. Process. 28 (2020)
Jean Cardinal, Erik D. Demaine, David Eppstein, Robert A. Hearn, Andrew Winslow
Reconfiguration of satisfying assignments and subset sums: Easy to find, hard to connect. Theor. Comput. Sci. 806 (2020)
Sualeh Asif, Michael J. Coulombe, Erik D. Demaine, Martin L. Demaine, Adam Hesterberg, Jayson Lynch, Mihir Singhal
Tetris is NP-hard even with $O(1)$ rows or columns. CoRR (2020)
Erik D. Demaine
Tribute to Godfried Toussaint. CCCG (2020)
Jeffrey Bosboom, Charlotte Chen, Lily Chung, Spencer Compton, Michael J. Coulombe, Erik D. Demaine, Martin L. Demaine, Ivan Tadeu Ferreira Antunes Filho, Dylan H. Hendrickson, Adam Hesterberg, Calvin Hsu, William Hu, Oliver Korten, Zhezheng Luo, Lillian Zhang
Edge Matching with Inequalities, Triangles, Unknown Shape, and Two Players. J. Inf. Process. 28 (2020)
Man-Kwun Chiu, Erik D. Demaine, Yevhenii Diomidov, David Eppstein, Robert A. Hearn, Adam Hesterberg, Matias Korman, Irene Parada, Mikhail Rudoy
New Results in Sona Drawing: Hardness and TSP Separation. CCCG (2020)
Erik D. Demaine, Martin L. Demaine, Hiro Ito, Chie Nara, Izumi Shirahama, Tomohiro Tachi, Mizuho Tomura
Flat Folding a Strip with Parallel or Nonacute Zigzag Creases with Mountain-Valley Assignment. J. Inf. Process. 28 (2020)
Erik D. Demaine, Martin L. Demaine, David Eppstein
Acutely Triangulated, Stacked, and Very Ununfoldable Polyhedra. CoRR (2020)
Leo Alcock, Sualeh Asif, Jeffrey Bosboom, Josh Brunner, Charlotte Chen, Erik D. Demaine, Rogers Epstein, Adam Hesterberg, Lior Hirschfeld, William Hu, Jayson Lynch, Sarah Scheffler, Lillian Zhang
Arithmetic Expression Construction. CoRR (2020)
Erik D. Demaine, Martin L. Demaine
Adventures in Maze Folding Art. J. Inf. Process. 28 (2020)
Erik D. Demaine, Martin L. Demaine, David Eppstein, Joseph O'Rourke
Some Polycubes Have No Edge Zipper Unfolding. CCCG (2020)
Joshua Ani, Jeffrey Bosboom, Erik D. Demaine, Yevhenii Diomidov, Dylan H. Hendrickson, Jayson Lynch
Walking through Doors is Hard, even without Staircases: Proving PSPACE-hardness via Planar Assemblies of Door Gadgets. CoRR (2020)
Hugo A. Akitaya, Erik D. Demaine, Andrei Gonczi, Dylan H. Hendrickson, Adam Hesterberg, Matias Korman, Oliver Korten, Jayson Lynch, Irene Parada, Vera Sacristán
Characterizing Universal Reconfigurability of Modular Pivoting Robots. CoRR (2020)
Erik D. Demaine, Hiro Ito, Stefan Langerman, Jayson Lynch, Mikhail Rudoy, Kai Xiao
Cookie Clicker. Graphs Comb. 36 (2) (2020)

Erik D. Demaine.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Erik D. Demaine