Event Series
Event Type
Wednesday, March 6, 2024 12:30 PM
Joseph Sloth (Caltech)

Degree-d multivariate polynomials over small finite fields are of central importance in theoretical computer science. And yet they retain many mysteries; for example, their Fourier spectra are very poorly understood. We will discuss the so-called "Fourier growth" of such functions, or the ℓ₁ norm of the level-k Fourier coefficients as a function of kd, and the number of variables. We will survey what is known about this quantity and explain how certain bounds on Fourier growth imply progress on one of the central open problems in complexity theory: are randomized algorithms any more powerful than deterministic ones?