UC Berkeley

Expanders are well-connected graphs. They have numerous applications in constructions of error correcting codes, metric embedding, derandomization, sampling algorithms, etc. Local-spectral expanders (HDXes) are a generalization of expander graphs to hypergraphs. They have recently received more attention due to their applications to agreement tests [24], locally testable codes [28, 99, 75, 27], hardness of SoS refutation [25, 59], and connections with local sampling algorithms [5]. In comparison to expanders we have very limited understanding of HDXes: there are abundant random or explicit constructions of sparse expander graphs such as random d-regular graphs [50], algebraic expanders [92, 51], the zig-zag product [101], etc. In contrast, we know only two general constructions of sparse HDXes: the LSV complexes [90] and thecoset construction [66]. In this thesis, we take two approaches to tackle the construction problem. The first approach is taking graph products of sparse expander graphs. This is inspired by the zig-zag product. However, this construction fails to give good local-spectral expansion. The second approach is inspired by the following question: does any continuous space have the local-spectral expansion property? We show that the answer is affirmative for high-dimensional spheres. More precisely, we show that 3-uniform hypergraphs sampled randomly over high-dimensional spheres are (relatively sparse) local-spectral expanders. Furthermore, tight isoperimetric inequalities of local-spectral expanders have remained elusive. Intuitively, isoperimetric inequalities provide a lower bound on the probability that a random walk leaves a subset of vertices in the graph. A tight bound on this probability is crucial for applications to agreement testing. In this thesis, we explore this problem and give an improved bound for good local-spectral expanders.