Pseudorandom generators for \(\mathrm{CC}^0[p]\) and the Fourier spectrum of low-degree polynomials over finite fields

DOI10.1007/s00037-012-0051-7zbMath1290.68049OpenAlexW2047062580MaRDI QIDQ395606

Shachar Lovett, Partha Mukhopadhyay, Amir Shpilka

Publication date: 29 January 2014

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00037-012-0051-7

zbMATH Keywords

pseudorandom generatorslow-degree polynomialssmall-depth circuits

Mathematics Subject Classification ID

Related Items (2)

Pseudorandom generators for \(\mathrm{CC}^0[p\) and the Fourier spectrum of low-degree polynomials over finite fields] ⋮ Pseudorandom generators for combinatorial checkerboards

Cites Work

• Unnamed Item
• Pseudorandom generators for \(\mathrm{CC}^0[p\) and the Fourier spectrum of low-degree polynomials over finite fields]
• The sum of \(D\) small-bias generators fools polynomials of degree \(D\)
• Pseudorandom bits for constant depth circuits
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• Approximate inclusion-exclusion
• Hardness vs randomness
• Pseudorandom Bits for Polynomials
• Small-Bias Probability Spaces: Efficient Constructions and Applications
• Polylogarithmic independence fools AC ⁰ circuits
• Pseudorandom Bit Generators That Fool Modular Sums
• Small-Bias Spaces for Group Products
• Polylogarithmic Independence Can Fool DNF Formulas
• Simple Constructions of Almost k-wise Independent Random Variables
• Computational Complexity
• Computational Complexity

This page was built for publication: Pseudorandom generators for \(\mathrm{CC}^0[p]\) and the Fourier spectrum of low-degree polynomials over finite fields