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.