Events
Spring 2017
![](https://old.simons.berkeley.edu/sites/default/files/styles/workshop_main/public/pseudo_placeholder_final.png?itok=6hVd5UbS)
Pseudorandomness Seminar
Tuesday, April 18th, 2017, 4:30 pm–5:30 pm
Parent Program:
Speaker:
Location:
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.