***********************************
                * Princeton Discrete Math Seminar *
                ***********************************

Speaker: Bhargav Narayanan (Rutgers)

Thursday 7th March, 3:00 in Fine Hall 224.

Title: Random reconstruction in two dimensions

Suppose that we only see small “k x k snapshots” of a random 
two-dimensional “n x n picture”: can we piece the original picture 
back together? Motivated by the one-dimensional problem of shotgun 
sequencing DNA, Mossel and Ross raised several interesting questions 
(like the one aforementioned) about reconstructing  random structures 
from “small snapshots” in two (and higher) dimensions. In this talk, 
I will sketch how we can now answer some of these two-dimensional 
reconstruction questions: in particular, it turns out that the answer 
to the problem mentioned above exhibits somewhat surprising “two-point 
concentration,” and getting to this answer involves a combination 
of entropic methods and tools from percolation.

		----------------------------------

Anyone wishing to be added to or removed from the mailing list should
contact Paul Seymour (pds@math.princeton.edu)