Nearly 30 years after Nisan and Wigderson’s landmark proof, randomized algorithms remain as popular as ever, because de-randomization can be tricky and deterministic algorithms are often efficient only in principle. It wasn’t until 2002 that three researchers found a way to de-randomize primality testing, and in practice their algorithm is far slower than the best randomized algorithms. For other problems, it’s hard even to know where to begin — the best known algorithm has a chicken-and-egg problem that you can only escape through randomness.
Read more:
Brubaker, B. (2023, April 3). How Randomness Improves Algorithms. Quanta Magazine. https://www.quantamagazine.org/how-randomness-improves-algorithms-20230403/