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

algebraic circuit complexitycircuit complexitycomplexity classesderandomizationprobabilistic algorithmspseudo-randomness

Mathematics Subject Classification ID

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

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

(22)

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

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)