Pseudo-random generators for all hardnesses

DOI10.1016/S0022-0000(03)00046-1zbMath1072.68129MaRDI QIDQ5917585

Christopher Umans

Publication date: 18 November 2004

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

zbMATH Keywords

DerandomizationComplexity classesLow-degree extensionPseudo-random number generators

Mathematics Subject Classification ID

Random number generation in numerical analysis (65C10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Randomized algorithms (68W20)

Related Items (23)

A brief and understandable guide to pseudo-random number generators and specific models for security ⋮ Quantified Derandomization: How to Find Water in the Ocean ⋮ Reconstructive dispersers and hitting set generators ⋮ Derandomization from Algebraic Hardness ⋮ \(\mathrm{AC}^{0}\circ \mathrm{MOD}_{2}\) lower bounds for the Boolean inner product ⋮ Uniform derandomization from pathetic lower bounds ⋮ Pseudorandom generators for combinatorial checkerboards ⋮ The power of natural properties as oracles ⋮ Paradigms for Unconditional Pseudorandom Generators ⋮ On derandomization and average-case complexity of monotone functions ⋮ Derandomizing Arthur-Merlin games and approximate counting implies exponential-size lower bounds ⋮ Circuit Lower Bounds for Nondeterministic Quasi-polytime from a New Easy Witness Lemma ⋮ Pseudo-Derandomizing Learning and Approximation ⋮ Fourier concentration from shrinkage ⋮ Unnamed Item ⋮ Natural Proofs versus Derandomization ⋮ ON THE HARDNESS AGAINST CONSTANT-DEPTH LINEAR-SIZE CIRCUITS ⋮ Jacobian Hits Circuits: Hitting Sets, Lower Bounds for Depth-$D$ Occur-$k$ Formulas and Depth-3 Transcendence Degree-$k$ Circuits ⋮ In a World of P=BPP ⋮ Unnamed Item ⋮ Relations and equivalences between circuit lower bounds and karp-lipton theorems ⋮ Randomness and Intractability in Kolmogorov Complexity ⋮ Targeted Pseudorandom Generators, Simulation Advice Generators, and Derandomizing Logspace

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Derandomizing Arthur-Merlin games using hitting sets
• \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
• Hardness vs randomness
• Decoding of Reed Solomon codes beyond the error-correction bound
• Derandomizing Arthur-Merlin games under uniform assumptions
• In search of an easy witness: Exponential time vs. probabilistic polynomial time.
• Extractors from Reed-Muller codes
• Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses
• Simplified Derandomization of BPP Using a Hitting Set Generator
• Extractors and pseudo-random generators with optimal seed length
• List decoding algorithms for certain concatenated codes
• How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
• A new general derandomization method
• Weak Random Sources, Hitting Sets, and BPP Simulations
• Extractors and pseudorandom generators
• Pseudorandom generators without the XOR lemma
• Easiness assumptions and hardness tests: Trading time for zero error

This page was built for publication: Pseudo-random generators for all hardnesses