The approximate degree of DNF and CNF formulas

DOI10.1145/3519935.3520000MaRDI QIDQ6083572zbMATH OpenWikidataFDO

Authors Alexander A. Sherstov

Publication date 8 December 2023

Published in Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2209.01584

zbMATH Keywords

AC\(^0\)approximate degreeCNF formulascommunication complexityconstant-depth circuitsDNF formulasnumber-on-the-Forehead modelpolynomial approximationquantum communication

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: The approximate degree of a Boolean function $fcolon{0,1}^{n}o0,1$ is the minimum degree of a real polynomial $p$ that approximates $f$ pointwise: $|f(x)-p(x)|leq1/3$ for all $xin{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 ($ext{AC}^0$), a question that has seen extensive research over the past 10 years. Previously, an $Omega(n^{1-delta})$ lower bound was known only for $ext{AC}^0$ circuits of depth that grows with $1/delta$ (Bun and Thaler, FOCS 2017). Moreover, our CNF and DNF formulas are the simplest possible in that they have constant width. Our result holds even for one-sided approximation, and has the following further consequences. (i) We essentially settle the communication complexity of $ext{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 $ext{coNP}_k$ can be separated essentially optimally from $ext{NP}_k$ and $ext{BPP}_k$ by a particularly simple function, a polynomial-size constant-width CNF. (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 $egf$.

Cited in

(1)

• Parity vs. \(\text{AC}^0\) with simple quantum preprocessing

This page was built for publication: The approximate degree of DNF and CNF formulas

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6083572)