59 citations · 74 across the 8 of their papers we have counts for
8 papers
Two-Disk Compound Symmetry Groups
Robert A. Hearn, William Kretschmer, Tomas Rokicki +2
Symmetry is at the heart of much of mathematics, physics, and art. Traditional geometric symmetry groups are defined in terms of isometries of the ambient space of a shape or patte…
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…
New Results in Sona Drawing: Hardness and TSP Separation
Man-Kwun Chiu, Erik D. Demaine, Jenny Diomidova +6
Given a set of point sites, a sona drawing is a single closed curve, disjoint from the sites and intersecting itself only in simple crossings, so that each bounded region of its co…
Reconfiguration of Satisfying Assignments and Subset Sums: Easy to Find, Hard to Connect
Jean Cardinal, Erik D. Demaine, David Eppstein +2
We consider the computational complexity of reconfiguration problems, in which one is given two combinatorial configurations satisfying some constraints, and is asked to transform…
Single-Player and Two-Player Buttons & Scissors Games
Kyle Burke, Erik D. Demaine, Harrison Gregg +12
We study the computational complexity of the Buttons \& Scissors game and obtain sharp thresholds with respect to several parameters. Specifically we show that the game is NP-compl…
Amazons is PSPACE-complete
Robert A. Hearn
Amazons is a board game which combines elements of Chess and Go. It has become popular in recent years, and has served as a useful platform for both game-theoretic study and AI gam…