Yotam Dikstein (IAS) – High Dimensional Expanders: Structure and Applications

Title: High Dimensional Expanders: Structure and Applications

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.

I will illustrate their power by presenting new Chernoff-type inequalities for HDXs and explaining their applications to:

1. Hardness amplification – constructing functions for which the best polynomial-time algorithm performs no better than random guessing.

2. Hardness of approximation – constructing natural problems for which even approximate solutions are intractable unless P=NP.

The talk will not assume prior background and is aimed at a broad audience.