Abstract:
Expanders are graphs that are both edge-sparse and well connected. They have been an instrumental tool in many results in mathematics and computer science, some of which seem to have little connection to graphs at all. High dimensional expanders (HDXs) are hypergraph analogues of expander graphs — sparse and well connected hypergraphs. HDXs have already played a key role in several recent results in theoretical computer science and combinatorics. However, much of their underlying theory remains unexplored.
Motivated by this, we will see what HDXs are, why they generalize expander graphs, and how they serve as a common setting for results in probability and computational complexity. In particular, we will how high dimensional expanders give rise to new Chernoff-type inequalities for HDXs, and also some applications to questions in computational complexity.
The talk will not assume prior background in complexity theory and is aimed at a broad audience.