research
∙
09/23/2021
Multidimensional Scaling: Approximation and Complexity
Metric Multidimensional scaling (MDS) is a classical method for generati...
share
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
∙
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
∙
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/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
∙
07/17/2020
Escaping a Polygon
Suppose an "escaping" player moves continuously at maximum speed 1 in th...
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
∙
03/22/2020
1 x 1 Rush Hour with Fixed Blocks is PSPACE-complete
Consider n^2-1 unit-square blocks in an n × n square board, where each b...
research
∙
02/10/2020
Edge Matching with Inequalities, Triangles, Unknown Shape, and Two Players
We analyze the computational complexity of several new variants of edge-...
research
∙
05/01/2019
Reconfiguring Undirected Paths
We consider problems in which a simple path of fixed length, in an undir...
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
∙
03/03/2018
Path Puzzles: Discrete Tomography with a Path Constraint is Hard
We prove that path puzzles with complete row and column information--or ...
research
∙
12/26/2017
Folding Polyominoes into (Poly)Cubes
We study the problem of folding a polyomino P into a polycube Q, allowin...
research
∙
08/22/2017