EVENT DETAILS AND ABSTRACT

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.