ECCC-Report TR21-099https://eccc.weizmann.ac.il/report/2021/099Comments and Revisions published for TR21-099en-usSun, 11 Jul 2021 10:39:29 +0300
Paper TR21-099
| Improved Product-Based High-Dimensional Expanders |
Louis Golowich
https://eccc.weizmann.ac.il/report/2021/099High-dimensional expanders generalize the notion of expander graphs to higher-dimensional simplicial complexes. In contrast to expander graphs, only a handful of high-dimensional expander constructions have been proposed, and no elementary combinatorial construction with near-optimal expansion is known. In this paper, we introduce an improved combinatorial high-dimensional expander construction, by modifying a previous construction of Liu, Mohanty, and Yang (ITCS 2020), which is based on a high-dimensional variant of a tensor product. Our construction achieves a spectral gap of $\Omega(\frac{1}{k^2})$ for random walks on the $k$-dimensional faces, which is only quadratically worse than the optimal bound of $\Theta(\frac{1}{k})$. Previous combinatorial constructions, including that of Liu, Mohanty, and Yang, only achieved a spectral gap that is exponentially small in $k$. We also present reasoning that suggests our construction is optimal among similar product-based constructions.Sun, 11 Jul 2021 10:39:29 +0300https://eccc.weizmann.ac.il/report/2021/099