Simple extractors for all min-entropies and a new pseudorandom generator

DOI10.1145/1059513.1059516zbMath1317.68132OpenAlexW2135453633MaRDI QIDQ3546310

Christopher Umans, Ronen Shaltiel

Publication date: 21 December 2008

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1059513.1059516

Mathematics Subject Classification ID

Data encryption (aspects in computer science) (68P25) Random number generation in numerical analysis (65C10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Randomized algorithms (68W20) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (30)

Incompressible functions, relative-error extractors, and the power of nondeterministic reductions ⋮ Quantified Derandomization: How to Find Water in the Ocean ⋮ Deterministic extractors for affine sources over large fields ⋮ Reconstructive dispersers and hitting set generators ⋮ Derandomization from Algebraic Hardness ⋮ A modular framework for quantum-proof randomness extractors ⋮ Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization ⋮ \(\mathrm{AC}^{0}\circ \mathrm{MOD}_{2}\) lower bounds for the Boolean inner product ⋮ Pseudorandom generators for combinatorial checkerboards ⋮ The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory ⋮ Infeasibility of instance compression and succinct PCPs for NP ⋮ (Nondeterministic) hardness vs. non-malleability ⋮ One-way functions and the hardness of (probabilistic) time-bounded Kolmogorov complexity w.r.t. samplable distributions ⋮ Paradigms for Unconditional Pseudorandom Generators ⋮ On derandomization and average-case complexity of monotone functions ⋮ Pseudorandom generators, typically-correct derandomization, and circuit lower bounds ⋮ Derandomizing Arthur-Merlin games and approximate counting implies exponential-size lower bounds ⋮ Unnamed Item ⋮ An Introduction to Randomness Extractors ⋮ Simple extractors via constructions of cryptographic pseudo-random generators ⋮ Unnamed Item ⋮ The complexity of the matroid-greedoid partition problem ⋮ Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification ⋮ Lower Bounds on the Query Complexity of Non-uniform and Adaptive Reductions Showing Hardness Amplification ⋮ Typically-correct derandomization for small time and space ⋮ Bounds on Fixed Input/Output Length Post-processing Functions for Biased Physical Random Number Generators ⋮ High-rate codes with sublinear-time decoding ⋮ A combination of testability and decodability by tensor products ⋮ On hitting-set generators for polynomials that vanish rarely ⋮ A Note on Perfect Correctness by Derandomization

This page was built for publication: Simple extractors for all min-entropies and a new pseudorandom generator