## EVENT DETAILS AND ABSTRACT

**Probability Seminar**
**Title:** Embedding in high-dimensional random geometric graphs

**Speaker:** Shuangping Li

**Speaker Info:** Stanford University

**Brief Description:** Embedding in high-dimensional random geometric graphs

**Special Note**:

**Abstract:**

I will discuss a random geometric graph model, where connections between vertices depend on the distances between latent d-dimensional feature vectors. We are especially interested in the high-dimensional case when d is large. Upon observing a graph, our aim is to recover these latent feature vectors (i.e., embedding). We have identified a phase transition phenomenon: when d is significantly larger than nH(p) (with a polylogarithmic term), embedding becomes feasible with high probability using a spectral algorithm. H here represents the entropy function. Conversely, when d is considerably smaller than nH(p), embedding becomes information theoretically impossible. In our proof of the impossibility result, we design a Glauber dynamics and show that it can find two distant embeddings that produce the same graph. This is based on joint works with Eric Ma and Tselil Schramm.

**Date:** Tuesday, November 14, 2023

**Time:** 3:00PM

**Where:** Lunt 107

**Contact Person:** Reza Gheissari

**Contact email:** gheissari@northwestern.edu

**Contact Phone:**

Copyright © 1997-2024
Department of Mathematics, Northwestern University.