ECCC-Report TR23-065https://eccc.weizmann.ac.il/report/2023/065Comments and Revisions published for TR23-065en-usTue, 26 Dec 2023 03:39:54 +0200
Revision 1
| From Grassmannian to Simplicial High-Dimensional Expanders |
Louis Golowich
https://eccc.weizmann.ac.il/report/2023/065#revision1 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 $\mathbb{F}_2^k$, 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 $\mathbb{F}_2$ of Cayley simplicial complexes over $\mathbb{F}_2^k$. 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 $\Omega(\log^2N)$. No prior constructions in the literature have been shown to achieve as large a 1-homology group.Tue, 26 Dec 2023 03:39:54 +0200https://eccc.weizmann.ac.il/report/2023/065#revision1
Paper TR23-065
| From Grassmannian to Simplicial High-Dimensional Expanders |
Louis Golowich
https://eccc.weizmann.ac.il/report/2023/065 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 $\mathbb{F}_2^k$, 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 $\mathbb{F}_2$ of Cayley simplicial complexes over $\mathbb{F}_2^k$. 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 $\Omega(\log^2N)$. No prior constructions in the literature have been shown to achieve as large a 1-homology group.Thu, 04 May 2023 16:54:49 +0300https://eccc.weizmann.ac.il/report/2023/065