Fourier Growth of XOR-Fibers of Communication Protocols

Explore the Fourier growth of XOR-fibers in communication protocols through this 53-minute lecture by Uma Girish from Princeton University. Delve into the concept of Fourier growth and its applications in pseudorandomness and quantum-versus-classical separations. Examine tight bounds on Fourier growth for various function classes, including decision trees and parity decision trees. Investigate the XOR-fiber of communication protocols and its significance in studying functions associated with XOR functions. Learn about improved Fourier growth bounds for XOR-fibers of randomized protocols, including a tight O(sqrt{d}) bound for the first level and an improved O(d^{3/2}) bound for the second level. Discover the open conjecture of an optimal O(d.polylog(n)) bound. Understand the proof methodology involving martingales and the crucial concept of spectral k-wise independence. Gain insights into how imposing spectral k-wise independence on sets allows for proving bounds on level-k Fourier growth of XOR-fibers. Explore the method of adaptively partitioning large sets into spectrally k-wise independent sets.

Fourier Growth of XOR-Fibers of Communication Protocols