Weak Random Sources, Hitting Sets, and BPP Simulations

DOI10.1137/S0097539797325636zbMath0943.68064OpenAlexW2111978056MaRDI QIDQ4268859

Luca Trevisan, Alexander E. Andreev, José D. P. Rolim, Andrea E. F. Clementi

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

derandomizationrandomized computationshitting setsexpander graphsimperfect sources of randomness

Mathematics Subject Classification ID

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

Related Items

A classification of the probabilistic polynomial time hierarchy under fault tolerant access to oracle classes, Extractors for weak random sources and their applications, Privacy with Imperfect Randomness, Reconstructive dispersers and hitting set generators, Worst-case hardness suffices for derandomization: A new method for hardness-randomness trade-offs, Approximation of boolean functions by combinatorial rectangles, Paradigms for Unconditional Pseudorandom Generators, Worst-case hardness suffices for derandomization: a new method for hardness-randomness trade-offs, Injective trapdoor functions via derandomization: how strong is Rudich's black-box barrier?, Unnamed Item, Injective trapdoor functions via derandomization: how strong is Rudich's black-box barrier?, Pseudo-random generators for all hardnesses, Simplified Derandomization of BPP Using a Hitting Set Generator, Randomness vs time: Derandomization under a uniform assumption