Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC^0

Abstract

The threshold degree of a Boolean function $f:\{0,1{\}}^n\to \{0,1\}$ is the minimum degree of a real polynomial $p$ that represents $f$ in sign: $\mathrm{sgn}p(x)=(-1{)}^{f(x)}.$ A related notion is sign-rank, defined for a Boolean matrix $F=[F_{ij}]$ as the minimum rank of a real matrix $M$ with $\mathrm{sgn}{M}_{ij}=(-1{)}^{F_{ij}}$. Determining the maximum threshold degree and sign-rank achievable by constant-depth circuits (${\text{AC}}^0$) is a well-known and extensively studied open problem, with complexity-theoretic and algorithmic applications. We give an essentially optimal solution to this problem. For any $\epsilon >0,$ we construct an ${\text{AC}}^0$ circuit in $n$ variables that has threshold degree $\Omega (n^{1-\epsilon })$ and sign-rank $\exp (\Omega (n^{1-\epsilon })),$ improving on the previous best lower bounds of $\Omega (\sqrt{n})$ and $\exp (\tilde{\Omega }(\sqrt{n}))$, respectively. Our results subsume all previous lower bounds on the threshold degree and sign-rank of ${\text{AC}}^0$ circuits of any given depth, with a strict improvement starting at depth $4$. As a corollary, we also obtain near-optimal bounds on the discrepancy, threshold weight, and threshold density of ${\text{AC}}^0$, strictly subsuming previous work on these quantities. Our work gives some of the strongest lower bounds to date on the communication complexity of ${\text{AC}}^0$.

99 pages