Small set expansion in high dimensional expanders is of great importance, e.g., towards
proving cosystolic expansion, local testability of codes and constructions of good quantum
codes.
In this work we improve upon the state of the art results of small set expansion in high
dimensional expanders. Our improvement is either on the expansion quality or on the size
of sets for which expansion is guaranteed.
One line of previous works [KM22, DD24] has obtained weak expansion for small sets,
which is sufficient for deducing cosystolic expansion of one dimension below. We improve
upon their result by showing strong expansion for small sets.
Another line of works [KKL14, EK16, KM21] has shown strong expansion for small sets.
However, they obtain it only for very small sets. We get an exponential improvement on
the size of sets for which expansion is guaranteed by these prior works.
Interestingly, our result is obtained by bridging between these two lines of works. The
works of [KM22, DD24] use global averaging operators in order to obtain expansion for
larger sets. However, their method could be utilized only on sets that are cocycle-like. We
show how to combine these global averaging operators with ideas from the so-called “fat
machinery” of [KKL14, EK16, KM21] in order to apply them for general sets.
Make this part of your paper trail
Save this paper to a shelf, write a review, and keep your own notes.