ECCC-Report TR08-016https://eccc.weizmann.ac.il/report/2008/016Comments and Revisions published for TR08-016en-usThu, 28 Feb 2008 18:25:58 +0200
Paper TR08-016
| The Sign-Rank of AC^0 |
Alexander Razborov,
Alexander A. Sherstov
https://eccc.weizmann.ac.il/report/2008/016The 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).
Thu, 28 Feb 2008 18:25:58 +0200https://eccc.weizmann.ac.il/report/2008/016