Date: October 27, 2025
Time: 3:45-5 p.m.
Location: Gates Hall 310 or via Zoom
Speaker: Avishay Tal, UC Berkley
Abstract: In this survey talk, I'll focus on a Fourier-analytic complexity measure for Boolean functions: the sum of absolute values of all level-k Fourier coefficients. Intuitively, this measure captures the ability to aggregate many weak k-fold correlations in the input and separates functions that are "sparse" and "dense" in their degree-k spectra.
Fourier sparsity at the lower levels is a pervasive property in classical computational models, like shallow circuits, decision trees, small-space algorithms, and communication protocols. Yet, it fails for most of their quantum counterparts, providing a unified way to separate quantum and classical models. A finer analysis reveals that Fourier growth can even separate quantum query algorithms with different levels of adaptivity.
Fourier growth also has applications in pseudorandomness: an explicit PRG (pseudorandom generator) fools any function with a sparse level-2 spectrum. I’ll survey these results and highlight open problems linking Fourier growth to long-standing challenges in complexity theory.
Based on several joint papers with Eshan Chattopadhyay, Uma Girish, Pooya Hatami, Shachar Lovett, Ran Raz, Omer Reingold, Makrand Sinha, and Kewen Wu.
Bio: Avishay Tal is an Associate Professor at the Department of Electrical Engineering and Computer Sciences at UC Berkeley. He earned his PhD in 2015 from the Weizmann Institute of Science and held postdoctoral positions at the Institute for Advanced Study and at Stanford University. His research interests include complexity theory, analysis of Boolean functions, quantum complexity, pseudorandomness, circuit lower bounds, and computational learning theory. He is the recipient of the NSF CAREER award, the Sloan Fellowship, STOC Best Paper Award, and ITCS Best Student Paper Award.