Improved Product-Based High-Dimensional Expanders

Understand

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})$.