Small Sample Spaces Cannot Fool Low Degree Polynomials

DOI10.1007/978-3-540-85363-3_22zbMath1159.68633OpenAlexW2118381322MaRDI QIDQ3541801

Noga Alon, Michael Krivelevich, Ido Ben-Eliezer

Publication date: 27 November 2008

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-85363-3_22

Mathematics Subject Classification ID

Combinatorial probability (60C05) Randomized algorithms (68W20)

Related Items

Random low-degree polynomials are hard to approximate, Small-bias is not enough to hit read-once CNF

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Lower bounds for local versions of dimension reductions
• The probabilistic method yields deterministic parallel algorithms
• Problems and results in extremal combinatorics. I.
• Some structural properties of low-rank matrices related to computational complexity
• Pseudorandom Bits for Polynomials
• Small-Bias Probability Spaces: Efficient Constructions and Applications
• Perturbed Identity Matrices Have High Rank: Proof and Applications
• Randomness-efficient low degree tests and short PCPs via epsilon-biased sets
• Pseudorandom generators for low degree polynomials
• Simple Constructions of Almost k-wise Independent Random Variables
• Random Cayley graphs and expanders