STOC2023

New High Dimensional Expanders from Covers

Yotam Dikstein

4 citations

Abstract

We present a new construction of high dimensional expanders based on covering spaces of simplicial complexes. High dimensional expanders (HDXs) are hypergraph analogues of expander graphs. They have many uses in theoretical computer science, but unfortunately only few constructions are known which have arbitrarily small local spectral expansion.