2 citations · 2 across the 12 of their papers we have counts for
16 papers
Streaming Algorithms for Monotonicity Testing
Amir Azarmehr, Soheil Behnezhad, Lily Chung +3
Consider a poset - or equivalently an -vertex DAG - and a boolean function on its vertex set. We say is monotone if f…
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.…
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,…
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…
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…
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…
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…
ASP-Completeness of Hamiltonicity in Grid Graphs, with Applications to Loop Puzzles
MIT Hardness Group, Josh Brunner, Lily Chung +4
We prove that Hamiltonicity in maximum-degree-3 grid graphs (directed or undirected) is ASP-complete, i.e., it has a parsimonious reduction from every NP search problem (including…
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…
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…
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…
Celeste is PSPACE-hard
Lily Chung, Erik D. Demaine
We investigate the complexity of the platform video game Celeste. We prove that navigating Celeste is PSPACE-hard in five different ways, corresponding to different subsets of the…
Flat Folding an Unassigned Single-Vertex Complex (Combinatorially Embedded Planar Graph with Specified Edge Lengths) without Flat Angles
Lily Chung, Erik D. Demaine, Dylan Hendrickson +1
A foundational result in origami mathematics is Kawasaki and Justin's simple, efficient characterization of flat foldability for unassigned single-vertex crease patterns (where eac…
Improved Local Computation Algorithms for Constructing Spanners
Rubi Arviv, Lily Chung, Reut Levi +1
A spanner of a graph is a subgraph that preserves lengths of shortest paths up to a multiplicative distortion. For every , a spanner with size and stretch $(2k+1)…
1 x 1 Rush Hour with Fixed Blocks is PSPACE-complete
Josh Brunner, Lily Chung, Erik D. Demaine +4
Consider unit-square blocks in an square board, where each block is labeled as movable horizontally (only), movable vertically (only), or immovable -- a variat…
Edge Matching with Inequalities, Triangles, Unknown Shape, and Two Players
Jeffrey Bosboom, Charlotte Chen, Lily Chung +12
We analyze the computational complexity of several new variants of edge-matching puzzles. First we analyze inequality (instead of equality) constraints between adjacent tiles, prov…