ECCC-Report TR22-123https://eccc.weizmann.ac.il/report/2022/123Comments and Revisions published for TR22-123en-usMon, 05 Sep 2022 07:49:37 +0300
Paper TR22-123
| The Approximate Degree of DNF and CNF Formulas |
Alexander A. Sherstov
https://eccc.weizmann.ac.il/report/2022/123The approximate degree of a Boolean function $f\colon\{0,1\}^n\to\{0,1\}$ is the minimum degree of a real polynomial $p$ that approximates $f$ pointwise: $|f(x)-p(x)|\leq1/3$ for all $x\in\{0,1\}^n.$ For every $\delta>0,$ we construct CNF and DNF formulas of polynomial size with approximate degree $\Omega(n^{1-\delta}),$ essentially matching the trivial upper bound of $n.$ This improves polynomially on previous lower bounds and fully resolves the approximate degree of constant-depth circuits ($\text{AC}^{0}$), a question that has seen extensive research over the past 10 years. Prior to our work, an $\Omega(n^{1-\delta})$ lower bound was known only for $\text{AC}^{0}$ circuits of depth that grows with $1/\delta$ (Bun and Thaler, FOCS 2017). Furthermore, the CNF and DNF formulas that we construct are the simplest possible in that they have constant width. Our result holds even for one-sided approximation: for any $\delta>0$, we construct a polynomial-size constant-width CNF formula with one-sided approximate degree $\Omega(n^{1-\delta})$.
Our work has the following consequences.
(i) We essentially settle the communication complexity of $\text{AC}^{0}$ circuits in the bounded-error quantum model, $k$-party number-on-the-forehead randomized model, and $k$-party number-on-the-forehead nondeterministic model: we prove that for every $\delta>0$, these models require $\Omega(n^{1-\delta})$, $\Omega(n/4^{k}k^{2})^{1-\delta}$, and $\Omega(n/4^{k}k^{2})^{1-\delta}$, respectively, bits of communication even for polynomial-size constant-width CNF formulas.
(ii) In particular, we show that the multiparty communication class $\text{coNP}_{k}$ can be separated essentially optimally from $\text{NP}_{k}$ and $\text{BPP}_{k}$ by a particularly simple function, a polynomial-size constant-width CNF formula.
(iii) We give an essentially tight separation, of $O(1)$ versus $\Omega(n^{1-\delta})$, for the one-sided versus two-sided approximate degree of a function; and $O(1)$ versus $\Omega(n^{1-\delta})$ for the one-sided approximate degree of a function $f$ versus its negation $\neg f$.
Our proof departs significantly from previous approaches and contributes a novel, number-theoretic method for amplifying approximate degree.Mon, 05 Sep 2022 07:49:37 +0300https://eccc.weizmann.ac.il/report/2022/123