TR07-112 Authors: Alexander A. Sherstov

Publication: 12th November 2007 21:53

Downloads: 1289

Keywords:

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.