2 citations · 2 across the 12 of their papers we have counts for
3 papers · 1 filter
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…