Mittagsseminar (in cooperation with J. Lengler, A. Steger, and D. Steurer)

Date and Time: Thursday, March 31, 2016, 12:15 pm

Duration: 30 minutes

Location: OAT S15/S16/S17

Speaker: Pascal Pfister

A threshold for the identifiability of the $n \times n$ random jigsaw puzzle

The jigsaw Puzzle is given by an $n \times n$ grid $G$ of puzzle pieces, where each puzzle piece has exactly four edges associated to it. Each pair of adjacent edges of the puzzle is coloured uniformly and independently at random from one of $q$ colors (edges adjacent to the border of the grid get coloured as well). We assume that two pieces can be joined at two of their edges if and only if both of these edges have the same colour. The problem then is the following: given a stack of $n^2$ coloured puzzle pieces, is it possible to find the original composition $G$ of the puzzle? Or formulated differently, how large does $q$ need to be so that the only possible reconstruction of the puzzle pieces is the original puzzle itself?

We show the following:
i) if $q = o(n)$ then the probability of unique reconstruction goes to 0 as $n \rightarrow \infty$, and
ii) for every $0 < \epsilon < 1/4$: if $q \geq n^{1+ \epsilon}$ then the probability of unique reconstruction goes to 1 as $n \rightarrow \infty$.

This result solves a conjecture of Mossel and Ross from their paper "Shotgun assembly of labeled graphs" (recall Mossel's Mittagseminar talk from last Oktober).

Upcoming talks     |     All previous talks     |     Talks by speaker     |     Upcoming talks in iCal format (beta version!)

Previous talks by year:   2024  2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login