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 AND 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^{\tilde Theta(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 AND 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 (Z_2)^n, discrete approximation theory,
the Fourier transform on (Z_2)^n, linear-programming duality,
and matrix analysis.