Random low-degree polynomials are hard to approximate
From MaRDI portal
Publication:430841
DOI10.1007/s00037-011-0020-6zbMath1280.68090MaRDI 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
94B05: Linear codes (general theory)
94B65: Bounds on codes
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q87: Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)
Related Items
On the Bias of Reed--Muller Codes over Odd Prime Fields, On Active and Passive Testing, Reed-Muller Codes, Unnamed Item, On hitting-set generators for polynomials that vanish rarely, Covering symmetric sets of the Boolean cube by affine hyperplanes
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
