Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC$^0$
| Autor: | Pei Wu, Alexander A. Sherstov |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
FOS: Computer and information sciences
Polynomial (hyperelastic model) General Computer Science Degree (graph theory) General Mathematics 020206 networking & telecommunications 0102 computer and information sciences 02 engineering and technology Computational Complexity (cs.CC) 01 natural sciences Combinatorics Computer Science - Computational Complexity 010201 computation theory & mathematics 0202 electrical engineering electronic engineering information engineering Rank (graph theory) Communication complexity Boolean function Mathematics Sign (mathematics) |
| Zdroj: | SIAM Journal on Computing. 52:STOC19-1 |
| ISSN: | 1095-7111 0097-5397 |
| DOI: | 10.1137/20m1312459 |
| Popis: | The threshold degree of a Boolean function $f\colon\{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}$. Comment: 99 pages |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|