Computer Science/Discrete Mathematics Seminar I

A random walk on expanders, despite its strong underlying correlations, poses extremely useful pseudorandom properties. The expander hitting property and the expander Chernoff are two such classic examples. That is, the AND function and certain interval indicator functions are "fooled" by expander random walks. More recently, Ta-Shma proved that even the highly sensitive parity function is fooled by expander random walks.

What about other "test" functions? We prove that all symmetric functions are fooled by expander random walks, yielding a central limit theorem for expander random walks with respect to the total variation distance. Our approach is Fourier analytic, and as such, it allows us to go beyond symmetric functions. We show that sufficiently good expanders fool bounded-depth circuits, bounded-width read-once branching programs, and so forth.

Based on joint works with Peri and Ta-Shma, and with Minzer, Peleg, Potechin and Ta-Shma.