Unconditional pseudorandom generators for low degree polynomials

DOI10.4086/TOC.2009.V005A003zbMATH Open1213.68274OpenAlexW2611668233MaRDI QIDQ3002801FDOQ3002801

Authors: Shachar Lovett 

Publication date: 24 May 2011

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

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

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

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)

Cited In (18)

• 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
• Title not available (Why is that?)
• Title not available (Why is that?)
• Cryptographic hardness of random local functions. Survey
• On hitting-set generators for polynomials that vanish rarely
• Quantified Derandomization: How to Find Water in the Ocean
• 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
• 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

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)