Spring 2017

Pseudorandomness Seminar

Tuesday, April 18th, 2017, 4:30 pm5: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.