|
Computer Science Seminar Speaker: Uma Girish, Princeton University Date: Tuesday, 16 July 2024 Time: 2:15 PM Venue: Seminar Hall, CMI Fourier Growth for Communication Protocols for XOR functions Uma Girish Princeton University. 16-07-24 Abstract Fourier growth of a Boolean function refers to the growth of the sum of absolute values of the level-k Fourier coefficients. Upper bounds on the Fourier growth, even for the first few levels, have important applications in pseudorandomness, learning theory, circuit lower bounds and quantum-versus-classical separations. We study the Fourier growth of functions associated with communication protocols for XOR problems. In this setting, Alice gets a bitstring x and Bob gets a bitstring y, and together they wish to compute a Boolean function that only depends on x+y (the point-wise Alice's and Bob's inputs). If a protocol C computes an XOR function, then the output C(x,y) of the protocol is a function of x + y. This motivates us to study the XOR-fiber H of a communication protocol C defined by H(z) := E[ C(x,y) | x + y = z]. In this talk, we present improved Fourier growth bounds for the XOR-fibers of randomized communication protocols that communicate at most d bits. For the first level, we show a tight O(sqrt{d}) bound. For the second level, we show an improved O(d^{3/2}) bound. We conjecture that the optimal bound is O(d.polylog(n)) and this is an open question. Our proof relies on viewing the protocol and its Fourier spectrum as a martingale using a geometric perspective. One crucial ingredient we use to control the step sizes of the martingale is a spectral notion of k-wise independence. We also provide a way of adaptively partitioning a large set into a few spectrally k-wise independent subsets. This is based on a joint work with Makrand Sinha, Avishay Tal and Kewen Wu.
|
