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 (ITCS 2016), 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 (Dinur and Kaufman FOCS 2017), 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 graph algorithms on HDX.

Towards the latter, we introduce a novel spectral complexity measure called \textit{Stripped Threshold Rank}, and show how it can replace the (much larger) threshold rank as a parameter controlling the performance of algorithms on structured objects. Combined with a sum-of-squares proof for the former $\ell_2$-characterization, we give a concrete application of this framework to algorithms for unique games on HD-walks, where in many cases we improve the state of the art (Barak, Raghavendra, and Steurer FOCS 2011, and Arora, Barak, and Steurer JACM 2015) from nearly-exponential to polynomial time (e.g.\ for sparsifications of Johnson graphs or of slices of the $q$-ary hypercube). Our characterization of expansion also holds an interesting connection to hardness of approximation, where an $\ell_\infty$-variant for the Grassmann graphs was recently used to resolve the 2-2 Games Conjecture (Khot, Minzer, and Safra FOCS 2018). We give a reduction from a related $\ell_\infty$-variant to our $\ell_2$-characterization, but it loses factors in the regime of interest for hardness where the gap between $\ell_2$ and $\ell_\infty$ structure is large. Nevertheless, our results open the door for further work on the use of HDX in hardness of approximation and their general relation to unique games.

New version includes UG algorithm for HD-walks over all two-sided local-spectral expanders (previously only over the complete complex). It also includes tighter structural theorems and simplified proofs.

Higher order random walks (HD-walks) on high dimensional expanders have played a crucial role in a number of recent breakthroughs in theoretical computer science, perhaps most famously in the recent resolution of the Mihail-Vazirani conjecture (Anari et al. STOC 2019), which focuses on HD-walks on one-sided local-spectral expanders. In this work we study the spectral structure of walks on the stronger two-sided variant, which capture wide generalizations of important objects like the Johnson and Grassmann graphs. We prove that the spectra of these walks are tightly concentrated in a small number of strips, each of which corresponds combinatorially to a level in the underlying complex. Moreover, the eigenvalues corresponding to these strips decay exponentially with a measure we term the depth of the walk.

Using this spectral machinery, we characterize the edge-expansion of small sets based upon the interplay of their local combinatorial structure and the global decay of the walk's eigenvalues across strips. Variants of this result for the special cases of the Johnson and Grassmann graphs were recently crucial both for the resolution of the 2-2 Games Conjecture (Khot et al. FOCS 2018), and for efficient algorithms for affine unique games over the Johnson graphs (Bafna et al. Arxiv 2020). For the complete complex, our characterization admits a low-degree Sum of Squares proof. Building on the work of Bafna et al., we provide the first polynomial time algorithm for affine unique games over the Johnson scheme. The soundness and runtime of our algorithm depend upon the number of strips with large eigenvalues, a measure we call High-Dimensional Threshold Rank that calls back to the seminal work of Barak, Raghavendra, and Steurer (FOCS 2011) on unique games and threshold rank.