Testing Thresholds for High-Dimensional Random Geometric Graphs

Speaker: Tselil Schramm , Stanford University

Date: Tuesday, April 19, 2022

Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location: 32-G449 (Kiva)

Event Type: Seminar

Room Description: 32-G449 (Kiva)

Host: Sam Hopkins, CSAIL MIT

Contact: Nathan Higgins, nhiggins@csail.mit.edu

Relevant URL:

Speaker URL: None

Speaker Photo:
None

Reminders to: theory-seminars@lists.csail.mit.edu, seminars@lists.csail.mit.edu

Reminder Subject: TALK: Testing Thresholds for High-Dimensional Random Geometric Graphs

Abstract: We study random geometric graphs on the unit sphere in the high-dimensional setting, where the dimension grows to infinity with the number of vertices. Our central question is: given such a graph, when is it possible to identify the 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. In this talk I will present recent progress on this question: we show that in sparse geometric random graphs, if the dimension is at least polylogarithmic in the number of vertices, then the graphs are statistically indistinguishable from Erdos-Renyi graphs, and the underlying geometry disappears.

Based on joint work with Siqi Liu, Sidhanth Mohanty, and Elizabeth Yang.

Research Areas:
Algorithms & Theory

Impact Areas:

See other events that are part of the Theory of Computation (ToC) Seminar 2022.

Created by Nathan Higgins at Wednesday, April 13, 2022 at 10:40 AM.