5 papers
Folding Polyominoes with Holes into a Cube
Oswin Aichholzer, Hugo A. Akitaya, Kenneth C. Cheung +9
When can a polyomino piece of paper be folded into a unit cube? Prior work studied tree-like polyominoes, but polyominoes with holes remain an intriguing open problem. We present s…
On Minimal Sets to Destroy the -Core in Random Networks
Christian Schmidt, Henry D. Pfister, Lenka Zdeborová
We study the problem of finding the smallest set of nodes in a network whose removal results in an empty -core; where the -core is the sub-network obtained after the iterativ…
Dense Limit of the Dawid-Skene Model for Crowdsourcing and Regions of Sub-optimality of Message Passing Algorithms
Christian Schmidt, Lenka Zdeborová
Crowdsourcing is a strategy to categorize data through the contribution of many individuals. A wide range of theoretical and algorithmic contributions are based on the model of Daw…
Single-Player and Two-Player Buttons & Scissors Games
Kyle Burke, Erik D. Demaine, Harrison Gregg +12
We study the computational complexity of the Buttons \& Scissors game and obtain sharp thresholds with respect to several parameters. Specifically we show that the game is NP-compl…
Computing Nonsimple Polygons of Minimum Perimeter
Sándor P. Fekete, Andreas Haas, Michael Hemmer +8
We provide exact and approximation methods for solving a geometric relaxation of the Traveling Salesman Problem (TSP) that occurs in curve reconstruction: for a given set of vertic…