
Optimalarea visibility representations of outer1plane graphs
This paper studies optimalarea visibility representations of nvertex o...
read it

YinYang Puzzles are NPcomplete
We prove NPcompleteness of YinYang / ShiromaruKuromaru pencilandpap...
read it

Continuous Flattening of All Polyhedral Manifolds using Countably Infinite Creases
We prove that any finite polyhedral manifold in 3D can be continuously f...
read it

Snipperclips: Cutting Tools into Desired Polygons using Themselves
We study Snipperclips, a computer puzzle game whose objective is to crea...
read it

Generalized LRdrawings of trees
The LRdrawingmethod is a method of drawing an ordered rooted binary tr...
read it

Hardness of Token Swapping on Trees
Given a graph where every vertex has exactly one labeled token, how can ...
read it

Characterizing Universal Reconfigurability of Modular Pivoting Robots
We give both efficient algorithms and hardness results for reconfiguring...
read it

Arithmetic Expression Construction
When can n given numbers be combined using arithmetic operators from a g...
read it

Mad Science is Provably Hard: Puzzles in Hearthstone's Boomsday Lab are NPhard
We consider the computational complexity of winning this turn (matein1...
read it

Tetris is NPhard even with O(1) rows or columns
We prove that the classic fallingblock video game Tetris (both survival...
read it

Escaping a Polygon
Suppose an "escaping" player moves continuously at maximum speed 1 in th...
read it

PSPACEcompleteness of Pulling Blocks to Reach a Goal
We prove PSPACEcompleteness of all but one problem in a large space of ...
read it

Walking through Doors is Hard, even without Staircases: Proving PSPACEhardness via Planar Assemblies of Door Gadgets
A door gadget has two states and three tunnels that can be traversed by ...
read it

Negative Instance for the Edge Patrolling Beacon Problem
Can an infinitestrength magnetic beacon always “catch” an iron ball, wh...
read it

Trains, Games, and Complexity: 0/1/2Player Motion Planning through Input/Output Gadgets
We analyze the computational complexity of motion planning through local...
read it

Tatamibari is NPcomplete
In the Nikoli pencilandpaper game Tatamibari, a puzzle consists of an ...
read it

Recursed is not Recursive: A Jarring Result
Recursed is a 2D puzzle platform video game featuring treasure chests th...
read it

Hamiltonicity in SemiRegular Tessellation Dual Graphs
This paper shows NPcompleteness for finding Hamiltonian cycles in induc...
read it

Data Races and the Discrete Resourcetime Tradeoff Problem with Resource Reuse over Paths
A determinacy race occurs if two or more logically parallel instructions...
read it

A General Theory of Motion Planning Complexity: Characterizing Which Gadgets Make Games Hard
We build a general theory for characterizing the computational complexit...
read it

Cookie Clicker
Cookie Clicker is a popular online incremental game where the goal of th...
read it

Losing at Checkers is Hard
We prove computational intractability of variants of checkers: (1) decid...
read it

Computational Complexity of Motion Planning of a Robot through Simple Gadgets
We initiate a general theory for analyzing the complexity of motion plan...
read it

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...
read it

Who witnesses The Witness? Finding witnesses in The Witness is hard and sometimes impossible
We analyze the computational complexity of the many types of penciland...
read it

FineGrained 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...
read it

PushPull Block Puzzles are Hard
This paper proves that pushpull block puzzles in 3D are PSPACEcomplete...
read it
Jayson Lynch
is this you? claim profile