4 citations · 10 across the 13 of their papers we have counts for
6 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…
PSPACE-Completeness of Reversible Deterministic Systems
Erik D. Demaine, Robert A. Hearn, Dylan Hendrickson +1
We prove PSPACE-completeness of several reversible, fully deterministic systems. At the core, we develop a framework for such proofs (building on a result of Tsukiji and Hagiwara a…
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…
Traversability, Reconfiguration, and Reachability in the Gadget Framework
Hayashi Ani, Erik Demaine, Jenny Diomidova +2
Consider an agent traversing a graph of "gadgets", each with local state that changes with each traversal by the agent. We characterize the complexity of universal traversal, where…
The Legend of Zelda: The Complexity of Mechanics
Jeffrey Bosboom, Josh Brunner, Michael Coulombe +4
We analyze some of the many game mechanics available to Link in the classic Legend of Zelda series of video games. In each case, we prove that the generalized game with that mechan…
Orthogonal Fold & Cut
Hayashi Ani, Josh Brunner, Erik D. Demaine +4
We characterize the cut patterns that can be produced by "orthogonal fold & cut": folding an axis-aligned rectangular sheet of paper along horizontal and vertical creases, and then…