Analysis Seminar

Wednesday, October 20, 2021 4:00 pm - 4:00 pm EDT (GMT -04:00)

Konstantin Tikhomirov, Georgia Institute of Technology

"Shotgun assembly of Erdos-Renyi graphs"

We show that in the regime p>n^{-1/2} polylog(n), the unlabeled G(n,p) random graph can be uniquely reconstructed from its 1-neighborhoods with probability close to one, answering a question of Gaudio and Mossel. Based on joint work with Han Huang.

This seminar will be held jointly online and in person.