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


View Calendar
November 17, 2023 3:00 pm - 4:00 pm
MIT, Room 2-139

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