Weak Random Sources, Hitting Sets, and BPP Simulations
From MaRDI portal
Publication:4268859
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
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