Richard P. Stanley Seminar in Combinatorics: Random Reconstruction in Two Dimensions

SEMINARS, HARVARD-MIT COMBINATORICS

Speaker:

Bhargav Narayanan - Rutgers

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.

===============================

For more info, see https://math.mit.edu/combin/