Pseudorandomness Seminar

Matrix Concentration for Expander Walks

We prove a Chernoff-type bound for sums of matrix-valued random variables sampled via a random walk on an expander, confirming a conjecture of Wigderson and Xiao up to logarithmic factors in the deviation parameter. This allows one to derandomize certain applications of the matrix Chernoff bound, going roughly from klog(n) to k+log(n) bits as in the scalar case.