The approximate degree of DNF and CNF formulas
The approximate degree of DNF and CNF formulas
复制标题
DOI：
10.1145/3519935.3520000
复制
发表时间：
2022-06
期刊：
影响因子：
--
通讯作者：
Alexander A. Sherstov
中科院分区：
文献类型：
--
作者：
Alexander A. Sherstov
布尔函数f∶{0,1}n→{0,1}的近似度数是一个实多项式p点逼近f的最小度数：对于所有x∈{0,1}n, |f(x)−p(x)|≤1/3。对于任意δ>0，我们构建了近似度为Ω（n1−δ）的多项式大小的DNF和CNF公式，基本上与n的平凡上界匹配。这完全解决了等深度电路（AC0）的近似度，这是一个在过去10年中得到广泛研究的问题。在我们的工作之前，只知道深度随1/δ增长的AC0电路的Ω（n1−δ）下界（Bun和Thaler， FOCS 2017）。此外，我们构建的DNF和CNF公式是最简单的，因为它们具有恒定的宽度。我们的结果给出了具有挑战性的k方数额模型和两方量子模型中多项式大小的DNF和CNF公式的有界误差通信复杂度的第一个近线性下界：分别为Ω（n/4kk2）1−δ和Ω（n1−δ），其中δ>0是任意常数。我们的下界是最优的。与上面类似，这种下界以前只知道深度随1/δ增长的AC0电路。
The approximate degree of a Boolean function f∶{0,1}n→{0,1} is the minimum degree of a real polynomial p that approximates f pointwise: |f(x)−p(x)|≤1/3 for all x∈{0,1}n. For any δ>0, we construct DNF and CNF formulas of polynomial size with approximate degree Ω(n1−δ), essentially matching the trivial upper bound of n. This fully resolves the approximate degree of constant-depth circuits (AC0), a question that has seen extensive research over the past 10 years. Prior to our work, an Ω(n1−δ) lower bound was known only for AC0 circuits of depth that grows with 1/δ (Bun and Thaler, FOCS 2017). Furthermore, the DNF and CNF formulas that we construct are the simplest possible in that they have constant width. Our result gives the first near-linear lower bounds on the bounded-error communication complexity of polynomial-size DNF and CNF formulas in the challenging k-party number-on-the-forehead model and two-party quantum model: Ω(n/4kk2)1−δ and Ω(n1−δ), respectively, where δ>0 is any constant. Our lower bounds are essentially optimal. Analogous to above, such lower bounds were previously known only for AC0 circuits of depth that grows with 1/δ.