Georgia Institute of Technology College of Sciences

(first of two talks; the second is on Sep. 29)

A random geometric graph (RGG) is generated by first sampling $n$ latent points independently and uniformly from the unit sphere in $R^d$, and then connecting each pair of points if their inner product exceeds a threshold. We study the sharp detection threshold---the largest dimension at which the RGG can be statistically distinguished from the Erdős--Rényi graph with the same edge density $p$. This threshold is conjectured to be $d \asymp (n h(p))^3$, where $h(p)$ is the binary entropy function. Previous works proved this conjecture for dense graphs with constant $p$ and, up to polylogarithmic factors, very sparse graphs with constant average degrees. In this series of two talks, I will discuss a resolution of this conjecture. This is based on joint work with Hang Du, Nike Sun, Yihong Wu, and Jiaming Xu.

I'll present various methods, some old, some new,  leading to estimates on the variance of $f(X_1, X_2, \dots, X_n)$ where  

$X_1, X_2, \dots, X_n$ are independent random variables.  These methods will be illustrated with various examples.