Random low-degree polynomials are hard to approximate

DOI10.1007/S00037-011-0020-6MaRDI QIDQ430841zbMATH OpenOpenAlexFDO

Authors Ido Ben-Eliezer, Rani Hod, Shachar Lovett

Publication date 26 June 2012

Published in Computational Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00037-011-0020-6

zbMATH Keywords

random polynomialsReed-Muller codes

Mathematics Subject Classification ID

Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Linear codes (general theory) (94B05) Bounds on codes (94B65)

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
• Algorithmic regularity for polynomials and applications

Cites work

• scientific article; zbMATH DE number 5485538 (Why is no real title available?)
• scientific article; zbMATH DE number 3577144 (Why is no real title available?)
• scientific article; zbMATH DE number 1324671 (Why is no real title available?)
• scientific article; zbMATH DE number 1024657 (Why is no real title available?)
• A new proof of Szemerédi's theorem
• Affine dispersers from subspace polynomials
• Hardness vs randomness
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
• On the density of sets of vectors
• On the trace of finite sets
• On the weight enumeration of weights less than 2.5d of Reed—Muller codes
• On the weight structure of Reed-Muller codes
• Set Systems with Restricted Cross-Intersections and the Minimum Rank ofInclusion Matrices
• Small Sample Spaces Cannot Fool Low Degree Polynomials
• Weight Distribution and List-Decoding Size of Reed–Muller Codes

Cited in

(8)

• Algorithmic regularity for polynomials and applications
• On the bias of Reed-Muller codes over odd prime fields
• On active and passive testing
• Covering symmetric sets of the Boolean cube by affine hyperplanes
• Random Low Degree Polynomials are Hard to Approximate
• scientific article; zbMATH DE number 7758331 (Why is no real title available?)
• On hitting-set generators for polynomials that vanish rarely
• Reed-Muller Codes

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 Q430841)