论文标题
DNF和CNF公式的近似程度
The Approximate Degree of DNF and CNF Formulas
论文作者
论文摘要
The 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 $δ> 0，$我们构建了多项式大小的CNF和DNF公式，大约$ω（n^{1-δ}），$与$n。$相匹配。以前，$ω（n^{1-δ}）$下限仅以$ \ text {ac}^0 $深度电路，其深度为$ 1/δ$（BUN和THALER，FOCS 2017）。此外，我们的CNF和DNF公式是最简单的，因为它们具有恒定的宽度。我们的结果甚至可以单方面近似，并且具有以下进一步的后果。 （i）我们本质上解决了$ \ text {ac}^0 $ coussuits在有限的量子量子模型中的通信复杂性，$ k $ -k $ - 零件数字随机模型和$ k $ -party-the-the-the-the-the-the-the-the-the-the-the-the-the-the-the-the-the-the-the-the-the-the-the-the-the-the-thehead-head-head-head-head-head nonderministic模型$ω（n/4^kk^2）^{1-δ} $和$ω（n/4^kk^2）^{1-δ} $，即使对于多项式尺寸恒定宽度CNF CNF公式，也可以进行交流。 （ii）尤其是，我们表明，多阶通通信类$ \ text {conp} _k $基本上可以与$ \ text {np} _k $和$ \ text {bpp} _k $通过特别简单的函数，一个特别简单的函数，一个多项式尺寸的常数宽度cnf。 （iii）我们给出了$（1）$对$ω（n^{1-δ}）$的基本紧密分离，对于函数的单侧与两侧近似程度；和$ o（1）$ vess $ω（n^{1-δ}）$对于函数$ f $的单侧近似度与其否定$ \ neg f $。
The 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 $δ>0,$ we construct CNF and DNF formulas of polynomial size with approximate degree $Ω(n^{1-δ}),$ 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. Previously, an $Ω(n^{1-δ})$ lower bound was known only for $\text{AC}^0$ circuits of depth that grows with $1/δ$ (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 $\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 $δ>0$, these models require $Ω(n^{1-δ})$, $Ω(n/4^kk^2)^{1-δ}$, and $Ω(n/4^kk^2)^{1-δ}$, 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. (iii) We give an essentially tight separation, of $O(1)$ versus $Ω(n^{1-δ})$, for the one-sided versus two-sided approximate degree of a function; and $O(1)$ versus $Ω(n^{1-δ})$ for the one-sided approximate degree of a function $f$ versus its negation $\neg f$.
