Publications (75)
Complexity of Solo Chess with Unlimited Moves
Josh Brunner, Lily Chung, Michael Coulombe +3
We analyze Solo Chess puzzles, where the input is an board containing some standard Chess pieces of the same color, and the goal is to make a sequence of capture moves…
A Neural Network Solves, Explains, and Generates University Math Problems by Program Synthesis and Few-Shot Learning at Human Level
Iddo Drori, Sarah Zhang, Reece Shuttleworth +15
We demonstrate that a neural network pre-trained on text and fine-tuned on code solves mathematics course problems, explains solutions, and generates new questions at a human level…
Deltahedral Domes over Equiangular Polygons
MIT CompGeom Group, Hugo A. Akitaya, Erik D. Demaine +6
A polyiamond is a polygon composed of unit equilateral triangles, and a generalized deltahedron is a convex polyhedron whose every face is a convex polyiamond. We study a variant w…
Two AI Metrics Diverged: Will it Make All the Difference?
Alex Fogelson, Zachary A. Brown, Hans Gundlach +2
As exponential compute scaling continues, will the capabilities of frontier AI models outstrip what is accessible to developers on a small fixed budget? Or will capabilities conver…
Negative Instance for the Edge Patrolling Beacon Problem
Zachary Abel, Hugo A. Akitaya, Erik D. Demaine +5
Can an infinite-strength magnetic beacon always ``catch'' an iron ball, when the beacon is a point required to be remain nonstrictly outside a polygon, and the ball is a point alwa…
The Impact of Approximation on Algorithmic Progress
Jeffery Li, Jayson Lynch, Liva Olina +3
In nearly every discipline, scientific computations are limited by the cost and speed of computation. For example, the best-known exact algorithms for the canonical Traveling Sales…
Complexity of Motion Planning of Arbitrarily Many Robots: Gadgets, Petri Nets, and Counter Machines
Hayashi Ani, Michael Coulombe, Erik D. Demaine +4
We extend the motion-planning-through-gadgets framework to several new scenarios involving various numbers of robots/agents, and analyze the complexity of the resulting motion-plan…
Arithmetic Expression Construction
Leo Alcock, Sualeh Asif, Jeffrey Bosboom +10
When can given numbers be combined using arithmetic operators from a given subset of to obtain a given target number? We study three variations of this p…
Generalized LR-drawings of trees
Therese Biedl, Giuseppe Liotta, Jayson Lynch +1
The LR-drawing-method is a method of drawing an ordered rooted binary tree based on drawing one root-to-leaf path on a vertical line and attaching recursively obtained drawings of…
Hardness of Token Swapping on Trees
Oswin Aichholzer, Erik D. Demaine, Matias Korman +6
Given a graph where every vertex has exactly one labeled token, how can we most quickly execute a given permutation on the tokens? In (sequential) token swapping, the goal is to us…
Slant/Gokigen Naname is NP-complete, and Some Variations are in P
Jayson Lynch, Jack Spalding-Jamieson
In this paper we show that a generalized version of the Nikoli puzzle Slant is NP-complete. We also give polynomial time algorithms for versions of the puzzle where some constraint…
Humanity's Last Exam
Long Phan, Alice Gatti, Ziwen Han +1144
Benchmarks are important tools for tracking the rapid advancements in large language model (LLM) capabilities. However, benchmarks are not keeping pace in difficulty: LLMs now achi…
This Game Is Not Going To Analyze Itself
Aviv Adler, Hayashi Ani, Lily Chung +5
We analyze the puzzle video game This Game Is Not Going To Load Itself, where the player routes data packets of three different colors from given sources to given sinks of the corr…
Quasigeodesics on the Cube
MIT CompGeom Group, Hugo A. Akitaya, Erik D. Demaine +10
A quasigeodesic is a curve on the surface of a convex polyhedron that has surface to each side at every point. In contrast, a geodesic has exactly to each side and so…
Characterizing the Decidability of Finite State Automata Team Games with Communication
Michael Coulombe, Jayson Lynch
In this paper we define a new model of limited communication for multiplayer team games of imperfect information. We prove that the Team DFA Game and Team Formula Game, which have…
Who witnesses The Witness? Finding witnesses in The Witness is hard and sometimes impossible
Zachary Abel, Jeffrey Bosboom, Michael Coulombe +7
We analyze the computational complexity of the many types of pencil-and-paper-style puzzles featured in the 2016 puzzle video game The Witness. In all puzzles, the goal is to draw…
Introducing the Quantum Economic Advantage Online Calculator
Frederick Mejia, Hans Gundlach, Jayson Lynch +5
Developing a systematic view of where quantum computers will outperform classical ones is important for researchers, policy makers and business leaders. But developing such a view…
Optimal-area visibility representations of outer-1-plane graphs
Therese Biedl, Giuseppe Liotta, Jayson Lynch +1
This paper studies optimal-area visibility representations of -vertex outer-1-plane graphs, i.e. graphs with a given embedding where all vertices are on the boundary of the oute…
Who Needs Crossings?: Noncrossing Linkages are Universal, and Deciding (Global) Rigidity is Hard
Zachary Abel, Erik D. Demaine, Martin L. Demaine +3
We exactly settle the complexity of graph realization, graph rigidity, and graph global rigidity as applied to three types of graphs: "globally noncrossing" graphs, which avoid cro…
Trains, Games, and Complexity: 0/1/2-Player Motion Planning through Input/Output Gadgets
Hayashi Ani, Erik D. Demaine, Dylan H. Hendrickson +1
We analyze the computational complexity of motion planning through local "input/output" gadgets with separate entrances and exits, and a subset of allowed traversals from entrances…
Subquadratic Approximation Algorithms for Separating Two Points with Objects in the Plane
Jayson Lynch, Jack Spalding-Jamieson
The (unweighted) point-separation problem asks, given a pair of points and in the plane, and a set of candidate geometric objects, for the minimum-size subset of objects wh…
Solving Machine Learning Problems
Sunny Tran, Pranav Krishna, Ishan Pakuwal +4
Can a machine learn Machine Learning? This work trains a machine learning model to solve machine learning problems from a University undergraduate level course. We generate a new t…
Data Races and the Discrete Resource-time Tradeoff Problem with Resource Reuse over Paths
Rathish Das, Shih-Yu Tsai, Sharmila Duppala +5
A determinacy race occurs if two or more logically parallel instructions access the same memory location and at least one of them tries to modify its content. Races often lead to n…
Recursed is not Recursive: A Jarring Result
Erik Demaine, Justin Kopinsky, Jayson Lynch
Recursed is a 2D puzzle platform video game featuring treasure chests that, when jumped into, instantiate a room that can later be exited (similar to function calls), optionally ge…
Yin-Yang Puzzles are NP-complete
Erik D. Demaine, Jayson Lynch, Mikhail Rudoy +1
We prove NP-completeness of Yin-Yang / Shiromaru-Kuromaru pencil-and-paper puzzles. Viewed as a graph partitioning problem, we prove NP-completeness of partitioning a rectangular g…
Lower Bounds on Retroactive Data Structures
Lily Chung, Erik D. Demaine, Dylan Hendrickson +1
We prove essentially optimal fine-grained lower bounds on the gap between a data structure and a partially retroactive version of the same data structure. Precisely, assuming any o…
PSPACE-completeness of Pulling Blocks to Reach a Goal
Hayashi Ani, Sualeh Asif, Erik D. Demaine +5
We prove PSPACE-completeness of all but one problem in a large space of pulling-block problems where the goal is for the agent to reach a target destination. The problems are param…
Hamiltonicity in Semi-Regular Tessellation Dual Graphs
Divya Gopinath, Rohan Kodialam, Kevin Lu +2
This paper shows NP-completeness for finding Hamiltonian cycles in induced subgraphs of the dual graphs of semi-regular tessilations. It also shows NP-hardness for a new, wide clas…
Folding One Polyhedral Metric Graph into Another
Lily Chung, Erik D. Demaine, Martin L. Demaine +4
We analyze the problem of folding one polyhedron, viewed as a metric graph of its edges, into the shape of another, similar to 1D origami. We find such foldings between all pairs o…
Quantum Deep Learning Still Needs a Quantum Leap
Hans Gundlach, Hrvoje Kukina, Jayson Lynch +1
Quantum computing technology is advancing rapidly. Yet, even accounting for these trends, a quantum leap would be needed for quantum computers to meaningfully impact deep learning…
Toward an Energy Efficient Language and Compiler for (Partially) Reversible Algorithms
Nirvan Tyagi, Jayson Lynch, Erik D. Demaine
We introduce a new programming language for expressing reversibility, Energy-Efficient Language (Eel), geared toward algorithm design and implementation. Eel is the first language…
Minimal forcing sets for 1D origami
Mirela Damian, Erik Demaine, Muriel Dulieu +5
This paper addresses the problem of finding minimum forcing sets in origami. The origami material folds flat along straight lines called creases that can be labeled as mountains or…
All Polyhedral Manifolds are Connected by a 2-Step Refolding
Lily Chung, Erik D. Demaine, Jenny Diomidova +4
We prove that, for any two polyhedral manifolds , there is a polyhedral manifold such that share a common unfolding and…
Pushing Blocks without Fixed Walls via Checkable Gizmos: Push-1 is PSPACE-Complete
MIT Hardness Group, Josh Brunner, Lily Chung +4
We prove PSPACE-completeness of Push-1: given a rectangular grid of 1 x 1 cells, each possibly occupied by a movable block, can a robot move from one specified location to another,…
Escaping a Polygon
Zachary Abel, Hugo Akitaya, Erik D. Demaine +4
Suppose an escaping player ("human") moves continuously at maximum speed in the interior of a region, while a pursuing player ("zombie") moves continuously at maximum speed …
Dissection with the Fewest Pieces is Hard, Even to Approximate
Jeffrey Bosboom, Erik D. Demaine, Martin L. Demaine +4
We prove that it is NP-hard to dissect one simple orthogonal polygon into another using a given number of pieces, as is approximating the fewest pieces to within a factor of $1+1/1…
Multidimensional Scaling: Approximation and Complexity
Erik Demaine, Adam Hesterberg, Frederic Koehler +2
Metric Multidimensional scaling (MDS) is a classical method for generating meaningful (non-linear) low-dimensional embeddings of high-dimensional data. MDS has a long history in th…
Toward a General Theory of Motion Planning Complexity: Characterizing Which Gadgets Make Games Hard
Erik D. Demaine, Dylan H. Hendrickson, Jayson Lynch
We build a general theory for characterizing the computational complexity of motion planning of robot(s) through a graph of "gadgets", where each gadget has its own state defining…
Tetris is NP-hard even with rows or columns
Sualeh Asif, Michael Coulombe, Erik D. Demaine +4
We prove that the classic falling-block video game Tetris (both survival and board clearing) remains NP-complete even when restricted to 8 columns, or to 4 rows, settling open prob…
Complexity of Reconfiguration in Surface Chemical Reaction Networks
Robert M. Alaniz, Josh Brunner, Michael Coulombe +9
We analyze the computational complexity of basic reconfiguration problems for the recently introduced surface Chemical Reaction Networks (sCRNs), where ordered pairs of adjacent sp…
The Legend of Zelda: The Complexity of Mechanics
Jeffrey Bosboom, Josh Brunner, Michael Coulombe +4
We analyze some of the many game mechanics available to Link in the classic Legend of Zelda series of video games. In each case, we prove that the generalized game with that mechan…
Tatamibari is NP-complete
Aviv Adler, Jeffrey Bosboom, Erik D. Demaine +3
In the Nikoli pencil-and-paper game Tatamibari, a puzzle consists of an grid of cells, where each cell possibly contains a clue among +, -, |. The goal is to partition…
Energy-Efficient Algorithms
Erik D. Demaine, Jayson Lynch, Geronimo J. Mirano +1
We initiate the systematic study of the energy complexity of algorithms (in addition to time and space complexity) based on Landauer's Principle in physics, which gives a lower bou…
Pachinko
Hugo A. Akitaya, Erik D. Demaine, Martin L. Demaine +4
Inspired by the Japanese game Pachinko, we study simple (perfectly "inelastic" collisions) dynamics of a unit ball falling amidst point obstacles (pins) in the plane. A classic exa…
Reconfiguration of Non-crossing Spanning Trees
Oswin Aichholzer, Brad Ballinger, Therese Biedl +7
For a set of points in the plane in general position, a non-crossing spanning tree is a spanning tree of the points where every edge is a straight-line segment between a pa…
EnigmaEval: A Benchmark of Long Multimodal Reasoning Challenges
Clinton J. Wang, Dean Lee, Cristina Menghini +7
As language models master existing reasoning benchmarks, we need new challenges to evaluate their cognitive frontiers. Puzzle-solving events are rich repositories of challenging mu…
Continuous Flattening of All Polyhedral Manifolds using Countably Infinite Creases
Zachary Abel, Erik D. Demaine, Martin L. Demaine +4
We prove that any finite polyhedral manifold in 3D can be continuously flattened into 2D while preserving intrinsic distances and avoiding crossings, answering a 19-year-old open p…
Cookie Clicker
Erik D. Demaine, Hiro Ito, Stefan Langerman +3
Cookie Clicker is a popular online incremental game where the goal of the game is to generate as many cookies as possible. In the game you start with an initial cookie generation r…
Improved Connectivity Condition for Byzantine Fault Tolerance
Adam Hesterberg, Andrea Lincoln, Jayson Lynch
Given a network in which some pairs of nodes can communicate freely, and some subsets of the nodes could be faulty and colluding to disrupt communication, when can messages reliabl…
The Price of Progress: Price Performance and the Future of AI
Hans Gundlach, Jayson Lynch, Matthias Mertens +1
Language models have seen enormous progress on advanced benchmarks in recent years, but much of this progress has only been possible by using more costly models. Benchmarks may the…
Push-Pull Block Puzzles are Hard
Erik D. Demaine, Isaac Grosof, Jayson Lynch
This paper proves that push-pull block puzzles in 3D are PSPACE-complete to solve, and push-pull block puzzles in 2D with thin walls are NP-hard to solve, settling an open question…
Characterizing Universal Reconfigurability of Modular Pivoting Robots
Hugo A. Akitaya, Erik D. Demaine, Andrei Gonczi +7
We give both efficient algorithms and hardness results for reconfiguring between two connected configurations of modules in the hexagonal grid. The reconfiguration moves that we co…
Computational Complexity of Flattening Fixed-Angle Orthogonal Chains
Erik D. Demaine, Hiro Ito, Jayson Lynch +1
Planar/flat configurations of fixed-angle chains and trees are well studied in the context of polymer science, molecular biology, and puzzles. In this paper, we focus on a simple t…
Mad Science is Provably Hard: Puzzles in Hearthstone's Boomsday Lab are NP-hard
Michael Hoffmann, Jayson Lynch, Andrew Winslow
We consider the computational complexity of winning this turn (mate-in-1 or "finding lethal") in Hearthstone as well as several other single turn puzzle types introduced in the Boo…
EvilGenie: A Reward Hacking Benchmark
Jonathan Gabor, Jayson Lynch, Jonathan Rosenfeld
We introduce EvilGenie, a benchmark for reward hacking in programming settings. We source problems from LiveCodeBench and create an environment in which agents can easily reward ha…
How fast are algorithms reducing the demands on memory? A survey of progress in space complexity
Hayden Rome, Jayson Lynch, Jeffery Li +2
Algorithm research focuses primarily on how many operations processors need to do (time complexity). But for many problems, both the runtime and energy used are dominated by memory…
Super Guarding and Dark Rays in Art Galleries
MIT CompGeom Group, Hugo A. Akitaya, Erik D. Demaine +5
We explore an Art Gallery variant where each point of a polygon must be seen by k guards, and guards cannot see through other guards. Surprisingly, even covering convex polygons un…
Traversability, Reconfiguration, and Reachability in the Gadget Framework
Hayashi Ani, Erik Demaine, Jenny Diomidova +2
Consider an agent traversing a graph of "gadgets", each with local state that changes with each traversal by the agent. We characterize the complexity of universal traversal, where…
The Computational Complexity of Finding Arithmetic Expressions With and Without Parentheses
Jayson Lynch, Yan, Weng
We show NP-completeness for various problems about the existence of arithmetic expression trees. When given a set of operations, inputs, and a target value does there exist an expr…
Walking through Doors is Hard, even without Staircases: Universality and PSPACE-hardness of Planar Door Gadgets
MIT Gadgets Group, Jeffrey Bosboom, Erik D. Demaine +4
An open-close door gadget has two states and three tunnels that can be traversed by an agent (player, robot, etc.): the "opening" and "closing" tunnels set the gadget's state to op…
The Computational Complexity of Portal and Other 3D Video Games
Erik D. Demaine, Joshua Lockhart, Jayson Lynch
We classify the computational complexity of the popular video games Portal and Portal 2. We isolate individual mechanics of the game and prove NP-hardness, PSPACE-completeness, or…
Computational Complexity of Motion Planning of a Robot through Simple Gadgets
Erik D. Demaine, Isaac Grosof, Jayson Lynch +1
We initiate a general theory for analyzing the complexity of motion planning of a single robot through a graph of "gadgets", each with their own state, set of locations, and allowe…
Fine-Grained I/O Complexity via Reductions: New lower bounds, faster algorithms, and a time hierarchy
Erik D. Demaine, Andrea Lincoln, Quanquan C. Liu +2
This paper initiates the study of I/O algorithms (minimizing cache misses) from the perspective of fine-grained complexity (conditional polynomial lower bounds). Specifically, we a…
The Computational Complexity of Finding Hamiltonian Cycles in Grid Graphs of Semiregular Tessellations
Kaiying Hou, Jayson Lynch
Finding Hamitonian Cycles in square grid graphs is a well studied and important questions. More recent work has extended these results to triangular and hexagonal grids, as well as…
An Efficient Reversible Algorithm for Linear Regression
Erik D. Demaine, Jayson Lynch, Jiaying Sun
This paper presents an efficient reversible algorithm for linear regression, both with and without ridge regression. Our reversible algorithm matches the asymptotic time and space…
Pushing Blocks via Checkable Gadgets: PSPACE-completeness of Push-1F and Block/Box Dude
Hayashi Ani, Lily Chung, Erik D. Demaine +3
We prove PSPACE-completeness of the well-studied pushing-block puzzle Push-1F, a theoretical abstraction of many video games (introduced in 1999). The proof also extends to Push-$k…
Meek Models Shall Inherit the Earth
Hans Gundlach, Jayson Lynch, Neil Thompson
The past decade has seen incredible scaling of AI systems by a few companies, leading to inequality in AI model performance. This paper argues that, contrary to prevailing intuitio…
Snipperclips: Cutting Tools into Desired Polygons using Themselves
Zachary Abel, Hugo Akitaya, Man-Kwun Chiu +7
We study Snipperclips, a computer puzzle game whose objective is to create a target shape with two tools. The tools start as constant-complexity shapes, and each tool can snip (i.e…
Undecidability of Tiling with a Tromino
ULB CompGeom Group, Zachary Abel, Hugo Akitaya +6
Given a periodic placement of copies of a tromino (either L or I), we prove co-RE-completeness (and hence undecidability) of deciding whether it can be completed to a plane tiling.…
All Polyhedral Manifolds are Connected by a 2-Step Refolding
Lily Chung, Erik D. Demaine, Jenny Diomidova +4
We prove that, for any two polyhedral manifolds , there is a polyhedral manifold such that share a common unfolding an…
Quantum Advantage in Computational Chemistry?
Hans Gundlach, Keeper Sharkey, Jayson Lynch +8
For decades, computational chemistry has been posited as one of the areas in which quantum computing would revolutionize. However, the algorithmic advantages that fault-tolerant qu…
Losing at Checkers is Hard
Jeffrey Bosboom, Spencer Congero, Erik D. Demaine +2
We prove computational intractability of variants of checkers: (1) deciding whether there is a move that forces the other player to win in one move is NP-complete; (2) checkers whe…
On the Origin of Algorithmic Progress in AI
Hans Gundlach, Alex Fogelson, Jayson Lynch +4
Algorithms have been estimated to increase AI training FLOP efficiency by a factor of 22,000 between 2012 and 2023 [Ho et al., 2024]. Running small-scale ablation experiments on ke…
PSPACE-Completeness of Reversible Deterministic Systems
Erik D. Demaine, Robert A. Hearn, Dylan Hendrickson +1
We prove PSPACE-completeness of several reversible, fully deterministic systems. At the core, we develop a framework for such proofs (building on a result of Tsukiji and Hagiwara a…
When Can You Tile an Integer Rectangle with Integer Squares?
MIT CompGeom Group, Zachary Abel, Hugo A. Akitaya +3
This paper characterizes when an rectangle, where and are integers, can be tiled (exactly packed) by squares where each has an integer side length of at least…