Small Sample Spaces Cannot Fool Low Degree Polynomials

DOI10.1007/978-3-540-85363-3_22MaRDI QIDQ3541801zbMATH OpenOpenAlexFDO

Authors Noga Alon, Ido Ben-Eliezer, Michael Krivelevich

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)

Recommendations

• The sum of \(D\) small-bias generators fools polynomials of degree \(D\)
• Some limitations of the sum of small-bias distributions
• Pseudorandom generators for low degree polynomials
• On Improved Degree Lower Bounds for Polynomial Approximation.
• Pseudorandom generators for \(\mathrm{CC}^0[p]\) and the Fourier spectrum of low-degree polynomials over finite fields

Cites work

• scientific article; zbMATH DE number 5485485 (Why is no real title available?)
• scientific article; zbMATH DE number 5485568 (Why is no real title available?)
• Inverse conjecture for the Gowers norm is false
• Lower bounds for local versions of dimension reductions
• Noisy interpolating sets for low-degree polynomials
• Perturbed Identity Matrices Have High Rank: Proof and Applications
• Problems and results in extremal combinatorics. I.
• Pseudorandom bits for polynomials
• Pseudorandom generators for low degree polynomials
• Pseudorandomness for width-2 branching programs
• Random Cayley graphs and expanders
• Randomness-efficient low degree tests and short PCPs via epsilon-biased sets
• Simple Constructions of Almost k-wise Independent Random Variables
• Small-Bias Probability Spaces: Efficient Constructions and Applications
• Some structural properties of low-rank matrices related to computational complexity
• The probabilistic method yields deterministic parallel algorithms
• The probabilistic method. With an appendix on the life and work of Paul Erdős.

Cited in

(5)

• Random low-degree polynomials are hard to approximate
• Small-bias is not enough to hit read-once CNF
• The sum of \(D\) small-bias generators fools polynomials of degree \(D\)
• Optimal pseudorandom generators for low-degree polynomials over moderately large fields
• Low-degree polynomials are good extractors

This page was built for publication: Small Sample Spaces Cannot Fool Low Degree Polynomials

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3541801)