|
+
PDF
Chat
|
Humanity's Last Exam
|
2025
|
Long Phan
Alice Gatti
Ziwen Han
Nathaniel Li
Josephina Hu
Hugh Zhang
Shuangshuang Shi
Michael Y. Choi
Arjun Agrawal
Asmita Chopra
|
|
+
PDF
Chat
|
Pushing Blocks via Checkable Gadgets: PSPACE-completeness of Push-1F and
Block/Box Dude
|
2024
|
Hayashi Ani
Lily Chung
Erik D. Demaine
Jenny Diomidova
Della Hendrickson
Jayson Lynch
|
|
+
PDF
Chat
|
Folding One Polyhedral Metric Graph into Another
|
2024
|
Lily Chung
Erik D. Demaine
Martin L. Demaine
Markus Hecher
Rebecca Lin
Jayson Lynch
Chiê Nara
|
|
+
PDF
Chat
|
All Polyhedral Manifolds are Connected by a 2-Step Refolding
|
2024
|
Lily Chung
Erik D. Demaine
Jenny Diomidova
Tonan Kamata
Jayson Lynch
Ryuhei Uehara
Hanyu Alice Zhang
|
|
+
PDF
Chat
|
Deltahedral Domes over Equiangular Polygons
|
2024
|
MIT CompGeom Group
Hugo A. Akitaya
Erik D. Demaine
Adam Hesterberg
Anna Lubiw
Jayson Lynch
Joseph O’Rourke
Frederick Stock
Josef Tkadlec
|
|
+
PDF
Chat
|
Super Guarding and Dark Rays in Art Galleries
|
2024
|
MIT CompGeom Group
Hugo A. Akitaya
Erik D. Demaine
Adam Hesterberg
Anna Lubiw
Jayson Lynch
Joseph O’Rourke
Frederick Stock
|
|
+
PDF
Chat
|
PSPACE-Completeness of Reversible Deterministic Systems
|
2023
|
Erik D. Demaine
Robert A. Hearn
Dylan Hendrickson
Jayson Lynch
|
|
+
PDF
Chat
|
Trains, games, and complexity: 0/1/2-player motion planning through input/output gadgets
|
2023
|
Joshua Ani
Erik D. Demaine
Dylan Hendrickson
Jayson Lynch
|
|
+
|
This Game Is Not Going To Analyze Itself
|
2023
|
Aviv Adler
Joshua Ani
Lily Chung
Michael Coulombe
Erik D. Demaine
Yevhenii Diomidov
Dylan Hendrickson
Jayson Lynch
|
|
+
|
Complexity of Solo Chess with Unlimited Moves
|
2023
|
Josh Brunner
Lily Chung
Michael Coulombe
Erik D. Demaine
Timothy M. Gómez
Jayson Lynch
|
|
+
|
Complexity of Reconfiguration in Surface Chemical Reaction Networks
|
2023
|
Robert M. Alaniz
Josh Brunner
Michael Coulombe
Erik D. Demaine
Yevhenii Diomidov
Ryan Knobel
Timothy M. Gómez
Elise Grizzell
Jayson Lynch
Andrew Rodriguez
|
|
+
|
Complexity of Motion Planning of Arbitrarily Many Robots: Gadgets, Petri Nets, and Counter Machines
|
2023
|
Joshua Ani
Michael Coulombe
Erik D. Demaine
Yevhenii Diomidov
Timothy M. Gómez
Dylan Hendrickson
Jayson Lynch
|
|
+
|
When Can You Tile an Integer Rectangle with Integer Squares?
|
2023
|
MIT CompGeom Group
Zachary Abel
Hugo A. Akitaya
Erik D. Demaine
Adam Hesterberg
Jayson Lynch
|
|
+
PDF
Chat
|
Characterizing the Decidability of Finite State Automata Team Games with Communication
|
2022
|
Michael Coulombe
Jayson Lynch
|
|
+
|
A neural network solves, explains, and generates university math problems by program synthesis and few-shot learning at human level
|
2022
|
Iddo Drori
Sarah Zhang
Reece Shuttleworth
Leonard Tang
Albert Lu
KE Elizabeth
Kevin Liu
Linda Chen
Sunny Tran
Newman Cheng
|
|
+
PDF
Chat
|
Trains, Games, and Complexity: 0/1/2-Player Motion Planning Through Input/Output Gadgets
|
2022
|
Joshua Ani
Erik D. Demaine
Dylan Hendrickson
Jayson Lynch
|
|
+
PDF
Chat
|
Traversability, Reconfiguration, and Reachability in the Gadget Framework
|
2022
|
Joshua Ani
Erik D. Demaine
Yevhenii Diomidov
Dylan Hendrickson
Jayson Lynch
|
|
+
|
The Legend of Zelda: The Complexity of Mechanics
|
2022
|
Jeffrey Bosboom
Josh Brunner
Michael Coulombe
Erik D. Demaine
Dylan Hendrickson
Jayson Lynch
Elle Najt
|
|
+
|
Reconfiguration of Non-crossing Spanning Trees
|
2022
|
Oswin Aichholzer
Brad Ballinger
Thérèse Biedl
Mirela Damian
Erik D. Demaine
Matias Korman
Anna Lubiw
Jayson Lynch
Josef Tkadlec
Yushi Uno
|
|
+
|
PSPACE-Completeness of Reversible Deterministic Systems
|
2022
|
Erik D. Demaine
Robert A. Hearn
Dylan Hendrickson
Jayson Lynch
|
|
+
PDF
Chat
|
PSPACE-Completeness of Reversible Deterministic Systems
|
2022
|
Erik D. Demaine
Robert A. Hearn
Dylan Hendrickson
Jayson Lynch
|
|
+
|
Lower Bounds on Retroactive Data Structures
|
2022
|
Lily Chung
Erik D. Demaine
Dylan Hendrickson
Jayson Lynch
|
|
+
|
Computational Complexity of Flattening Fixed-Angle Orthogonal Chains
|
2022
|
Erik D. Demaine
Hiro Ito
Jayson Lynch
Ryuhei Uehara
|
|
+
PDF
Chat
|
An Efficient Reversible Algorithm for Linear Regression
|
2021
|
Erik D. Demaine
Jayson Lynch
Jiaying Sun
|
|
+
|
The Computational Complexity of Finding Arithmetic Expressions With and Without Parentheses.
|
2021
|
Jayson Lynch
Yan Weng
|
|
+
|
Snipperclips: Cutting Tools into Desired Polygons using Themselves
|
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
|
|
+
PDF
Chat
|
Snipperclips: Cutting tools into desired polygons using themselves
|
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
|
|
+
|
Generalized LR-drawings of trees
|
2021
|
Thérèse Biedl
Giuseppe Liotta
Jayson Lynch
Fabrizio Montecchiani
|
|
+
PDF
Chat
|
Continuous flattening of all polyhedral manifolds using countably infinite creases
|
2021
|
Zachary Abel
Erik D. Demaine
Martin L. Demaine
Jason S. Ku
Jayson Lynch
Jin‐ichi Itoh
Chiê Nara
|
|
+
|
Hardness of Token Swapping on Trees.
|
2021
|
Oswin Aichholzer
Erik D. Demaine
Matias Korman
Jayson Lynch
Anna Lubiw
Zuzana Masárová
Mikhail Rudoy
Virginia Vassilevska Williams
Nicole Wein
|
|
+
|
Yin-Yang Puzzles are NP-complete
|
2021
|
Erik D. Demaine
Jayson Lynch
Mikhail Rudoy
Yushi Uno
|
|
+
|
Solving Machine Learning Problems
|
2021
|
Sunny Tran
Pranav Krishna
Ishan Pakuwal
Prabhakar Kafle
Nikhil Singh
Jayson Lynch
Iddo Drori
|
|
+
PDF
Chat
|
Optimal-Area Visibility Representations of Outer-1-Plane Graphs
|
2021
|
Thérèse Biedl
Giuseppe Liotta
Jayson Lynch
Fabrizio Montecchiani
|
|
+
|
Generalized LR-Drawings of Trees.
|
2021
|
Thérèse Biedl
Giuseppe Liotta
Jayson Lynch
Fabrizio Montecchiani
|
|
+
PDF
Chat
|
Negative Instance for the Edge Patrolling Beacon Problem
|
2021
|
Zachary Abel
Hugo A. Akitaya
Erik D. Demaine
Martin L. Demaine
Adam Hesterberg
Matias Korman
Jason S. Ku
Jayson Lynch
|
|
+
|
The Computational Complexity of Finding Arithmetic Expressions With and Without Parentheses
|
2021
|
Jayson Lynch
Yan
Weng
|
|
+
|
Multidimensional Scaling: Approximation and Complexity
|
2021
|
Erik D. Demaine
Adam Hesterberg
Frederic Koehler
Jayson Lynch
John Urschel
|
|
+
|
Optimal-area visibility representations of outer-1-plane graphs
|
2021
|
Thérèse Biedl
Giuseppe Liotta
Jayson Lynch
Fabrizio Montecchiani
|
|
+
|
Snipperclips: Cutting Tools into Desired Polygons using Themselves
|
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
|
|
+
|
Generalized LR-drawings of trees
|
2021
|
Thérèse Biedl
Giuseppe Liotta
Jayson Lynch
Fabrizio Montecchiani
|
|
+
|
Hardness of Token Swapping on Trees
|
2021
|
Oswin Aichholzer
Erik D. Demaine
Matias Korman
Jayson Lynch
Anna Lubiw
Zuzana Masárová
Mikhail Rudoy
Virginia Vassilevska Williams
Nicole Wein
|
|
+
|
An Efficient Reversible Algorithm for Linear Regression
|
2021
|
Erik D. Demaine
Jayson Lynch
Jiaying Sun
|
|
+
|
Characterizing Universal Reconfigurability of Modular Pivoting Robots
|
2020
|
Hugo A. Akitaya
Erik D. Demaine
Andrei Gonczi
Dylan Hendrickson
Adam Hesterberg
Matias Korman
Oliver Korten
Jayson Lynch
Irene Parada
Vera Sacristán
|
|
+
|
Tetris is NP-hard even with $O(1)$ rows or columns
|
2020
|
Sualeh Asif
Michael Coulombe
Erik D. Demaine
Martin L. Demaine
Adam Hesterberg
Jayson Lynch
Mihir Singhal
|
|
+
|
Escaping a Polygon.
|
2020
|
Zachary Abel
Hugo A. Akitaya
Erik D. Demaine
Martin L. Demaine
Adam Hesterberg
Jason S. Ku
Jayson Lynch
|
|
+
|
Who witnesses The Witness? Finding witnesses in The Witness is hard and sometimes impossible
|
2020
|
Zachary Abel
Jeffrey Bosboom
Michael Coulombe
Erik D. Demaine
Linus Hamilton
Adam Hesterberg
Justin Kopinsky
Jayson Lynch
Mikhail Rudoy
Clemens Thielen
|
|
+
|
PSPACE-completeness of Pulling Blocks to Reach a Goal
|
2020
|
Joshua Ani
Sualeh Asif
Erik D. Demaine
Yevhenii Diomidov
Dylan Hendrickson
Jayson Lynch
Sarah Scheffler
Adam Suhl
|
|
+
|
Walking through Doors is Hard, even without Staircases: Proving PSPACE-hardness via Planar Assemblies of Door Gadgets
|
2020
|
Joshua Ani
Jeffrey Bosboom
Erik D. Demaine
Yevhenii Diomidov
Dylan Hendrickson
Jayson Lynch
|
|
+
|
Negative Instance for the Edge Patrolling Beacon Problem
|
2020
|
Zachary Abel
Hugo A. Akitaya
Erik D. Demaine
Martin L. Demaine
Adam Hesterberg
Matias Korman
Jason S. Ku
Jayson Lynch
|
|
+
|
Recursed is not Recursive: A Jarring Result
|
2020
|
Erik D. Demaine
Justin Kopinsky
Jayson Lynch
|
|
+
|
Recursed Is Not Recursive: A Jarring Result
|
2020
|
Erik D. Demaine
Justin Kopinsky
Jayson Lynch
|
|
+
|
Tatamibari is NP-complete
|
2020
|
Aviv Adler
Jeffrey Bosboom
Erik D. Demaine
Martin L. Demaine
Quanquan C. Liu
Jayson Lynch
|
|
+
|
Walking Through Doors Is Hard, Even Without Staircases: Proving PSPACE-Hardness via Planar Assemblies of Door Gadgets.
|
2020
|
Joshua Ani
Jeffrey Bosboom
Erik D. Demaine
Yevhenii Diomidov
Dylan Hendrickson
Jayson Lynch
|
|
+
PDF
Chat
|
Mad Science is Provably Hard: Puzzles in Hearthstone's Boomsday Lab are NP-hard
|
2020
|
Michael M. Hoffmann
Jayson Lynch
Andrew Winslow
|
|
+
|
Arithmetic Expression Construction
|
2020
|
Leo Alcock
Sualeh Asif
Jeffrey Bosboom
Josh Brunner
Charlotte Chen
Erik D. Demaine
Rogers Epstein
Adam Hesterberg
Lior Hirschfeld
William Hu
|
|
+
PDF
Chat
|
PSPACE-completeness of Pulling Blocks to Reach a Goal
|
2020
|
Joshua Ani
Sualeh Asif
Erik D. Demaine
Yevhenii Diomidov
Dylan Hendrickson
Jayson Lynch
Sarah Scheffler
Adam Suhl
|
|
+
PDF
Chat
|
Tetris is NP-hard even with <i>O</i>(1) Rows or Columns
|
2020
|
Sualeh Asif
Michael Coulombe
Erik D. Demaine
Martin L. Demaine
Adam Hesterberg
Jayson Lynch
Mihir Singhal
|
|
+
|
Arithmetic Expression Construction.
|
2020
|
Leo Alcock
Sualeh Asif
Jeffrey Bosboom
Josh Brunner
Charlotte Chen
Erik D. Demaine
Rogers Epstein
Adam Hesterberg
Lior Hirschfeld
William Hu
|
|
+
|
Characterizing Universal Reconfigurability of Modular Pivoting Robots
|
2020
|
Hugo A. Akitaya
Erik D. Demaine
Andrei Gonczi
Dylan Hendrickson
Adam Hesterberg
Matias Korman
Oliver Korter
Jayson Lynch
Irene Parada
Vera Sacristán
|
|
+
|
Mad Science is Provably Hard: Puzzles in Hearthstone's Boomsday Lab are NP-hard
|
2020
|
Michael R. Hoffmann
Jayson Lynch
Andrew Winslow
|
|
+
|
Tetris is NP-hard even with $O(1)$ rows or columns
|
2020
|
Sualeh Asif
Michael Coulombe
Erik D. Demaine
Martin L. Demaine
Adam Hesterberg
Jayson Lynch
Mihir Singhal
|
|
+
|
Negative Instance for the Edge Patrolling Beacon Problem
|
2020
|
Zachary Abel
Hugo A. Akitaya
Erik D. Demaine
Martin L. Demaine
Adam Hesterberg
Matias Korman
Jason S. Ku
Jayson Lynch
|
|
+
|
Walking through Doors is Hard, even without Staircases: Proving PSPACE-hardness via Planar Assemblies of Door Gadgets
|
2020
|
Joshua Ani
Jeffrey Bosboom
Erik D. Demaine
Yevhenii Diomidov
Dylan Hendrickson
Jayson Lynch
|
|
+
|
Recursed is not Recursive: A Jarring Result
|
2020
|
Erik D. Demaine
Justin Kopinsky
Jayson Lynch
|
|
+
|
Escaping a Polygon
|
2020
|
Zachary Abel
Hugo A. Akitaya
Erik D. Demaine
Martin L. Demaine
Adam Hesterberg
Jason S. Ku
Jayson Lynch
|
|
+
|
Trains, Games, and Complexity: 0/1/2-Player Motion Planning through Input/Output Gadgets
|
2020
|
Joshua Ani
Erik D. Demaine
Dylan Hendrickson
Jayson Lynch
|
|
+
|
Data Races and the Discrete Resource-time Tradeoff Problem with Resource Reuse over Paths
|
2019
|
Rathish Das
Shih-Yu Tsai
Sharmila Duppala
Jayson Lynch
Esther M. Arkin
Rezaul Chowdhury
Joseph S. B. Mitchell
Steven Skiena
|
|
+
|
Hamiltonicity in Semi-Regular Tessellation Dual Graphs
|
2019
|
Divya Gopinath
Rohan Kodialam
Kevin W. Lu
Jayson Lynch
Santiago Ospina
|
|
+
|
A General Theory of Motion Planning Complexity: Characterizing Which Gadgets Make Games Hard.
|
2018
|
Erik D. Demaine
Dylan Hendrickson
Jayson Lynch
|
|
+
|
The Computational Complexity of Finding Hamiltonian Cycles in Grid Graphs of Semiregular Tessellations.
|
2018
|
Kaiying Hou
Jayson Lynch
|
|
+
|
Who witnesses The Witness? Finding witnesses in The Witness is hard and sometimes impossible
|
2018
|
Zachary Abel
Jeffrey Bosboom
Michael Coulombe
Erik D. Demaine
Linus Hamilton
Adam Hesterberg
Justin Kopinsky
Jayson Lynch
Mikhail Rudoy
Clemens Thielen
|
|
+
|
Computational Complexity of Motion Planning of a Robot through Simple Gadgets
|
2018
|
Erik D. Demaine
Isaac Grosof
Jayson Lynch
Mikhail Rudoy
|
|
+
|
Losing at Checkers is Hard
|
2018
|
Jeffrey Bosboom
Spencer Congero
Erik D. Demaine
Martin L. Demaine
Jayson Lynch
|
|
+
|
The Computational Complexity of Finding Hamiltonian Cycles in Grid Graphs of Semiregular Tessellations
|
2018
|
Kaiying Hou
Jayson Lynch
|
|
+
|
Fine-grained I/O Complexity via Reductions: New Lower Bounds, Faster Algorithms, and a Time Hierarchy
|
2018
|
Erik D. Demaine
Andrea Lincoln
Quanquan C. Liu
Jayson Lynch
Virginia Vassilevska Williams
|
|
+
|
Who witnesses The Witness? Finding witnesses in The Witness is hard and sometimes impossible
|
2018
|
Zachary Abel
Jeffrey Bosboom
Michael Coulombe
Erik D. Demaine
Linus Hamilton
Adam Hesterberg
Justin Kopinsky
Jayson Lynch
Mikhail Rudoy
Clemens Thielen
|
|
+
|
Cookie Clicker
|
2018
|
Erik D. Demaine
Hiro Ito
Stefan Langerman
Jayson Lynch
Mikhail Rudoy
Kai Xiao
|
|
+
|
Toward a General Theory of Motion Planning Complexity: Characterizing Which Gadgets Make Games Hard
|
2018
|
Erik D. Demaine
Dylan Hendrickson
Jayson Lynch
|
|
+
|
Minimal forcing sets for 1D origami
|
2017
|
Mirela Damian
Erik D. Demaine
Muriel Dulieu
Robin Flatland
Hella Hoffmann
Thomas C. Hull
Jayson Lynch
Suneeta Ramaswami
|
|
+
|
Push-Pull Block Puzzles are Hard
|
2017
|
Erik D. Demaine
Isaac Grosof
Jayson Lynch
|
|
+
PDF
Chat
|
Unfolding and Dissection of Multiple Cubes, Tetrahedra, and Doubly Covered Squares
|
2017
|
Zachary Abel
Brad Ballinger
Erik D. Demaine
Martin L. Demaine
Jeff Erickson
Adam Hesterberg
Hiro Ito
Irina Kostitsyna
Jayson Lynch
Ryuhei Uehara
|
|
+
|
Fine-Grained I/O Complexity via Reductions: New lower bounds, faster algorithms, and a time hierarchy
|
2017
|
Erik D. Demaine
Andrea Lincoln
Quanquan C. Liu
Jayson Lynch
Virginia Vassilevska Williams
|
|
+
PDF
Chat
|
Push-Pull Block Puzzles are Hard
|
2017
|
Erik D. Demaine
Isaac Grosof
Jayson Lynch
|
|
+
|
The Computational Complexity of Portal and Other 3D Video Games
|
2016
|
Erik D. Demaine
Joshua Lockhart
Jayson Lynch
|
|
+
|
Toward an Energy Efficient Language and Compiler for (Partially) Reversible Algorithms
|
2016
|
Nirvan Tyagi
Jayson Lynch
Erik D. Demaine
|
|
+
|
Energy-Efficient Algorithms
|
2016
|
Erik D. Demaine
Jayson Lynch
Geronimo J. Mirano
Nirvan Tyagi
|
|
+
PDF
Chat
|
Energy-Efficient Algorithms
|
2016
|
Erik D. Demaine
Jayson Lynch
Geronimo J. Mirano
Nirvan Tyagi
|
|
+
PDF
Chat
|
Toward an Energy Efficient Language and Compiler for (Partially) Reversible Algorithms
|
2016
|
Nirvan Tyagi
Jayson Lynch
Erik D. Demaine
|
|
+
|
The Computational Complexity of Portal and Other 3D Video Games
|
2016
|
Erik D. Demaine
Joshua Lockhart
Jayson Lynch
|
|
+
|
Toward an Energy Efficient Language and Compiler for (Partially) Reversible Algorithms
|
2016
|
Nirvan Tyagi
Jayson Lynch
Erik D. Demaine
|
|
+
|
Energy-Efficient Algorithms
|
2016
|
Erik D. Demaine
Jayson Lynch
Geronimo J. Mirano
Nirvan Tyagi
|
|
+
|
Pachinko
|
2016
|
Hugo A. Akitaya
Erik D. Demaine
Martin L. Demaine
Adam Hesterberg
Ferrán Hurtado
Jason S. Ku
Jayson Lynch
|
|
+
|
Improved Connectivity Condition for Byzantine Fault Tolerance
|
2015
|
Adam Hesterberg
Andrea Lincoln
Jayson Lynch
|
|
+
|
Dissection with the Fewest Pieces is Hard, Even to Approximate
|
2015
|
Jeffrey Bosboom
Erik D. Demaine
Martin L. Demaine
Jayson Lynch
Pasin Manurangsi
Mikhail Rudoy
Anak Yodpinyanee
|
|
+
|
Improved Connectivity Condition for Byzantine Fault Tolerance
|
2015
|
Adam Hesterberg
Andrea Lincoln
Jayson Lynch
|