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

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

Mathematics Subject Classification ID

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

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)

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