Weak Random Sources, Hitting Sets, and BPP Simulations

DOI10.1137/S0097539797325636MaRDI QIDQ4268859zbMATH OpenOpenAlexFDO

Authors Luca Trevisan, Alexander E. Andreev, Andrea Clementi, José Rolim

Publication date 28 October 1999

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0097539797325636

zbMATH Keywords

derandomizationexpander graphshitting setsimperfect sources of randomnessrandomized computations

Mathematics Subject Classification ID

Pseudo-random numbers; Monte Carlo methods (11K45) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Recommendations

• Simulating BPP using a general weak random source
• Computing with Very Weak Random Sources
• scientific article; zbMATH DE number 2102761
• Pseudorandom sources for BPP

Cited in

(17)

• Approximation of boolean functions by combinatorial rectangles
• Randomness vs time: Derandomization under a uniform assumption
• Simulating BPP using a general weak random source
• Worst-case hardness suffices for derandomization: a new method for hardness-randomness trade-offs
• Reconstructive dispersers and hitting set generators
• A classification of the probabilistic polynomial time hierarchy under fault tolerant access to oracle classes
• Simplified derandomization of BPP using a hitting set generator
• Privacy with Imperfect Randomness
• Worst-case hardness suffices for derandomization: a new method for hardness-randomness trade-offs
• scientific article; zbMATH DE number 2102761 (Why is no real title available?)
• Extractors for weak random sources and their applications
• Hitting sets give two-sided derandomization of small space
• Injective trapdoor functions via derandomization: how strong is Rudich's black-box barrier?
• Pseudo-random generators for all hardnesses
• Injective trapdoor functions via derandomization: how strong is Rudich's black-box barrier?
• Paradigms for Unconditional Pseudorandom Generators
• Pseudodistributions that beat all pseudorandom generators

This page was built for publication: Weak Random Sources, Hitting Sets, and BPP Simulations

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