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
Complexity of Solo Chess with Unlimited Moves
We analyze Solo Chess puzzles, where the input is an n × n board contain...
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
∙
09/21/2022
Characterizing the Decidability of Finite State Automata Team Games with Communication
In this paper we define a new model of limited communication for multipl...
research
∙
03/31/2022
The Legend of Zelda: The Complexity of Mechanics
We analyze some of the many game mechanics available to Link in the clas...
research
∙
09/29/2020
Tetris is NP-hard even with O(1) rows or columns
We prove that the classic falling-block video game Tetris (both survival...
research
∙
02/10/2020