TR08-016 Authors: Alexander Razborov, Alexander A. Sherstov

Publication: 28th February 2008 18:25

Downloads: 1288

Keywords:

The sign-rank of a matrix A=[A_{ij}] with +/-1 entries

is the least rank of a real matrix B=[B_{ij}] with A_{ij}B_{ij}>0

for all i,j. We obtain the first exponential lower bound on the

sign-rank of a function in AC^0. Namely, let

f(x,y)=\bigwedge_{i=1}^m\bigvee_{j=1}^{m^2} (x_{ij}\wedge y_{ij}).

We show that the matrix [f(x,y)]_{x,y} has sign-rank 2^{Omega(m)}.

This in particular implies that Sigma_2^{cc}\not\subseteq UPP^{cc},

which solves a long-standing open problem posed by Babai, Frankl,

and Simon (1986).

Our result additionally implies a lower bound in learning theory.

Specifically, let phi_1,...,phi_r : {0,1}^n -> R be functions

such that every DNF formula f:{0,1}^n->{+1,-1} of polynomial size has

the representation f=sign(a_1*phi_1+...+a_r*phi_r) for

some reals a_1,...,a_r. We prove that then r> 2^{Omega(n^{1/3})},

which essentially matches an upper bound of 2^{tilde O(n^{1/3})}

due to Klivans and Servedio (2001).

Finally, our work yields the first exponential lower bound on the

size of threshold-of-majority circuits computing a function

in AC^0. This substantially generalizes and strengthens the

results of Krause and Pudlak (1997).