Random Low Degree Polynomials are Hard to Approximate

DOI10.1007/978-3-642-03685-9_28zbMath1255.68069OpenAlexW1786790728MaRDI QIDQ3638891

Rani Hod, Ido Ben-Eliezer, 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

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

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