Simplified derandomization of BPP using a hitting set generator

DOI10.1007/978-3-642-22670-0_8MaRDI QIDQ3088176zbMATH OpenOpenAlexFDO

Authors Oded Goldreich, A. Wigderson, Salil 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

BPPderandomizationone-sided error versus two-sided errorRP

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Randomized algorithms (68W20)

Recommendations

• scientific article; zbMATH DE number 2102761
• A new general derandomization method
• Hitting sets with near-optimal error for read-once branching programs
• Weak Random Sources, Hitting Sets, and BPP Simulations
• scientific article; zbMATH DE number 1559537

Cites work

• A new general derandomization method
• Another Proof That $\mathcal{BPP}\subseteq \mathcal{PH}$ (and More)
• BPP and the polynomial hierarchy
• scientific article; zbMATH DE number 1304314 (Why is no real title available?)
• scientific article; zbMATH DE number 1559537 (Why is no real title available?)
• Simulating BPP using a general weak random source
• The complexity of promise problems with applications to public-key cryptography
• Weak Random Sources, Hitting Sets, and BPP Simulations

Cited in

(11)

• A note on perfect correctness by derandomization
• A note on parameterized polynomial identity testing using hitting set generators
• Reconstructive dispersers and hitting set generators
• A new general derandomization method
• scientific article; zbMATH DE number 2102761 (Why is no real title available?)
• 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: Simplified derandomization of BPP using a hitting set generator

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