Algorithmic polynomials
Algorithmic polynomials
复制标题
DOI：
10.1145/3188745.3188958
复制
发表时间：
2018-01
期刊：
影响因子：
--
通讯作者：
Alexander A. Sherstov
中科院分区：
文献类型：
--
作者：
Alexander A. Sherstov
布尔函数f（x1，x2，.，xn）的近似次数是指在1/3以内逐点逼近f的真实的多项式的最小次数。近似度的上界在学习理论、差分隐私和算法设计中有着广泛的应用。几乎所有已知的近似度上界都是以存在的方式从量子查询复杂度的界限中产生的。我们开发了一个第一性原理，经典的方法来多项式逼近布尔函数。我们用它给出了几个基本问题的近似度的第一个构造性上界：（i）对于k-元唯一性问题为O（n3/4−1/（4（2k−1）;（ii）对于k-子集和问题为O（n1−1/（k+1））;（iii）对于任何k-DNF或k-CNF公式为O（n1−1/（k+1））;（iv）对于满射性问题为O（n3/4）。在所有情况下，我们得到明确的，封闭形式的近似多项式，是无关的量子参数从以前的工作。我们的前三个结果符合量子查询复杂性的界限。我们的第四个结果多项式地提高了问题的量子查询复杂度，并驳斥了几位专家关于满射性具有近似度Ω（n）的猜想。特别是，我们展示了第一个自然的问题，近似度和量子查询复杂性之间的多项式差距。
The approximate degree of a Boolean function f(x1,x2,…,xn) is the minimum degree of a real polynomial that approximates f pointwise within 1/3. Upper bounds on approximate degree have a variety of applications in learning theory, differential privacy, and algorithm design in general. Nearly all known upper bounds on approximate degree arise in an existential manner from bounds on quantum query complexity. We develop a first-principles, classical approach to the polynomial approximation of Boolean functions. We use it to give the first constructive upper bounds on the approximate degree of several fundamental problems: (i) O(n3/4−1/(4(2k−1))) for the k-element distinctness problem; (ii) O(n1−1/(k+1)) for the k-subset sum problem; (iii) O(n1−1/(k+1)) for any k-DNF or k-CNF formula; (iv) O(n3/4) for the surjectivity problem. In all cases, we obtain explicit, closed-form approximating polynomials that are unrelated to the quantum arguments from previous work. Our first three results match the bounds from quantum query complexity. Our fourth result improves polynomially on the Θ(n) quantum query complexity of the problem and refutes the conjecture by several experts that surjectivity has approximate degree Ω(n). In particular, we exhibit the first natural problem with a polynomial gap between approximate degree and quantum query complexity.