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

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) 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

• A new proof of Szemerédi's theorem
• Affine dispersers from subspace polynomials
• Hardness vs randomness
• 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?)
• 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

(14)

• 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
• On the bias of Reed-Muller codes over odd prime fields
• Algorithmic regularity for polynomials and applications
• On active and passive testing
• Reed-Muller Codes
• scientific article; zbMATH DE number 7758331 (Why is no real title available?)
• Property testing with online adversaries
• Hilbert functions and low-degree randomness extractors
• A criterion for decoding on the binary symmetric channel
• Learning a mixture of two subspaces over finite fields
• Property testing with online adversaries
• Low-degree polynomials are good extractors

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)