Simplified Derandomization of BPP Using a Hitting Set Generator

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

zbMATH Keywords

derandomizationRPBPPone-sided error versus two-sided error

Mathematics Subject Classification ID

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