We construct the first (locally computable, approximately) locally list decodable codes with rate, efficiency, and error tolerance approaching the information theoretic limit, a core regime of interest for the complexity theoretic task of hardness amplification. Our algorithms run in polylogarithmic time and sub-logarithmic depth, which together with classic constructions in the unique decoding (low-noise) regime leads to the resolution of several long-standing problems in coding and complexity theory:

The focus of this paper is the development of new elementary techniques for the construction and analysis of high dimensional expanders. Specifically, we present two new explicit constructions of Cayley high dimensional expanders (HDXs) over the abelian group 𝔽₂ⁿ. Our expansion proofs use only linear algebra and combinatorial arguments. The first construction gives local spectral HDXs of any constant dimension and subpolynomial degree exp(n^ε) for every ε > 0, improving on a construction by Golowich [Golowich, 2023] which achieves ε = 1/2. [Golowich, 2023] derives these HDXs by sparsifying the complete Grassmann poset of subspaces. The novelty in our construction is the ability to sparsify any expanding Grassmann posets, leading to iterated sparsification and much smaller degrees. The sparse Grassmannian (which is of independent interest in the theory of HDXs) serves as the generating set of the Cayley graph. Our second construction gives a 2-dimensional HDX of any polynomial degree exp(ε n) for any constant ε > 0, which is simultaneously a spectral expander and a coboundary expander. To the best of our knowledge, this is the first such non-trivial construction. We name it the Johnson complex, as it is derived from the classical Johnson scheme, whose vertices serve as the generating set of this Cayley graph. This construction may be viewed as a derandomization of the recent random geometric complexes of [Liu et al., 2023]. Establishing coboundary expansion through Gromov’s "cone method" and the associated isoperimetric inequalities is the most intricate aspect of this construction. While these two constructions are quite different, we show that they both share a common structure, resembling the intersection patterns of vectors in the Hadamard code. We propose a general framework of such "Hadamard-like" constructions in the hope that it will yield new HDXs.

We give new bounds on the cosystolic expansion constants of several families of high dimensional expanders, and the known coboundary expansion constants of order complexes of homogeneous geometric lattices, including the spherical building of $SL_n(F_q)$. The improvement applies to the high dimensional expanders constructed by Lubotzky, Samuels and Vishne, and by Kaufman and Oppenheim. Our new expansion constants do not depend on the degree of the complex nor on its dimension, nor on the group of coefficients. This implies improved bounds on Gromov's topological overlap constant, and on Dinur and Meshulam's cover stability, which may have applications for agreement testing. In comparison, existing bounds decay exponentially with the ambient dimension (for spherical buildings) and in addition decay linearly with the degree (for all known bounded-degree high dimensional expanders). Our results are based on several new techniques: * We develop a new "color-restriction" technique which enables proving dimension-free expansion by restricting a multi-partite complex to small random subsets of its color classes. * We give a new "spectral" proof for Evra and Kaufman's local-to-global theorem, deriving better bounds and getting rid of the dependence on the degree. This theorem bounds the cosystolic expansion of a complex using coboundary expansion and spectral expansion of the links. * We derive absolute bounds on the coboundary expansion of the spherical building (and any order complex of a homogeneous geometric lattice) by constructing a novel family of very short cones.

High dimensional expanders (HDXs) are a hypergraph generalization of expander graphs. They are extensively studied in the math and TCS communities due to their many applications. Like expander graphs, HDXs are especially interesting for applications when they are bounded degree, namely, if the number of edges adjacent to every vertex is bounded. However, only a handful of constructions are known to have this property, all of which rely on algebraic techniques. In particular, no random or combinatorial construction of bounded degree HDXs is known. As a result, our understanding of these objects is limited. The degree of an $i$-face in an HDX is the number of $(i+1)$-faces containing it. In this work we construct HDXs whose higher dimensional faces have bounded degree. This is done by giving an elementary and deterministic algorithm that takes as input a regular $k$-dimensional HDX $X$ and outputs another $k$-dimensional HDX $\widehat{X}$ with twice as many vertices. While the degree of vertices in $\widehat{X}$ grows, the degree of the $(k-1)$-faces in $\widehat{X}$ stays the same. As a result, we obtain a new `algebra-free' construction of HDXs whose $(k-1)$-face degree is bounded. Our algorithm is based on a simple and natural generalization of the construction by Bilu and Linial (Combinatorica, 2006), which build expanders using lifts coming from edge signings. Our construction is based on local lifts of HDXs, where a local lift is a complex whose top-level links are lifts of links in the original complex. We demonstrate that a local lift of an HDX is an HDX in many cases. In addition, combining local lifts with existing bounded degree constructions creates new families of bounded degree HDXs with significantly different links than before. For every large enough $D$, we use this technique to construct families of bounded degree HDXs with links that have diameter $\geq D$.

We solve the derandomized direct product testing question in the low acceptance regime, by constructing new high dimensional expanders that have no small connected covers. We show that our complexes have swap cocycle expansion, which allows us to deduce the agreement theorem by relying on previous work. Derandomized direct product testing, also known as agreement testing, is the following problem. Let$X$be a family of k-element subsets of$[N]$and let$\{f_{s}:s\rightarrow\Sigma\vert s\in X\}$be an ensemble of local functions, each defined over a subset$s\subset\lceil N$. Suppose that we run the following so-called agreement test: choose a random pair of sets$s_{1}, s_{2}\in X$that intersect on$\sqrt{k}$elements, and accept if$f_{s_{1}}, f_{s_{2}}$agree on the elements in$s_{1}\cap s_{2}$. We denote the success probability of this test by Agree$\{f_{s}\})$Given that Agree$(\{f_{s}\})=\varepsilon > 0$is there a global function$G:[N]\rightarrow\Sigma$such that$f_{s}=G\vert _{s}$for a non-negligible fraction of$s\in X\ ?$We construct a family$X$of k-subsets of$[N]$such that$\vert X\vert =O(N)$, and such that it satisfies the low acceptance agreement theorem. Namely,$\text{Agree}\left(\left\{f_s\right\}\right)>\varepsilon \Longrightarrow \exists G:[N] \rightarrow \Sigma, \quad \underset{s}{\mathbb{P}}\left[\left.f_s \stackrel{0.99}{\approx} G\right\vert_s\right] \geqslant \text{poly}(\varepsilon)$. A key idea is to replace the well-studied LSV complexes by symplectic high dimensional expanders (HDXs). The family$X$is just the k-faces of the new symplectic HDXs. The latter serve our needs better since their fundamental group satisfies the congruence subgroup property, which implies that they lack small covers. We also give a polynomial-time algorithm to construct this family of sym-plectic HDXs.

We prove optimal concentration of measure for lifted functions on high dimensional expanders (HDX). Let$X$be a$k$-dimensional HDX. We show for any$i \leq k$and function$f: X(i)\rightarrow [0, 1]$: \begin{equation*}\underset{s \in X(k)}{\mathbb{P}}[\vert \underset{t \subseteq s}{\mathbb{E}}[f(t)]-\mu\vert \geqslant \varepsilon] \leqslant \exp \left(-\varepsilon^2 \frac{k}{i}\right). \end{equation*} Using this fact, we prove that high dimensional expanders are reverse hypercontractive, a powerful functional inequality from discrete analysis implying that for any sets$A, B \subset X(k)$, the probability a$\rho$-correlated pair passes between them is at least \begin{equation*}\underset{s, s^{\prime} \sim T_\rho}{\mathbb{P}}\left[s \in A, s^{\prime} \in B\right] \geqslant \mathbb{P}[A]^{O(1)} \mathbb{P}[B]^{O(1)}.\end{equation*} Our results hold under weak spectral assumptions on$X$. Namely we prove exponential concentration of measure for any complex below the ‘Trickling-Down Threshold’ (beyond which concentration may be arbitrarily poor), and optimal concentration for$\sqrt{k}$. skeletons of such complexes. We also show optimal bounds for the top dimension of stronger HDX among other settings. We leverage our inequalities to prove several new agreement testing theorems on high dimensional expanders, including a new 99%-regime test for subsets, and a variant of the ‘Z-test’ achieving inverse exponential soundness under the stronger assumption of$\ell_{\infty}$-expansion. The latter gives rise to the first optimal testers beyond the complete complex and products, a stepping stone toward the use of HDX in strong soundness PCPs. We also give applications within expansion, analysis, combinatorics, and coding theory, including a proof that two-sided HDX have optimal geometric overlap (giving the first explicit bounded-degree construction), near-optimal double samplers, new super-exponential degree lower bounds for certain HDX, distance-amplified list-decodable and locally testable codes, a Frankl+Rödl Theorem, and more.

We introduce and study swap cosystolic expansion, a new expansion property of simplicial complexes. We prove lower bounds for swap coboundary expansion of spherical buildings and use them to lower bound swap cosystolic expansion of the LSV Ramanujan complexes. Our motivation is the recent work (in a companion paper) showing that swap cosystolic expansion implies agreement theorems. Together the two works show that these complexes support agreement tests in the low acceptance regime. We also study the closely related swap coboundary expansion. Swap cosystolic expansion is defined by considering, for a given complex X, its faces complex , whose vertices are r-faces of X and where two vertices are connected if their disjoint union is also a face in X. The faces complex is a derandomization of the product of X with itself r times. The graph underlying is the swap walk of X, known to have excellent spectral expansion. The swap cosystolic expansion of X is defined to be the cosystolic expansion of . Our main result is a exp(−O(√r)) lower bound on the swap coboundary expansion of the spherical building and the swap cosystolic expansion of the LSV complexes. For more general coboundary expanders we show a weaker lower bound of exp(−O(r)).

Let X be a family of k-element subsets of [n] and let {fs:s→Σ : s∈ X} be an ensemble of local functions, each defined over a subset s⊂ [n]. Is there a global function G:[n]→Σ such that fs = G|s for all s∈ X ? An agreement test is a randomized property tester for this question.

We present a new construction of high dimensional expanders based on covering spaces of simplicial complexes. High dimensional expanders (HDXs) are hypergraph analogues of expander graphs. They have many uses in theoretical computer science, but unfortunately only few constructions are known which have arbitrarily small local spectral expansion.

We introduce a framework of layered subsets, and give a sufficient condition for when a set system supports an agreement test. Agreement testing is a certain type of property testing that generalizes PCP tests such as the plane vs. plane test. Previous work has shown that high dimensional expansion is useful for agreement tests. We extend these results to more general families of subsets, beyond simplicial complexes. These include - Agreement tests for set systems whose sets are faces of high dimensional expanders. Our new tests apply to all dimensions of complexes both in case of two-sided expansion and in the case of one sided partite expansion. This improves and extends an earlier work of Dinur and Kaufman (FOCS 2017) and applies to matroids, and potentially many additional complexes. - Agreement tests for set systems whose sets are neighborhoods of vertices in a high dimensional expander. This family resembles the expander neighborhood family used in the gap-amplification proof of the PCP theorem. This set system is quite natural yet does not sit in a simplicial complex, and demonstrates some versatility in our proof technique. - Agreement tests on families of subspaces (also known as the Grassmann poset). This extends the classical low degree agreement tests beyond the setting of low degree polynomials. Our analysis relies on a new random walk on simplicial complexes which we call the “complement random walk” and which may be of independent interest. This random walk generalizes the non-lazy random walk on a graph to higher dimensions, and has significantly better expansion than previously-studied random walks on simplicial complexes.

We initiate the study of Boolean function analysis on high-dimensional expanders. We describe an analog of the Fourier expansion and of the Fourier levels on simplicial complexes, and generalize the FKN theorem to high-dimensional expanders. Our results demonstrate that a high-dimensional expanding complex X can sometimes serve as a sparse model for the Boolean slice or hypercube, and quite possibly additional results from Boolean function analysis can be carried over to this sparse model. Therefore, this model can be viewed as a derandomization of the Boolean slice, containing |X(k)|=O(n) points in comparison to binom{n}{k+1} points in the (k+1)-slice (which consists of all n-bit strings with exactly k+1 ones).