Random reconstruction in two dimensions
Random reconstruction in two dimensions

Bhargav Narayanan, Rutgers
Fine Hall 224
Suppose that we only see small “k x k snapshots” of a random twodimensional “n x n picture”: can we piece the original picture back together? Motivated by the onedimensional 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 twodimensional reconstruction questions: in particular, it turns out that the answer to the problem mentioned above exhibits somewhat surprising “twopoint concentration,” and getting to this answer involves a combination of entropic methods and tools from percolation.