Making polynomials robust to noise

DOI10.4086/TOC.2013.V009A018MaRDI QIDQ3191588zbMATH OpenOpenAlexFDO

Authors Alexander A. Sherstov

Publication date 6 October 2014

Published in Theory of Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4086/toc.2013.v009a018

zbMATH Keywords

computation with noisepolynomial approximationreal polynomials on Boolean hypercuberobust polynomials

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Symbolic computation and algebraic computation (68W30)

Recommendations

• Making polynomials robust to noise
• Robust polynomials and quantum algorithms
• STACS 2005
• Learning polynomials with queries: The highly noisy case
• Reliable computation by formulas in the presence of noise

Cites work

• Coding for interactive communication
• Finding parity in a simple broadcast network
• scientific article; zbMATH DE number 1256711 (Why is no real title available?)

Cited in

(16)

• Robust polynomials and quantum algorithms
• Breaking the Minsky--Papert Barrier for Constant-Depth Circuits
• The power of asymmetry in constant-depth circuits
• Low-sensitivity functions from unambiguous certificates
• Computational benefit of smoothness: parameterized bit-complexity of numerical operators on analytic functions and Gevrey's hierarchy
• Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC^0
• 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
• Making polynomials robust to noise
• STACS 2005
• scientific article; zbMATH DE number 7758330 (Why is no real title available?)
• Polynomial approximation on disjoint segments and amplification of approximation
• Approximate degree composition for recursive functions
• The approximate degree of DNF and CNF formulas
• Classical algorithms for constant approximation of the ground state energy of local Hamiltonians

This page was built for publication: Making polynomials robust to noise

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