High Dimensional Expanders and Chernoff Inequalities

Chernoff’s inequality is one of the most basic inequalities in probability theory. It states that the sum of independent random variables is close to its mean with very high probability. The `Expander-Graph Chernoff inequality’, proven by Ajtai, Komlos, and Szemeredi in 1987, is a powerful extension of Chernoff’s inequality, asserting that Chernoff’s inequality holds even when sampling the random variables using paths in an expander graph instead of sampling them independently.

In this talk, we will discuss further extensions and generalizations of Chernoff’s inequality coming from high dimensional expanders. High dimensional expanders are sparse hypergraphs exhibiting pseudo-random properties. These are more sophisticated structures than the expander graphs of [AKS], but in return the generalization of Chernoff’s bound obtained from them applies in a far more general setup.

We will see why Chernoff-type bounds hold for high dimensional expanders, and how this inequality arises naturally in problems in high dimensional geometry and computational complexity.

This is based on joint work with Max Hopkins. The talk will not assume prior background in complexity theory and is aimed at a broad audience.