Lily Chung
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Interests
Lily Chung has a total of 5 co-authors. Here are the top co-authors by number of shared publications:
- Dylan Hendrickson
MIT Computer Science and Artificial Intelligence Laboratory 32 Vassar St. 02139 Cambridge MA USA
1 shared publication - Erik D. Demaine
Computer Science and Artificial Intelligence Laboratory, MIT, Cambridge, MA, USA
1 shared publication - Jayson Lynch
Massachusetts Institute of Technology
1 shared publication Jenny Diomidova
Computer Science and Artificial Intelligence Laboratory, MIT, Cambridge, MA, USA
1 shared publication- Josh Brunner
Computer Science and Artificial Intelligence Laboratory, MIT, Cambridge, MA, USA
1 shared publication
Latest Publications
- 1 August 2026
- Published by SAGE Publications in ICGA Journal: The Journal of the Computer Games Community
- Vol. 48 (3) , 86-114
Pushing Blocks Without Fixed Walls Via Checkable Gizmos: Push-1 Is PSPACE-Complete
We prove PSPACE -completeness of Push-1: given a rectangular grid of 1 × 1 cells, each possibly occupied by a movable block, can a robot move from one specified location to another, given the ability to push up to one block at a time? In particular, we remove the need for fixed (immovable) walls from a 2022 result. This fundamental model of block pushing, introduced in 1999, abstracts the mechanics of many video games. It was shown NP -hard in 2000, but its final complexity remained open for 25 years. Our result uses a new framework for checkable gadgets/gizmos, extending a prior framework for checkable gadgets to handle reconfiguration problems, at the cost of requiring a stronger auxiliary gadget. We also introduce a new connection between the motion-planning-through-gadgets framework (with an agent) and the Graph Orientation Reconfiguration Problem (with no agent), including Nondeterministic Constraint Logic.
- 1 August 2026
- Published by SAGE Publications in ICGA Journal: The Journal of the Computer Games Community
- Vol. 48 (3) , 86-114
Pushing Blocks Without Fixed Walls Via Checkable Gizmos: Push-1 Is PSPACE-Complete
We prove PSPACE -completeness of Push-1: given a rectangular grid of 1 × 1 cells, each possibly occupied by a movable block, can a robot move from one specified location to another, given the ability to push up to one block at a time? In particular, we remove the need for fixed (immovable) walls from a 2022 result. This fundamental model of block pushing, introduced in 1999, abstracts the mechanics of many video games. It was shown NP -hard in 2000, but its final complexity remained open for 25 years. Our result uses a new framework for checkable gadgets/gizmos, extending a prior framework for checkable gadgets to handle reconfiguration problems, at the cost of requiring a stronger auxiliary gadget. We also introduce a new connection between the motion-planning-through-gadgets framework (with an agent) and the Graph Orientation Reconfiguration Problem (with no agent), including Nondeterministic Constraint Logic.