Abstract
The Fourier growth of a function refers to the growth of the sum of absolute values of the level-k Fourier coefficients. Bounds on the Fourier growth, even for the first few levels, have important applications in pseudorandomness and quantum-versus-classical separations. Tight bounds on the Fourier growth have been studied for many classes of functions, including decision trees and parity decision trees.
We study the Fourier growth of functions associated to communication protocols for XOR functions (functions evaluated on the point-wise XOR of Alice's and Bob's inputs). If a protocol C computes an XOR function, then C(x,y) is a function of x + y. This motivates us to study the XOR-fiber of the communication protocol C, defined as h(z) := E[C(x,y)|x + y = z]. These functions form a powerful class which includes decision trees and parity decision trees. Proving tight bounds on the Fourier growth of XOR fibers also 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 protocols that communicate 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.