2 citations · 2 across the 5 of their papers we have counts for
12 papers
Tetris is Hard with Just One Piece Type
MIT Hardness Group, Josh Brunner, Erik D. Demaine +2
We analyze the computational complexity of Tetris clearing (determining whether the player can clear an initial board using a given sequence of pieces) and survival (determining wh…
Reconfiguration Algorithms for Cubic Modular Robots with Realistic Movement Constraints
NASA Space Robots Team, Josh Brunner, Kenneth C. Cheung +5
We introduce and analyze a model for self-reconfigurable robots made up of unit-cube modules. Compared to past models, our model aims to newly capture two important practical aspec…
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 Simple Folding of Mixed Orthogonal Crease Patterns
Hugo Akitaya, Josh Brunner, Erik D. Demaine +3
Continuing results from JCDCGGG 2016 and 2017, we solve several new cases of the simple foldability problem -- deciding which crease patterns can be folded flat by a sequence of (s…
Complexity of Reconfiguration in Surface Chemical Reaction Networks
Robert M. Alaniz, Josh Brunner, Michael Coulombe +9
We analyze the computational complexity of basic reconfiguration problems for the recently introduced surface Chemical Reaction Networks (sCRNs), where ordered pairs of adjacent sp…
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…