Random low-degree polynomials are hard to approximate

DOI10.1007/s00037-011-0020-6zbMath1280.68090OpenAlexW2032742263MaRDI QIDQ430841

Ido Ben-Eliezer, Shachar Lovett, Rani Hod

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

Reed-Muller codesrandom polynomials

Mathematics Subject Classification ID

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

Related Items (6)

Covering symmetric sets of the Boolean cube by affine hyperplanes ⋮ On the Bias of Reed--Muller Codes over Odd Prime Fields ⋮ On Active and Passive Testing ⋮ Unnamed Item ⋮ On hitting-set generators for polynomials that vanish rarely ⋮ Reed-Muller Codes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the density of sets of vectors
• 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
• Hardness vs randomness
• On the trace of finite sets
• Small Sample Spaces Cannot Fool Low Degree Polynomials
• On the weight enumeration of weights less than 2.5d of Reed—Muller codes
• Affine dispersers from subspace polynomials
• Weight Distribution and List-Decoding Size of Reed–Muller Codes
• Set Systems with Restricted Cross-Intersections and the Minimum Rank ofInclusion Matrices
• On the weight structure of Reed-Muller codes
• A new proof of Szemerédi's theorem

This page was built for publication: Random low-degree polynomials are hard to approximate