Unconditional pseudorandom generators for low degree polynomials

DOI10.4086/TOC.2009.V005A003MaRDI QIDQ3002801zbMATH OpenOpenAlexFDO

Authors Shachar Lovett

Publication date 24 May 2011

Published in Theory of Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4086/toc.2009.v005a003

zbMATH Keywords

explicit constructionlow degreepolynomialpseudorandom

Mathematics Subject Classification ID

Number-theoretic algorithms; complexity (11Y16) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Recommendations

• Pseudorandom bits for polynomials
• Pseudorandom generators for low degree polynomials
• The sum of \(D\) small-bias generators fools polynomials of degree \(D\)
• Pseudorandom generators for \(\mathrm{CC}^0[p]\) and the Fourier spectrum of low-degree polynomials over finite fields

Cited in

(22)

• On hitting-set generators for polynomials that vanish rarely
• Additive combinatorics: with a view towards computer science and cryptography -- an exposition
• Pseudorandom bits for polynomials
• Cryptographic hardness of random local functions. Survey
• Pseudorandom generators for low degree polynomials
• Pseudorandom generators for \(\mathrm{CC}^0[p]\) and the Fourier spectrum of low-degree polynomials over finite fields
• Pseudorandom generators for combinatorial checkerboards
• Bounded independence plus noise fools products
• Luby-Veličković-Wigderson revisited: improved correlation bounds and pseudorandom generators for depth-two circuits
• Quantified Derandomization: How to Find Water in the Ocean
• scientific article; zbMATH DE number 7528580 (Why is no real title available?)
• Pseudorandom Generators from the Second Fourier Level and Applications to AC0 with Parity Gates
• More on bounded independence plus noise: pseudorandom generators for read-once polynomials
• Entropy of weight distributions of small-bias spaces and pseudobinomiality
• Improved pseudorandom generators from pseudorandom multi-switching lemmas
• A simple deterministic reduction for the gap minimum distance of code problem
• On hitting-set generators for polynomials that vanish rarely
• Paradigms for Unconditional Pseudorandom Generators
• The sum of \(D\) small-bias generators fools polynomials of degree \(D\)
• Optimal pseudorandom generators for low-degree polynomials over moderately large fields
• Fourier conjectures, correlation bounds, and majority
• On sums of INW pseudorandom generators

This page was built for publication: Unconditional pseudorandom generators for low degree polynomials

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