The Unbounded-Error Communication Complexity of Symmetric Functions

Alexander Sherstov
The University of Texas at Austin

Friday, April 4 at 10:50am
CSE 3941


ABSTRACT:

We prove an essentially tight lower bound on the unbounded-error communication complexity of every symmetric function, i.e., f(x,y)=D(|x AND y|), where D:{0,1,...,n}->{0,1} is given and x,y range over {0,1}^n. Specifically, we show that the communication complexity of f equals the number of sign changes of D in {0,1,...,n}, to within a polylogarithmic factor. The unbounded-error model is the most powerful of the standard models of communication (both classical and quantum), and proving lower bounds in it is a substantial challenge. The only previous nontrivial lower bounds for this model appear in the groundbreaking work of Forster (2001) and its extensions.

The technical content of this work is diverse and features random walks on (Z_2)^n, discrete approximation theory, the Fourier transform on (Z_2)^n, and linear-programming duality.