Kaufman, Tali ;
Sharakanski, Ella
Chernoff Bound for HighDimensional Expanders
Abstract
We generalize the expander Chernoff bound to highdimensional expanders. The expander Chernoff bound is an essential property of expanders, first proved by Gillman [Gillman, 1993]. Given a graph G and a function f on the vertices, it states that the probability of f’s mean sampled via a random walk on G to deviate from its actual mean, has a bound that depends on the spectral gap of the walk and decreases exponentially as the walk’s length increases.
We are interested in obtaining an analog Chernoff bound for high order walks on highdimensional expanders. A naive generalization of the expander Chernoff bound from expander graphs to highdimensional expanders gives a very poor bound due to obstructions that occur in highdimensional expanders and are not present in (onedimensional) expander graphs. Because of these obstructions, the spectral gap of highorder random walks is inherently small.
A natural question that arises is how to get a meaningful Chernoff bound for highdimensional expanders. In this paper, we manage to get a strong Chernoff bound for highdimensional expanders by looking beyond the spectral gap.
First, we prove an expander Chernoff bound that depends on a notion that we call the "shrinkage of a function" instead of the spectral gap. In onedimensional expanders, the shrinkage of any function with zeromean is bounded by λ(M). Therefore, the spectral gap is just the onedimensional manifestation of the shrinkage.
Next, we show that in good highdimensional expanders, the shrinkage of functions that "do not come from below" is good. A function does not come from below if from any local point of view (called "link") its mean is zero.
Finally, we prove a highdimensional Chernoff bound that captures the expansion of the complex. When the function on the faces has a small variance and does not "come from below", our bound is better than the naive highdimensional expander Chernoff bound.
BibTeX  Entry
@InProceedings{kaufman_et_al:LIPIcs:2020:12628,
author = {Tali Kaufman and Ella Sharakanski},
title = {{Chernoff Bound for HighDimensional Expanders}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
pages = {25:125:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771641},
ISSN = {18688969},
year = {2020},
volume = {176},
editor = {Jaros{\l}aw Byrka and Raghu Meka},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12628},
URN = {urn:nbn:de:0030drops126287},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2020.25},
annote = {Keywords: High Dimensional Expanders, Random Walks, Tail Bounds}
}
11.08.2020
Keywords: 

High Dimensional Expanders, Random Walks, Tail Bounds 
Seminar: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)

Issue date: 

2020 
Date of publication: 

11.08.2020 