Skip to main content

Julia Gaudio: Shotgun Assembly of Erdos-Renyi Random Graphs

Time: Mon 2021-06-07 15.15 - 16.15

Location: Zoom, meeting ID: 621 4469 8204

Participating: Julia Gaudio (MIT)

Export to calendar

Abstract

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^{-\alpha}\) for \(0 < \alpha < 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 < \alpha < \frac{1}{3}\), but not reconstructable for \(\frac{1}{2} < \alpha < 1\). Given the collection of distance-2 neighborhoods, \(G\) is exactly reconstructable for \(0 < \alpha < \frac{3}{5}\), but not reconstructable for \(\frac{3}{4} < \alpha < 1\).

This is based on joint work with Elchanan Mossel.

Zoom notes: This meeting ID – 621 4469 8204 – will be the recurring meeting for the Statistics and Probability Seminar.