High Dimensional Expanders: Eigenstripping, Pseudorandomness, and Unique Games

Understand

Higher order random walks (HD-walks) on high dimensional expanders (HDX) have seen an incredible amount of study and application since their introduction by Kaufman and Mass [KM16], yet their broader combinatorial and spectral properties remain poorly understood.

• We develop a combinatorial characterization of the spectral structure of HD-walks on two-sided local-spectral expanders [DK17], which offer a broad generalization of the well-studied Johnson and Grassmann graphs.
• Our characterization, which shows that the spectra of HD-walks lie tightly concentrated in a few combinatorially structured strips, leads to novel structural theorems such as a tight $\ell_2$-characterization of edge-expansion, as well as to a new understanding of local-to-global algorithms on HDX.
• Towards the latter, we introduce a spectral complexity measure called Stripped Threshold Rank, and show how it can replace the (much larger) threshold rank in controlling the performance of algorithms on structured objects.