research
∙
08/29/2023
When Can You Tile an Integer Rectangle with Integer Squares?
This paper characterizes when an m × n rectangle, where m and n are inte...
share
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...
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
∙
12/23/2022
Computational Complexity of Flattening Fixed-Angle Orthogonal Chains
Planar/flat configurations of fixed-angle chains and trees are well stud...
research
∙
11/26/2022
Lower Bounds on Retroactive Data Structures
We prove essentially optimal fine-grained lower bounds on the gap betwee...
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
∙
07/14/2022
PSPACE-Completeness of Reversible Deterministic Systems
We prove PSPACE-completeness of several reversible, fully deterministic ...
research
∙
06/08/2022
Reconfiguration of Non-crossing Spanning Trees
For a set P of n points in the plane in general position, a non-crossing...
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
∙
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
∙
10/27/2021
An Efficient Reversible Algorithm for Linear Regression
This paper presents an efficient reversible algorithm for linear regress...
research
∙
10/26/2021
The Computational Complexity of Finding Arithmetic Expressions With and Without Parentheses
We show NP-completeness for various problems about the existence of arit...
research
∙
09/23/2021
Multidimensional Scaling: Approximation and Complexity
Metric Multidimensional scaling (MDS) is a classical method for generati...
research
∙
08/26/2021
Optimal-area visibility representations of outer-1-plane graphs
This paper studies optimal-area visibility representations of n-vertex o...
research
∙
06/29/2021
Yin-Yang Puzzles are NP-complete
We prove NP-completeness of Yin-Yang / Shiromaru-Kuromaru pencil-and-pap...
research
∙
05/22/2021
Continuous Flattening of All Polyhedral Manifolds using Countably Infinite Creases
We prove that any finite polyhedral manifold in 3D can be continuously f...
research
∙
05/18/2021
Snipperclips: Cutting Tools into Desired Polygons using Themselves
We study Snipperclips, a computer puzzle game whose objective is to crea...
research
∙
05/14/2021
Generalized LR-drawings of trees
The LR-drawing-method is a method of drawing an ordered rooted binary tr...
research
∙
03/11/2021
Hardness of Token Swapping on Trees
Given a graph where every vertex has exactly one labeled token, how can ...
research
∙
12/14/2020
Characterizing Universal Reconfigurability of Modular Pivoting Robots
We give both efficient algorithms and hardness results for reconfiguring...
research
∙
11/23/2020
Arithmetic Expression Construction
When can n given numbers be combined using arithmetic operators from a g...
research
∙
10/17/2020
Mad Science is Provably Hard: Puzzles in Hearthstone's Boomsday Lab are NP-hard
We consider the computational complexity of winning this turn (mate-in-1...
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
∙
07/17/2020
Escaping a Polygon
Suppose an "escaping" player moves continuously at maximum speed 1 in th...
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
Walking through Doors is Hard, even without Staircases: Proving PSPACE-hardness via Planar Assemblies of Door Gadgets
A door gadget has two states and three tunnels that can be traversed by ...
research
∙
06/01/2020
Negative Instance for the Edge Patrolling Beacon Problem
Can an infinite-strength magnetic beacon always “catch” an iron ball, wh...
research
∙
05/07/2020
Trains, Games, and Complexity: 0/1/2-Player Motion Planning through Input/Output Gadgets
We analyze the computational complexity of motion planning through local...
research
∙
03/18/2020
Tatamibari is NP-complete
In the Nikoli pencil-and-paper game Tatamibari, a puzzle consists of an ...
research
∙
02/12/2020
Recursed is not Recursive: A Jarring Result
Recursed is a 2D puzzle platform video game featuring treasure chests th...
research
∙
09/30/2019
Hamiltonicity in Semi-Regular Tessellation Dual Graphs
This paper shows NP-completeness for finding Hamiltonian cycles in induc...
research
∙
04/19/2019
Data Races and the Discrete Resource-time Tradeoff Problem with Resource Reuse over Paths
A determinacy race occurs if two or more logically parallel instructions...
research
∙
12/10/2018
A General Theory of Motion Planning Complexity: Characterizing Which Gadgets Make Games Hard
We build a general theory for characterizing the computational complexit...
research
∙
08/22/2018
Cookie Clicker
Cookie Clicker is a popular online incremental game where the goal of th...
research
∙
06/14/2018
Losing at Checkers is Hard
We prove computational intractability of variants of checkers: (1) decid...
research
∙
06/09/2018
Computational Complexity of Motion Planning of a Robot through Simple Gadgets
We initiate a general theory for analyzing the complexity of motion plan...
research
∙
05/08/2018
The Computational Complexity of Finding Hamiltonian Cycles in Grid Graphs of Semiregular Tessellations
Finding Hamitonian Cycles in square grid graphs is a well studied and im...
research
∙
04/26/2018
Who witnesses The Witness? Finding witnesses in The Witness is hard and sometimes impossible
We analyze the computational complexity of the many types of pencil-and-...
research
∙
11/21/2017
Fine-Grained I/O Complexity via Reductions: New lower bounds, faster algorithms, and a time hierarchy
This paper initiates the study of I/O algorithms (minimizing cache misse...
research
∙
09/05/2017
