2023/05/04 by Louis Golowich, Golowich, Louis
Biochemistry, Genetics and Molecular Biology · Computer Science · #05C48 #05C65 #Coding theory and cryptography #Combinatorics (math.CO) #DNA and Biological Computing #Discrete Mathematics (cs.DM) #Error Correcting Code Techniques #FOS: Computer and information sciences #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.2305.02512
openalex publication_date 2023/05/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper, we present a new construction of simplicial complexes of subpolynomial degree with arbitrarily good local spectral expansion. Previously, the only known high-dimensional expanders (HDXs) with arbitrarily good expansion and less than polynomial degree were based on one of two constructions, namely Ramanujan complexes and coset complexes. In contrast, our construction is a Cayley complex over the group \mathbbF2k, with Cayley generating set given by a Grassmannian HDX. Our construction is in part motivated by a coding-theoretic interpretation of Grassmannian HDXs that we present, which provides a formal connection between Grassmannian HDXs, simplicial HDXs, and LDPC codes. We apply this interpretation to prove a general characterization of the 1-homology groups over \mathbbF2 of Cayley simplicial complexes over \mathbbF2k. Using this result, we construct simplicial complexes on N vertices with arbitrarily good local expansion for which the dimension of the 1-homology group grows as Ω(log2N). No prior constructions in the literature have been shown to achieve as large a 1-homology group.