Reducing the seed length in the Nisan-Wigderson generator

DOI10.1007/S00493-006-0036-8MaRDI QIDQ879167zbMATH OpenOpenAlexFDO

Authors Russell Impagliazzo, Ronen Shaltiel, A. Wigderson

Publication date 8 May 2007

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00493-006-0036-8

zbMATH Keywords

pseudo-random generatorexplicit constructionoptimal seed length

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Extractors and pseudo-random generators with optimal seed length
• Construction of extractors using pseudo-random generators (extended abstract)
• Extractors and pseudorandom generators
• Simple extractors for all min-entropies and a new pseudorandom generator
• Automata, Languages and Programming

Cited in

(6)

• Pseudorandom generators for combinatorial checkerboards
• Paradigms for Unconditional Pseudorandom Generators
• Extractors and pseudo-random generators with optimal seed length
• \(\mathrm{AC}^{0}\circ \mathrm{MOD}_{2}\) lower bounds for the Boolean inner product
• Reconstructive dispersers and hitting set generators
• Amplification and Derandomization without Slowdown

This page was built for publication: Reducing the seed length in the Nisan-Wigderson generator

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