Algorithmic polynomials

DOI10.1145/3188745.3188958zbMATH Open1428.68159arXiv1801.04607OpenAlexW2808904471MaRDI QIDQ5230299FDOQ5230299

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)

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.

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

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

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)

Cited In (27)

• Algorithmic Polynomials
• Title not available (Why is that?)
• Algorithmic problems for differential polynomial algebras
• Title not available (Why is that?)
• Code Generation for Polynomial Multiplication
• Title not available (Why is that?)
• Algorithms for Symbolic Polynomials
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• 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
• Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization
• An Egyptian algorithm for polynomials
• Variation on Euclid's algorithm for polynomials
• Lower bounds for the approximate degree of block-composed functions

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)