PACM Colloquium: Nikhil Srivastava, UC Berkeley

A Matrix Expander Chernoff Bound

The Matrix Chernoff Bound asserts that a sum of independent bounded random matrices concentrates around its mean. We prove a conjecture of Wigderson and Xiao, asserting that the same conclusion is true when the matrices are not independent, but sampled according to a random walk on a Markov chain with a spectral gap (i.e., an expander graph). This implies a black-box derandomization of many applications of the matrix Chernoff bound. A key ingredient in the proof is a multi-matrix extension of the Golden-Thompson inequality, based on the work of Sutter et al., which relates the trace of the matrix exponential of a sum of many matrices to a the trace of the product of their exponentials.

Joint work with Ankit Garg, Yin Tat Lee, and Zhao Song. 

Nikhil is an assistant professor in the mathematics department at UC Berkeley. He received his PhD in computer science from Yale in 2010, advised by Daniel Spielman, and his BS from Union College in 2005. After postdocs at the IAS, Princeton, and MSRI, he spent two and a half years as a researcher at Microsoft Research India, before coming to Berkeley. He is currently interested in algorithms, spectral graph theory, random matrices, and the geometry of polynomials.