Erik D. Demaine
- Classic Nintendo Games are (Computationally) Hard
2012/03/08 by Greg Aloupis, Erik D. Demaine, Aloupis, Greg +5 · 12 voices
#cs.CC #cs.GT
- Tiling with Three Polygons is Undecidable
2024/09/17 by Erik D. Demaine, Stefan Langerman, Demaine, Erik D. +1 · 8 voices · 3 citations
#cs.CG #math.MG
- Tetris is Hard, Even to Approximate
2002/10/21 by Erik D. Demaine, Susan Hohenberger, Demaine, Erik D. +3 · 2 voices · 3 citations
Computer Science · #cs.CC #cs.CG #cs.DM
- Solving the Rubik's Cube Optimally is NP-complete
2017/06/21 by Erik D. Demaine, Sarah Eisenstat, Mikhail Rudoy · 1 voice · 3 citations
Computer Science · #Algorithms and Data Compression #Embedded Systems Design Techniques #Parallel Computing and Optimization Techniques
- Picture-Hanging Puzzles
2012/03/16 by Erik D. Demaine, Martin L. Demaine, Yair N. Minsky +4 · 2 voices · 1 citation
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Advanced Combinatorial Mathematics #semigroups and automata theory
- Push-Pull Block Puzzles are Hard
2017/09/05 by Erik D. Demaine, Isaac Grosof, Jayson Lynch · 1 voice · 1 citation
#cs.CC
- PSPACE-Completeness of Sliding-Block Puzzles and Other Problems through the Nondeterministic Constraint Logic Model of Computation
2002/05/04 by Robert A. Hearn, Hearn, Robert A., Erik D. Demaine +1 · 6 citations
Computer Science · #Artificial Intelligence in Games #Computational Complexity (cs.CC) #Computational Geometry and Mesh Generation #Computer Science and Game Theory (cs.GT) #F.1 #F.2.2 #FOS: Computer and information sciences #Image Processing and 3D Reconstruction #cs.CC #cs.GT
- Every Author as First Author
2023/04/03 by Erik D. Demaine, Martin L. Demaine, Demaine, Erik D. +1 · 6 voices
#cs.DL
- Logarithmic Lower Bounds in the Cell-Probe Model
2005/02/08 by Mihai Patrascu, Mihai Pǎtraşcu, Patrascu, Mihai +2 · 4 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #DNA and Biological Computing #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.CC #cs.DS
- PushPush and Push-1 are NP-hard in 2D
2000/07/13 by Erik D. Demaine, Demaine, Erik D., Martin L. Demaine +3 · 3 citations
Computer Science · #Computational Geometry (cs.CG) #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences #cs.CG #cs.DM
- Online Searching with Turn Cost
2004/06/23 by Erik D. Demaine, Sandor P. Fekete, Sándor P. Fekete +5 · 2 citations
Computer Science · Decision Sciences · #Auction Theory and Applications #Optimization and Search Problems #Web Data Mining and Analysis #cs.DS
- The complexity of UNO
2010/03/15 by Erik D. Demaine, Demaine, Erik D., Martin L. Demaine +9 · 1 voice
Computer Science · Social Sciences · Decision Sciences · #Artificial Intelligence in Games #Digital Games and Media #Game Theory and Applications
- Linear-Time Algorithm for Sliding Tokens on Trees
2014/06/25 by Erik D. Demaine, Demaine, Erik D., Martin L. Demaine +15 · 2 citations
Computer Science · #Advanced Graph Theory Research #Computational Geometry and Mesh Generation #Complexity and Algorithms in Graphs
- Characterization of Curved Creases and Rulings: Design and Analysis of Lens Tessellations
2015/02/11 by Erik D. Demaine, Demaine, Erik D., Martin L. Demaine +7 · 2 citations
Engineering · Computer Science · #Advanced Materials and Mechanics #Advanced Numerical Analysis Techniques #Computational Geometry and Mesh Generation
- When Can You Fold a Map?
2000/11/20 by Esther M. Arkin, Arkin, Esther M., Michael A. Bender +11 · 1 citation
Computer Science · #Computational Geometry (cs.CG) #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences #G.2.1 #cs.CG #cs.DM
- PushPush is NP-hard in 2D
2000/01/24 by Erik D. Demaine, Martin L. Demaine, Demaine, Erik D. +3 · 1 citation
Computer Science · #Computational Geometry (cs.CG) #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences #G.2.m #cs.CG #cs.DM
- Long Proteins with Unique Optimal Foldings in the H-P Model
2002/01/21 by Oswin Aichholzer, Aichholzer, Oswin, David Bremner +9 · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · #Biomolecules (q-bio.BM) #Computational Geometry (cs.CG) #FOS: Biological sciences #FOS: Computer and information sciences #G.2 #I.3.5 #cs.CG #q-bio.BM
- Algorithms for Solving Rubik's Cubes
2011/06/28 by Erik D. Demaine, Demaine, Erik D., Martin L. Demaine +7 · 1 citation
Computer Science · Engineering · #Algorithms and Data Compression #Combinatorics (math.CO) #Computational Complexity (cs.CC) #Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems #graph theory and CDMA systems
- Energy-Efficient Algorithms
2016/05/26 by Erik D. Demaine, Demaine, Erik D., Jayson Lynch +5 · 1 citation
Computer Science · #Computability, Logic, AI Algorithms #Parallel Computing and Optimization Techniques #Quantum Computing Algorithms and Architecture
- Coordinated Motion Planning: Reconfiguring a Swarm of Labeled Robots\n with Bounded Stretch
2018/01/05 by Erik D. Demaine, Demaine, Erik D., Sándor P. Fekete +7 · 1 citation
Computer Science · Engineering · #Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #I.2.9 #Modular Robots and Swarm Intelligence #Optimization and Search Problems #Robotic Path Planning Algorithms #Robotics (cs.RO)
- Remarks on separating words
2011/03/23 by Erik D. Demaine, Sarah Eisenstat, Demaine, Erik D. +5 · 1 citation
Computer Science · Biochemistry, Genetics and Molecular Biology · #semigroups and automata theory #DNA and Biological Computing #Coding theory and cryptography
- 07281 Abstracts Collection – Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs
2007/01/01 by Erik D. Demaine, Gregory Gutin, Demaine, Erik +5 · 1 citation
Computer Science · #Advanced Graph Theory Research #Graph Labeling and Dimension Problems
- Tetris is Hard with Just One Piece Type
2026/03/10 by MIT Hardness Group, Josh Brunner, Erik D. Demaine +2 · 1 voice
Computer Science · #cs.CC
- Dudeney's Dissection is Optimal
2024/12/05 by Erik D. Demaine, Demaine, Erik D., Tonan Kamata +3 · 9 voices
#cs.CG #cs.DM #math.GT
- Celeste is PSPACE-hard
2022/11/21 by Lily Chung, Erik D. Demaine, Chung, Lily +1 · 1 citation
Computer Science · Social Sciences · Psychology · #Artificial Intelligence in Games #Digital Games and Media #Educational Games and Gamification
- PSPACE-Hard 2D Super Mario Games: Thirteen Doors
2024/04/16 by MIT Hardness Group, Hayashi Ani, Erik D. Demaine +6 · 1 citation
Computer Science · Social Sciences · Psychology · #Artificial Intelligence in Games #Digital Games and Media #Educational Games and Gamification