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

polynomialpseudorandomexplicit constructionlow degree

Mathematics Subject Classification ID

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

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

(18)

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

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)