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. 160724 Abstract Fourier growth of a Boolean function refers to the growth of the sum of absolute values of the levelk Fourier coeď¬€icients. Upper bounds on the Fourier growth, even for the first few levels, have important applications in pseudorandomness, learning theory, circuit lower bounds and quantumversusclassical 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 pointwise 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 XORfiber 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 XORfibers 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 kwise independence. We also provide a way of adaptively partitioning a large set into a few spectrally kwise independent subsets. This is based on a joint work with Makrand Sinha, Avishay Tal and Kewen Wu.
