vix.ing · top · new · best · stats · spec

Demaine, Erik D.

  1. Classic Nintendo Games are (Computationally) Hard
    2012/03/08 by Greg Aloupis, Erik D. Demaine, Aloupis, Greg +5 · 12 voices
    #cs.CC #cs.GT
  2. Tiling with Three Polygons is Undecidable
    2024/09/17 by Erik D. Demaine, Demaine, Erik D., Stefan Langerman +1 · 8 voices · 3 citations
    #cs.CG #math.MG
  3. Tetris is Hard, Even to Approximate
    2002/10/21 by Erik D. Demaine, Demaine, Erik D., Susan Hohenberger +3 · 2 voices · 3 citations
    Computer Science · #cs.CC #cs.CG #cs.DM
  4. 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
  5. Every Author as First Author
    2023/04/03 by Erik D. Demaine, Martin L. Demaine, Demaine, Erik D. +1 · 6 voices
    #cs.DL
  6. Logarithmic Lower Bounds in the Cell-Probe Model
    2005/02/08 by Mihai Pǎtraşcu, Mihai Patrascu, Erik D. Demaine +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
  7. PushPush and Push-1 are NP-hard in 2D
    2000/07/13 by Erik D. Demaine, Martin L. Demaine, Demaine, Erik D. +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
  8. 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
  9. 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
  10. 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
  11. Characterization of Curved Creases and Rulings: Design and Analysis of Lens Tessellations
    2015/02/11 by Erik D. Demaine, Martin L. Demaine, Demaine, Erik D. +7 · 2 citations
    Engineering · Computer Science · #Advanced Materials and Mechanics #Advanced Numerical Analysis Techniques #Computational Geometry and Mesh Generation
  12. Reconfiguring Undirected Paths
    2019/05/01 by Demaine, Erik D., Eppstein, David, Hesterberg, Adam +4 · 2 citations
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  13. When Can You Fold a Map?
    2000/11/20 by Esther M. Arkin, Michael A. Bender, Arkin, Esther M. +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
  14. 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
  15. Playing Games with Algorithms: Algorithmic Combinatorial Game Theory
    2001/06/11 by Demaine, Erik D., Hearn, Robert A. · 1 citation
    #Combinatorics (math.CO) #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #F.1.3 #F.2.2 #FOS: Computer and information sciences #FOS: Mathematics #G.2.1
  16. Long Proteins with Unique Optimal Foldings in the H-P Model
    2002/01/21 by Oswin Aichholzer, David Bremner, Aichholzer, Oswin +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
  17. De Dictionariis Dynamicis Pauco Spatio Utentibus
    2005/12/20 by Demaine, Erik D., der Heide, Friedhelm Meyer auf, Pagh, Rasmus +1 · 1 citation
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  18. 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
  19. Minimizing Movement: Fixed-Parameter Tractability
    2012/05/31 by Demaine, Erik D., Hajiaghayi, MohammadTaghi, Marx, Dániel · 1 citation
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  20. Zig-Zag Numberlink is NP-Complete
    2014/10/21 by Adcock, Aaron, Demaine, Erik D., Demaine, Martin L. +4 · 1 citation
    #Computational Complexity (cs.CC) #FOS: Computer and information sciences
  21. Energy-Efficient Algorithms
    2016/05/26 by Erik D. Demaine, Jayson Lynch, Demaine, Erik D. +5 · 1 citation
    Computer Science · #Computability, Logic, AI Algorithms #Parallel Computing and Optimization Techniques #Quantum Computing Algorithms and Architecture
  22. The Computational Complexity of Portal and Other 3D Video Games
    2016/11/30 by Demaine, Erik D., Lockhart, Joshua, Lynch, Jayson · 1 citation
    #Computational Complexity (cs.CC) #FOS: Computer and information sciences
  23. Particle Computation: Complexity, Algorithms, and Logic
    2017/12/04 by Becker, Aaron T., Demaine, Erik D., Fekete, Sándor P. +2 · 1 citation
    #Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #Distributed #Emerging Technologies (cs.ET) #FOS: Computer and information sciences #Parallel #Robotics (cs.RO) #and Cluster Computing (cs.DC)
  24. 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)
  25. Nearly Optimal Separation Between Partially And Fully Retroactive Data Structures
    2018/04/18 by Chen, Lijie, Demaine, Erik D., Gu, Yuzhou +3 · 1 citation
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  26. Structural Sparsity of Complex Networks: Bounded Expansion in Random Models and Real-World Graphs
    2014/06/10 by Demaine, Erik D., Reidl, Felix, Rossmanith, Peter +3 · 1 citation
    #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Physical sciences #Physics and Society (physics.soc-ph) #Social and Information Networks (cs.SI)
  27. Folding Polyominoes with Holes into a Cube
    2019/10/22 by Aichholzer, Oswin, Akitaya, Hugo A., Cheung, Kenneth C. +9 · 1 citation
    #Computational Geometry (cs.CG) #F.2.2 #FOS: Computer and information sciences
  28. Tatamibari is NP-complete
    2020/03/18 by Adler, Aviv, Bosboom, Jeffrey, Demaine, Erik D. +3 · 1 citation
    #Computational Complexity (cs.CC) #Computational Geometry (cs.CG) #FOS: Computer and information sciences
  29. Computing Convex Partitions for Point Sets in the Plane: The CG:SHOP Challenge 2020
    2020/04/08 by Demaine, Erik D., Fekete, Sándor P., Keldenich, Phillip +2 · 1 citation
    #Computational Geometry (cs.CG) #F.2.2 #FOS: Computer and information sciences
  30. Tetris is NP-hard even with O(1) rows or columns
    2020/09/29 by Asif, Sualeh, Coulombe, Michael, Demaine, Erik D. +4 · 1 citation
    #Computational Complexity (cs.CC) #FOS: Computer and information sciences
  31. Remarks on separating words
    2011/03/23 by Erik D. Demaine, Demaine, Erik D., Sarah Eisenstat +5 · 1 citation
    Computer Science · Biochemistry, Genetics and Molecular Biology · #semigroups and automata theory #DNA and Biological Computing #Coding theory and cryptography
  32. Area-Optimal Simple Polygonalizations: The CG Challenge 2019
    2021/11/14 by Demaine, Erik D., Fekete, Sándor P., Keldenich, Phillip +2 · 1 citation
    #Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences
  33. Dudeney's Dissection is Optimal
    2024/12/05 by Erik D. Demaine, Tonan Kamata, Demaine, Erik D. +3 · 9 voices
    #cs.CG #cs.DM #math.GT
  34. PSPACE-Completeness of Reversible Deterministic Systems
    2022/07/14 by Demaine, Erik D., Hearn, Robert A., Hendrickson, Dylan +1 · 1 citation
    #Computational Complexity (cs.CC) #FOS: Computer and information sciences
  35. 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
  36. Complexity of Reconfiguration in Surface Chemical Reaction Networks
    2023/03/27 by Alaniz, Robert M., Brunner, Josh, Coulombe, Michael +9 · 1 citation
    #Computational Complexity (cs.CC) #FOS: Computer and information sciences
  37. 1 x 1 Rush Hour with Fixed Blocks is PSPACE-complete
    2020/03/22 by Brunner, Josh, Chung, Lily, Demaine, Erik D. +4 · 1 citation
    #Computational Complexity (cs.CC) #Computational Geometry (cs.CG) #FOS: Computer and information sciences
  38. Reconfiguration of Non-crossing Spanning Trees
    2022/06/08 by Aichholzer, Oswin, Ballinger, Brad, Biedl, Therese +7 · 1 citation
    #Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences
  39. Super Guarding and Dark Rays in Art Galleries
    2024/04/06 by MIT CompGeom Group, Akitaya, Hugo A., Demaine, Erik D. +5 · 1 citation
    #52C99 #Computational Geometry (cs.CG) #F.2.2 #FOS: Computer and information sciences #FOS: Mathematics #G.2.2 #Metric Geometry (math.MG)
  40. 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
  41. Reconfiguration Algorithms for Cubic Modular Robots with Realistic Movement Constraints
    2024/05/24 by NASA Space Robots Team, Brunner, Josh, Cheung, Kenneth C. +5 · 1 citation
    #Computational Geometry (cs.CG) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Robotics (cs.RO)
  42. Tetris with Few Piece Types
    2024/04/16 by MIT Hardness Group, Demaine, Erik D., Hall, Holden +1 · 1 citation
    #Computational Complexity (cs.CC) #FOS: Computer and information sciences
  43. Pushing Blocks via Checkable Gadgets: PSPACE-completeness of Push-1F and Block/Box Dude
    2024/12/28 by Ani, Hayashi, Chung, Lily, Demaine, Erik D. +3 · 2 citations
    #Computational Complexity (cs.CC) #FOS: Computer and information sciences