The Sign-Rank of AC^O
Alexander Alexandrovich Razborov, Alexander A. Sherstov · 2008
The sign-rank of a matrix A = [Aij] with plusmn1 entries is the least rank of a real matrix B = [Bij] with AijBij> 0 for all i, j. We obtain the first exponential lower bound on the sign-rank of a function in AC0. Namely, let f(x, y) = Lambdai=1mLambdaj=1m2(xijLambda yij). We show that the matrix [f(x, y)]x,yhas sign-rank 2Omega(m). This in particular implies that Sigma2ccnsubeUPPcc, 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 Phi1,..., Phir: {0, 1}nrarrRopf be functions such that every DNF formula f : {0, 1}nrarr {-1, +1} of polynomial size has the representation f equiv sign(a1Phi1+ hellip + arPhir) for some reals a1,..., ar. We prove that then r ges 2Omega(n1/3), which essentially matches an upper bound of 2Otilde(n1/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 AC0. This substantially generalizes and strengthens the results of Krause and Pudlak (1997).