Computer Science/Discrete Mathematics Seminar I

Expander Random Walks: A Fourier-Analytic Approach

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.

Date & Time

September 20, 2021 | 11:15am – 12:15pm

Location

Simonyi Hall 101 and Remote Access

Speakers

Speaker Affiliation

Tel Aviv University