Algorithmic polynomials

DOI10.1145/3188745.3188958MaRDI QIDQ5230299zbMATH OpenOpenAlexFDO

Authors Alexander A. Sherstov

Publication date 22 August 2019

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

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

zbMATH Keywords

\(k\)-CNF formulas\(k\)-DNF formulas\(k\)-element distinctness problem\(k\)-subset sum problemapproximate degreequantum query complexitysurjectivity problem

Mathematics Subject Classification ID

Boolean functions (06E30) Quantum algorithms and complexity in the theory of computing (68Q12)

Abstract: The approximate degree of a Boolean function $f(x_1,x_2,ldots,x_n)$ 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: - $$ for the $k$-element distinctness problem; - $O(n^{1-frac1k+1})$ for the $k$-subset sum problem; - $O(n^{1-frac1k+1})$ for any $k$-DNF or $k$-CNF formula; - $O(n^{3/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 $Theta(n)$ quantum query complexity of the problem and refutes the conjecture by several experts that surjectivity has approximate degree $Omega(n)$. In particular, we exhibit the first natural problem with a polynomial gap between approximate degree and quantum query complexity.

Recommendations

• Algorithmic Polynomials
• scientific article; zbMATH DE number 1296286
• Polynomial algorithms in computer algebra
• Algorithms for polynomials in two variables
• Polynomial decomposition algorithms
• Polynomial decomposition algorithms
• Algorithmic properties of polynomial rings
• scientific article; zbMATH DE number 4092769
• Algorithms related to the decomposition of polynomials

Cited in

(27)

• Polynomial algorithms in computer algebra
• An algorithmic characterization of polynomial functions over \(\mathbb Z_{p^n}\)
• Algorithmic problems for differential polynomial algebras
• Algorithms with polynomial interpretation termination proof
• Dual polynomials for collision and element distinctness
• An explicit VC-theorem for low-degree polynomials
• Algorithms for Symbolic Polynomials
• Code Generation for Polynomial Multiplication
• scientific article; zbMATH DE number 3987032 (Why is no real title available?)
• Lower bounds for the approximate degree of block-composed functions
• scientific article; zbMATH DE number 1929311 (Why is no real title available?)
• Approximate Degree in Classical and Quantum Computing
• Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization
• Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximity
• scientific article; zbMATH DE number 7561760 (Why is no real title available?)
• A nearly optimal lower bound on the approximate degree of \(\mathrm{AC}^0\)
• Algorithmic Polynomials
• The polynomial method strikes back: tight quantum query bounds via dual polynomials
• The polynomial method strikes back: tight quantum query bounds via dual polynomials
• On the sum-of-squares degree of symmetric quadratic functions
• Variation on Euclid's algorithm for polynomials
• Approximate degree, weight, and indistinguishability
• scientific article; zbMATH DE number 7651029 (Why is no real title available?)
• Algorithm for computing the truncation of the discriminant of a polynomial
• scientific article; zbMATH DE number 7716601 (Why is no real title available?)
• Polynomial approximation on disjoint segments and amplification of approximation
• An Egyptian algorithm for polynomials

This page was built for publication: Algorithmic polynomials

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