Chernoff bounds for expander walks

Computer Science/Discrete Mathematics Seminar II
Topic:Chernoff bounds for expander walks
Speaker:Christopher Beck
Affiliation:Member, School of Mathematics
Date:Tuesday, March 10
Time/Room:10:30am - 12:30pm/West Bldg. Lect. Hall
Video Link:

Expander walk sampling is an important tool for derandomization. For any bounded function, sampling inputs from a random walk on an expander graph yields a sample average which is quite close to the true mean, and moreover the deviations obtained are qualitatively similar to those obtained from statistically independent samples. The "Chernoff Bound for Expander Walks" was first described by Ajtai, Komlos, and Szemeredi in 1987, and analyzed in a general form by Gilman in 1988. A significantly simpler analysis was given by Healy in 2005, who also gave a more general form in which the function may differ from step to step in a certain sense. I will give an exposition of Healy's proof and describe minor variations and extensions.