A Simple Sub-Polynomial Degree Coboundary Expander
This work simplifies the construction of high-dimensional expanders with strong expansion properties, which are crucial for PCP and coding theory, replacing a highly complex algebraic construction with a simple combinatorial one.
The authors present a simple combinatorial construction of a high-dimensional expander that is both a local spectral expander and a coboundary expander, achieving sub-polynomial degree. This yields the first near-linear size hypergraphs with good agreement tests in the '1%' regime and a simple PCP construction with near-linear size.
High dimensional expanders simultaneously satisfying spectral and combinatorial (coboundary) expansion have recently played a major role in breakthroughs in PCP and coding theory, but the only known construction of such complexes is extremely involved, requiring deep algebraic number theory. In this work, we give an extremely simple combinatorial construction of a sub-polynomial degree complex based on projections of the flags complex (subspace chains) that is (i) a local spectral expander, (ii) a coboundary expander, and (iii) a swap coboundary expander. As a corollary, we also give the first near-linear size combinatorial hypergraphs with good agreement tests in the '1%' regime, and a simple PCP construction with near-linear size.