Computer Science/Discrete Mathematics Seminar I

Chernoff-type bounds study concentration of sums of independent random variables and are extremely useful in various settings. In many settings, the random variables may not be completely independent but only have limited independence. One such setting, which turns out to be useful in derandomization and theoretical computer science, in general, involves random walks on expanders. I will talk about a Chernoff-type bound for sums of matrix-valued random variables sampled via a random walk on an expander. Our proof is based on a new multi-matrix extension of the Golden-Thompson inequality which improves in some ways a recent inequality due to Sutter et al. and may be of independent interest, as well as an adaptation of an argument for the scalar case due to Healy. Based on joint work with Yin Tat Lee, Zhao Song and Nikhil Srivastava.