Hitting sets derandomize BPP

DOI10.1007/3-540-61440-0_142MaRDI QIDQ4818849zbMATH OpenFDO

Authors Alexander E. Andreev, Andrea Clementi, José Rolim

Publication date 24 September 2004

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-61440-0_142

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Simplified derandomization of BPP using a hitting set generator
• A new general derandomization method
• On derandomizing algorithms that err extremely rarely
• Weak Random Sources, Hitting Sets, and BPP Simulations
• Can every randomized algorithm be derandomized?

Cited in

(14)

• Minimal approximate hitting sets and rule templates
• Randomness vs time: Derandomization under a uniform assumption
• Polynomial asymptotically optimal coding of underdetermined Bernoulli sources of the general form
• Reconstructive dispersers and hitting set generators
• Simplified derandomization of BPP using a hitting set generator
• Lower bounds on black-box reductions of hitting to density estimation
• A new general derandomization method
• Weak Random Sources, Hitting Sets, and BPP Simulations
• Nearly bounded error probabilistic sets
• Worst-case hardness suffices for derandomization: a new method for hardness-randomness trade-offs
• Hitting sets give two-sided derandomization of small space
• Efficient constructions of hitting sets for systems of linear functions
• Hitting sets give two-sided derandomization of small space
• On pseudorandomness and resource-bounded measure

This page was built for publication: Hitting sets derandomize BPP

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