Abstract:
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).