Can every randomized algorithm be derandomized?

DOI10.1145/1132516.1132571MaRDI QIDQ2931400zbMATH OpenOpenAlexFDO

Authors Russell Impagliazzo

Publication date 25 November 2014

Published in Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1132516.1132571

zbMATH Keywords

complexity classesderandomizationcircuit complexityprobabilistic algorithmspseudo-randomnessalgebraic circuit complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• scientific article; zbMATH DE number 1559537
• scientific article; zbMATH DE number 1857655
• Hardness vs randomness
• scientific article; zbMATH DE number 1789922
• Randomness vs time: Derandomization under a uniform assumption

Cited in

(20)

• Coin flipping in dynamic programming is almost useless
• Worst-case hardness suffices for derandomization: a new method for hardness-randomness trade-offs
• Derandomization of quantum algorithm for triangle finding
• scientific article; zbMATH DE number 1857655 (Why is no real title available?)
• On derandomization and average-case complexity of monotone functions
• Pseudorandom generators, typically-correct derandomization, and circuit lower bounds
• Holographic Proofs and Derandomization
• scientific article; zbMATH DE number 2019636 (Why is no real title available?)
• Weak derandomization of weak algorithms: explicit versions of Yao's lemma
• Easiness assumptions and hardness tests: Trading time for zero error
• Pseudorandomness when the odds are against you
• Can a randomized binary search have an \(O(1)\) complexity at least in practice?
• Randomness vs time: Derandomization under a uniform assumption
• On derandomizing algorithms that err extremely rarely
• scientific article; zbMATH DE number 1789922 (Why is no real title available?)
• Worst-case hardness suffices for derandomization: a new method for hardness-randomness trade-offs
• scientific article; zbMATH DE number 2102761 (Why is no real title available?)
• Fine-grained derandomization: from problem-centric to resource-centric complexity
• Pairwise independence and derandomization.
• Nearly optimal pseudorandomness from hardness

This page was built for publication: Can every randomized algorithm be derandomized?

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