Skip to main content

Seminars - Probability and statistics

KTH's seminar series on probability, statistics, data science and related topics.

The seminar takes place on Mondays 15:15–16:16. For now all talks are held via Zoom, with meeting ID 62144698204

Next Talk

Monday, 7 June, 15:15
Julia Gaudio (MIT)
Shotgun Assembly of Erdos-Renyi Random Graphs

Graph shotgun assembly refers to the problem of reconstructing a graph from a collection of local neighborhoods. We consider shotgun assembly of Erdos-Renyi random graphs G(n, p_n), where p_n = n^{-α} for 0 < α < 1. We consider both reconstruction up to isomorphism as well as exact reconstruction (recovering the vertex labels as well as the structure). We show that given the collection of distance-1 neighborhoods, G is exactly reconstructable for 0 < α < 1/3, but not reconstructable for 1/2 < α < 1. Given the collection of distance-2 neighborhoods, G is exactly reconstructable for 0 < α < 3/5, but not reconstructable for 3/4 < α < 1. (Joint work with Elchanan Mossel)