UC San Diego

High dimensional expanders (HDX) are a nascent generalization of expander graphs (sparse yet robustly connected networks that play a core role in the theory of computation) to high dimensional domains. Despite recent breakthrough use in sampling and local testability, relatively little is known about HDX, their properties, and their broader position in theoretical computer science. In this dissertation, we develop the role of high dimensional expanders in computation through the interplay of Boolean analysis, concentration of measure, approximation algorithms, and hardness of approximation.

In the first half of this dissertation, we develop a robust theory of Fourier and probabilistic analysis on HDX. This includes generalizations of standard tools of theoretical computer science such as the Fourier decomposition, hypercontractivity, and Chernoff bounds, as well as more application-focused techniques such as symmetrization, reverse hypercontractivity, and concentration of high degree functions. In many cases, our results give the first \emph{sparse} domains satisfying such notions, a critical consideration in application where density or `degree' controls the cost associated with their use.

In the second half of this dissertation, we give applications of these ideas to algorithms, complexity, and mathematics. Algorithmically, we show the local structure of high dimensional expanders can be exploited to build fast approximation algorithms for unique games, and explore implications of fast approximate sampling algorithms on HDX to massive multiplayer matrix games. In mathematics, we show high dimensional expanders have optimal geometric overlap, extend a variant of the Frankl–R\"{o}dl theorem to HDX, and prove new degree lower bounds for certain HDX. Finally in complexity we leverage new topological HDX to construct optimally hard explicit constraint satisfaction problems for Sum-of-Squares (a powerful optimization paradigm), and prove spectral HDX satisfy an optimal (local) agreement testing theorem and an optimal global tester under stronger $\ell_\infty$-type assumptions, a stepping stone towards improved low-soundness probabilistically checkable proofs and hardness of approximation.