Simplified Derandomization of BPP Using a Hitting Set Generator
From MaRDI portal
Publication:3088176
DOI10.1007/978-3-642-22670-0_8zbMath1343.68303OpenAlexW2571236692MaRDI QIDQ3088176
Oded Goldreich, Avi Wigderson, Salil P. Vadhan
Publication date: 19 August 2011
Published in: Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-22670-0_8
Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Randomized algorithms (68W20)
Related Items
A note on perfect correctness by derandomization, Reconstructive dispersers and hitting set generators, Paradigms for Unconditional Pseudorandom Generators, 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
Cites Work
- Unnamed Item
- Unnamed Item
- BPP and the polynomial hierarchy
- Simulating BPP using a general weak random source
- Another Proof That $\mathcal{BPP}\subseteq \mathcal{PH}$ (and More)
- The complexity of promise problems with applications to public-key cryptography
- A new general derandomization method
- Weak Random Sources, Hitting Sets, and BPP Simulations
