Unbounded-Error Communication Complexity of Symmetric Functions

The sign-rank of a real matrix M is the least rank of a matrix R in which every entry has the same sign as the corresponding entry of M. We determine the sign-rank of every matrix of the form M = [ D(|x ∧ y|)]x,y, where D: {0, 1,..., n} → {−1,+1} is given and x and y range over {0, 1}n. Specifically, we prove that the sign-rank of M equals 2 ˜Θ(k), where k is the number of times D changes sign in {0, 1,..., n}. Put differently, we prove an optimal lower bound on the unbounded-error communication complexity of every symmetric function, i.e., a function of the form f (x, y) = D(|x ∧ y|) for some D. The unbounded-error model is essentially the most powerful of all 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. As corollaries to our result, we give new lower bounds for PAC learning and for threshold-of-majority circuits. The technical content of our proof is diverse and features random walks on Zn2, discrete approximation theory, the Fourier transform on Zn2, linear-programming duality, and matrix analysis