Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR16-075 | 10th September 2016 05:11

Improved Bounds on the Sign-Rank of AC$^0$

RSS-Feed

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} \cdot 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 AC$^0$, 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 \colon \{-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.



Changes to previous version:

Minor corrections to the proofs of Claims 2 and 3.1. We thank Lijie Chen for pointing out these issues.


Paper:

TR16-075 | 9th May 2016 15:47

Improved Bounds on the Sign-Rank of AC$^0$


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} \cdot 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 AC$^0$, 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 \colon \{-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.



ISSN 1433-8092 | Imprint