Spring 2017

Pseudorandomness Seminar

Apr 18, 2017 4:30 pm – 5:30 pm 

Add to Calendar

Parent Program: 

Calvin Lab Room 116

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.