High-Dimensional Expansion in Random Geometric Graphs

High-Dimensional Expansion in Random Geometric Graphs

Abstract:  High-dimensional expansion is a generalization of expansion to hypergraphs where the expansion of certain random walks are witnessed by local neighborhoods.This talk is on the topic of constructing natural probability distributions over sparse high-dimensional expanders (HDXes).  On one hand, (standard/1-dimensional) sparse expanders are plentiful, since a constant degree random graph is an expander with high probability.  On the other hand, most natural random models over hypergraphs fail to exhibit 2-dimensional expansion unless the average degree exceeds sqrt(number of vertices). However, sparse HDXes are known to exist due to algebraic and number theory based construction.  We describe some progress towards constructing sparse HDXes based on random geometrics graphs on the unit sphere.
Based on joint work with Siqi Liu (Berkeley), Tselil Schramm (Stanford), and Elizabeth Yang (Berkeley).
Bio: Sidhanth is a PhD student at UC Berkeley advised by Prasad Raghavendra, and is broadly interested in spectral graph theory, random matrices, and their applications in theoretical computer science.