Chicago Journal of Theoretical Computer Science

Volume 2017

Article 2

Published by the Department of Computer Science, The University of Chicago.

Unique reconstruction threshold for random jigsaw puzzles

Rajko Nenadov;
School of Mathematical Sciences
Monash University
Melbourne, Australia
rajko DOT nedanov AT monash DOT edu

Pascal Pfister
Institute of Theoretical Computer Science
Zurich, Switzerland
ppfister AT inf DOT ethz DOT ch


Angelika Steger
Institute of Theoretical Computer Science
steger AT inf DOT ethz DOT ch

June 30, 2017


A random jigsaw puzzle is constructed by arranging $n^2$ square pieces into an $n \times n$ grid and assigning to each edge of a piece one of $q$ available colors uniformly at random, with the restriction that touching edges receive the same color. We show that if $q = o(n)$ then with high probability such a puzzle does not have a unique solution, while if $q \ge n^{1 + \varepsilon}$ for any constant $\varepsilon > 0$ then the solution is unique. This solves a conjecture of Mossel and Ross (Shotgun assembly of labeled graphs, arXiv:1504.07682).

Submitted October 21, 2016, revised May 22, 2017, in final form June 29, 2017, published June 30, 2017

DOI: 10.4086/cjtcs.2017.002

[] Volume 2017, Article 1
[back] Volume 2017 [back] Published articles
[CJCTS home]