[Proof Complexity] MIAO seminar Mon Jan 29 at 16:00 with Uma Girish: Fourier growth of communication protocols for XOR functions

[Jakob Nordström]

Dear all,

On Monday January 29 at 16:00 CET (please note the time!) we will have the opportunity to enjoy a seminar with Uma Girish from Princeton University, who will give a talk titled "Fourier growth of communication protocols for XOR functions". You find the abstract at the bottom of this message.

This will be a video seminar at https://lu-se.zoom.us/j/61925271827. Please feel free to share this information with colleagues who you think might be interested. We are also hoping to record the seminar and post on the MIAO Research YouTube channel https://youtube.com/@MIAOresearch for people who would like to hear the talk but cannot attend.

Most of our seminars consist of two parts: first a 50-55-minute regular talk, and then after a break a ca-1-hour in-depth technical presentation with (hopefully) a lot of interaction. The intention is that the first part of the seminar will give all listeners a self-contained overview of some exciting research results, and after the break people who have the time and interest will get an opportunity to really get into the technical details. (However, for those who feel that the first part was enough, it is perfectly fine to just discretely drop out during the break. No questions asked; no excuses needed.)

More information about upcoming MIAO seminars can be found at https://jakobnordstrom.se/miao-seminars/. If you do not wish to receive these announcements, or receive several copies of them, please send a message to jn at di.ku.dk.

Best regards,
Jakob Nordström

P.S. Apologies for any multiple copies you might receive of this announcement --- the seminar mailing list is not feeling very well right now.

**********

Monday Jan 29 at 16:00 CET (note the time!) on Zoom
Fourier growth of communication protocols for XOR functions
(Uma Girish, Princeton University)

Fourier growth of a Boolean function refers to the growth of the sum of absolute values of the level-k Fourier coefficients. Intuitively, functions with small Fourier growth cannot aggregate many weak signals in the input to obtain a considerable effect on the output. 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. Tight bounds on the Fourier growth have been extensively studied for various computational models, including AC0 circuits, branching programs, decision trees and parity decision trees.

We study the Fourier growth of functions associated with communication protocols. In our 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) while minimizing the amount of communication. Such communication problems are referred to as XOR functions and are central in the field of communication complexity. 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]. XOR-fibers of communication protocols form a powerful class of functions, which includes decision trees and parity decision trees. Proving tight bounds on the Fourier growth of XOR-fibers has applications to the Gap-Hamming problem and improved quantum versus classical separations in communication complexity.

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. One crucial ingredient we use to control the step sizes is a spectral notion of k-wise independence. Loosely speaking, this corresponds to sets such that the k-th moments of the uniform distribution on the set are well-behaved in all directions. We show how imposing spectral k-wise independence on Alice's and Bob's sets allows us to prove bounds on the level-k Fourier growth of XOR-fibers. We also provide a way of adaptively partitioning a large set into a few spectrally k-wise independent sets.


Jakob Nordström, Professor
University of Copenhagen and Lund University
Phone: +46 70 742 21 98 / +45 28 78 38 11
https://jakobnordstrom.se