Random Low Degree Polynomials are Hard to Approximate

DOI10.1007/978-3-642-03685-9_28MaRDI QIDQ3638891zbMATH OpenOpenAlexFDO

Authors Ido Ben-Eliezer, Rani Hod, Shachar Lovett

Publication date 28 October 2009

Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-03685-9_28

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Linear codes (general theory) (94B05)

Recommendations

• Random low-degree polynomials are hard to approximate
• On Improved Degree Lower Bounds for Polynomial Approximation.
• On the bias of Reed-Muller codes over odd prime fields
• Hardness of Reconstructing Multivariate Polynomials over Finite Fields
• Hard functions for low-degree polynomials over prime fields

Cited in

(3)

• Random low-degree polynomials are hard to approximate
• Quadratic Maps Are Hard to Sample
• On the bias of Reed-Muller codes over odd prime fields

This page was built for publication: Random Low Degree Polynomials are Hard to Approximate

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