| No. |
Title |
Author |
Year |
| 1 |
Complexity of Motion Planning of Arbitrarily Many Robots: Gadgets, Petri Nets, and Counter Machines |
Ani, Joshua et al. |
2023 |
| 2 |
Complexity of Reconfiguration in Surface Chemical Reaction Networks |
Alaniz, Robert M. et al. |
2023 |
| 3 |
Hardness of Token Swapping on Trees |
Aichholzer, Oswin et al. |
2022 |
| 4 |
Lower Bounds on Retroactive Data Structures |
Chung, Lily et al. |
2022 |
| 5 |
Pushing Blocks via Checkable Gadgets: PSPACE-Completeness of Push-1F and Block/Box Dude |
Ani, Joshua et al. |
2022 |
| 6 |
Characterizing Universal Reconfigurability of Modular Pivoting Robots |
A. Akitaya, Hugo et al. |
2021 |
| 7 |
Dynamic Boolean Formula Evaluation |
Das, Rathish et al. |
2021 |
| 8 |
Arithmetic Expression Construction |
Alcock, Leo et al. |
2020 |
| 9 |
Recursed Is Not Recursive: A Jarring Result |
Demaine, Erik D. et al. |
2020 |
| 10 |
Tatamibari Is NP-Complete |
Adler, Aviv et al. |
2020 |
| 11 |
Toward a General Complexity Theory of Motion Planning: Characterizing Which Gadgets Make Games Hard |
Demaine, Erik D. et al. |
2020 |
| 12 |
Walking Through Doors Is Hard, Even Without Staircases: Proving PSPACE-Hardness via Planar Assemblies of Door Gadgets |
Ani, Joshua et al. |
2020 |
| 13 |
Computational Complexity of Motion Planning of a Robot through Simple Gadgets |
Demaine, Erik D. et al. |
2018 |
| 14 |
Cooperating in Video Games? Impossible! Undecidability of Team Multiplayer Games |
Coulombe, Michael J. et al. |
2018 |
| 15 |
Fine-grained I/O Complexity via Reductions: New Lower Bounds, Faster Algorithms, and a Time Hierarchy |
Demaine, Erik D. et al. |
2018 |
| 16 |
The Computational Complexity of Portal and Other 3D Video Games |
Demaine, Erik D. et al. |
2018 |
| 17 |
Who witnesses The Witness? Finding witnesses in The Witness is hard and sometimes impossible |
Abel, Zachary et al. |
2018 |
| 18 |
Who Needs Crossings? Hardness of Plane Graph Rigidity |
Abel, Zachary et al. |
2016 |
