research
∙
06/01/2023
Complexity of Motion Planning of Arbitrarily Many Robots: Gadgets, Petri Nets, and Counter Machines
We extend the motion-planning-through-gadgets framework to several new s...
share
research
∙
03/27/2023
Complexity of Reconfiguration in Surface Chemical Reaction Networks
We analyze the computational complexity of basic reconfiguration problem...
research
∙
02/02/2023
This Game Is Not Going To Analyze Itself
We analyze the puzzle video game This Game Is Not Going To Load Itself, ...
research
∙
04/01/2022
Traversability, Reconfiguration, and Reachability in the Gadget Framework
Consider an agent traversing a graph of "gadgets", each with local state...
research
∙
09/09/2021
Any Regular Polyhedron Can Transform to Another by O(1) Refoldings
We show that several classes of polyhedra are joined by a sequence of O(...
research
∙
01/16/2021
Strings-and-Coins and Nimstring are PSPACE-complete
We prove that Strings-and-Coins – the combinatorial two-player game gene...
research
∙
07/31/2020
New Results in Sona Drawing: Hardness and TSP Separation
Given a set of point sites, a sona drawing is a single closed curve, dis...
research
∙
06/08/2020
PSPACE-completeness of Pulling Blocks to Reach a Goal
We prove PSPACE-completeness of all but one problem in a large space of ...
research
∙
06/01/2020