Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR21-099 | 4th July 2021 06:32

Improved Product-Based High-Dimensional Expanders


Authors: Louis Golowich
Publication: 11th July 2021 10:39
Downloads: 516


High-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.

ISSN 1433-8092 | Imprint