ECCC-Report TR16-075https://eccc.weizmann.ac.il/report/2016/075Comments and Revisions published for TR16-075en-usSat, 10 Sep 2016 05:11:22 +0300
Revision 1
| Improved Bounds on the Sign-Rank of AC$^0$ |
Mark Bun,
Justin Thaler
https://eccc.weizmann.ac.il/report/2016/075#revision1The 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.Sat, 10 Sep 2016 05:11:22 +0300https://eccc.weizmann.ac.il/report/2016/075#revision1
Paper TR16-075
| Improved Bounds on the Sign-Rank of AC$^0$ |
Mark Bun,
Justin Thaler
https://eccc.weizmann.ac.il/report/2016/075The 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.Mon, 09 May 2016 17:18:19 +0300https://eccc.weizmann.ac.il/report/2016/075