Abstract:
The sign-rank of a matrix A with entries in {-1, +1}$ is the least rank of a real matrix B with A_{ij} *B_{ij} > 0 for all i, j.
Razborov and Sherstov (2008) gave the first exponential lower bounds on the sign-rank of a function in \acz, answering an old question of Babai, Frankl, and Simon (1986).
Specifically, they exhibited a matrix A=[F(x, y)]_{x, y} for a specific function F: {-1, 1}^n \times {-1, 1}^n \rightarrow {-1, 1}$ in AC^0, such that A has sign-rank exp(Omega(n^{1/3})).
We prove a generalization of Razborov and Sherstov's result, yielding exponential sign-rank lower bounds for a non-trivial class of functions (that includes
the function used by Razborov and Sherstov).
As a corollary of our general result, we improve Razborov and Sherstov's lower bound on the sign-rank of AC^0 from exp(Omega(n^{1/3})) to exp(\tilde{Omega}(n^{2/5})).
We also describe several applications to communication complexity, learning theory, and circuit complexity.
Versions: