Random low-degree polynomials are hard to approximate

DOI10.1007/S00037-011-0020-6zbMATH Open1280.68090OpenAlexW2032742263MaRDI QIDQ430841FDOQ430841

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

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

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)

Cites Work

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

Cited In (8)

• On hitting-set generators for polynomials that vanish rarely
• Covering symmetric sets of the Boolean cube by affine hyperplanes
• Random Low Degree Polynomials are Hard to Approximate
• Title not available (Why is that?)
• Reed-Muller Codes
• Algorithmic regularity for polynomials and applications
• On active and passive testing
• 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 Q430841)