research
∙
06/01/2023
Complexity of Motion Planning of Arbitrarily Many Robots: Gadgets, Petri Nets, and Counter Machines
We extend the motion-planning-through-gadgets framework to several new s...
share
research
∙
06/01/2023
Complexity of Simple Folding of Mixed Orthogonal Crease Patterns
Continuing results from JCDCGGG 2016 and 2017, we solve several new case...
research
∙
02/02/2023
This Game Is Not Going To Analyze Itself
We analyze the puzzle video game This Game Is Not Going To Load Itself, ...
research
∙
11/26/2022
Lower Bounds on Retroactive Data Structures
We prove essentially optimal fine-grained lower bounds on the gap betwee...
research
∙
07/14/2022
PSPACE-Completeness of Reversible Deterministic Systems
We prove PSPACE-completeness of several reversible, fully deterministic ...
research
∙
04/07/2022
Flat Folding an Unassigned Single-Vertex Complex (Combinatorially Embedded Planar Graph with Specified Edge Lengths) without Flat Angles
A foundational result in origami mathematics is Kawasaki and Justin's si...
research
∙
04/01/2022
Traversability, Reconfiguration, and Reachability in the Gadget Framework
Consider an agent traversing a graph of "gadgets", each with local state...
research
∙
02/02/2022
Orthogonal Fold Cut
We characterize the shapes that can be produced by "orthogonal fold ...
research
∙
10/19/2020
Complexity of Retrograde and Helpmate Chess Problems: Even Cooperative Chess is Hard
We prove PSPACE-completeness of two classic types of Chess problems when...
research
∙
06/08/2020
PSPACE-completeness of Pulling Blocks to Reach a Goal
We prove PSPACE-completeness of all but one problem in a large space of ...
research
∙
06/01/2020
Walking through Doors is Hard, even without Staircases: Proving PSPACE-hardness via Planar Assemblies of Door Gadgets
A door gadget has two states and three tunnels that can be traversed by ...
research
∙
03/22/2020
1 x 1 Rush Hour with Fixed Blocks is PSPACE-complete
Consider n^2-1 unit-square blocks in an n × n square board, where each b...
research
∙
02/10/2020