  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. Combined with a sum-of-squares proof of the former
$\ell_2$-characterization, we give a concrete application of this framework to
algorithms for unique games on HD-walks, in many cases improving the state of
the art [RBS11, ABS15] 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 [KMS18]. 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, we open the door
for further work on the use of HDX in hardness of approximation and unique
games.
