Chernoff bounds for High dimensional Expanders
SEMINARS: HARVARD-MIT COMBINATORICS
The classical Chernoff’s inequality states that for any set $A \subseteq [n]$, the random variable $|A \cap S|$ is well concentrated around its mean when S is chosen as a random set of k elements from [n]. The `Expander-Graph Chernoff’ inequality, proven by Ajtai, Komlos, and Szemeredi in 1987, is a powerful derandomization of Chernoff’s inequality. It asserts that the set S can be chosen from a much smaller collection of k-tuples – paths of an expander graph.
In this talk, we will discuss further derandomizations of Chernoff’s bound coming from high dimensional expanders. High dimensional expanders are sparse collections of subsets of [n] 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 how basic tools such as Chernoff-type bounds and reverse hypercontractivity hold for high dimensional expanders. Time permitting, we will discuss some applications of this Chernoff bound to PCPs, property testing and high dimensional geometry.
This talk is based on joint work with Max Hopkins.
For information about the Richard P. Stanley Seminar in Combinatorics, visit https://math.mit.edu/combin/