
Multidimensional Scaling: Approximation and Complexity
Metric Multidimensional scaling (MDS) is a classical method for generati...
read it

Snipperclips: Cutting Tools into Desired Polygons using Themselves
We study Snipperclips, a computer puzzle game whose objective is to crea...
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

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

New Results in Sona Drawing: Hardness and TSP Separation
Given a set of point sites, a sona drawing is a single closed curve, dis...
read it

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

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

1 x 1 Rush Hour with Fixed Blocks is PSPACEcomplete
Consider n^21 unitsquare blocks in an n × n square board, where each b...
read it

Edge Matching with Inequalities, Triangles, Unknown Shape, and Two Players
We analyze the computational complexity of several new variants of edge...
read it

Reconfiguring Undirected Paths
We consider problems in which a simple path of fixed length, in an undir...
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

Path Puzzles: Discrete Tomography with a Path Constraint is Hard
We prove that path puzzles with complete row and column informationor ...
read it

Folding Polyominoes into (Poly)Cubes
We study the problem of folding a polyomino P into a polycube Q, allowin...
read it

Upward Partitioned Book Embeddings
We analyze a directed variation of the book embedding problem when the p...
read it
Adam Hesterberg
is this you? claim profile