Theory Seminar

Friday, May 6, 2022 - 3:00pm to 4:00pm

Location:

In Person Gates Hillman 8102

Speaker:

SIDHANTH MOHANTY, Ph.D. StudentTheory GroupDepartment of Electrical Engineering and Computer SciencesUniversity of California, Berkeley http://sidhanthm.com/

Testing thresholds for sparse random geometric graphs

In the random geometric graph model, we identify each of our vertices with an independently and uniformly sampled vector from a high-dimensional unit sphere, and we connect pairs of vertices whose vectors are sufficiently close.A fundamental question is: when is a random geometric graph a faithful model for its underlying geometry?  As the dimension grows relative to the number of vertices, the edges in the graph become increasingly independent, and the underlying geometry becomes less apparent.  This talk will cover some recent progress on this question: we show that in sparse random geometric graphs, if the dimension is at least polylogarithmic in the number of vertices, then the graphs are statistically indistinguishable from Erdős-Rényi graphs, i.e. the underlying geometry disappears. Based on joint work with Siqi Liu, Tselil Schramm, and Elizabeth Yang

Additional Reading

Event Website:

http://theory.cs.cmu.edu/#talks

For More Information, Contact:

Keywords:

Seminar Series