Remix.run Logo
gnull 6 hours ago

https://www.wisdom.weizmann.ac.il/~oded/PDF/rnd.pdf

Then you reach derandomization and it hits you once again, it shows you that maybe you can "cheat" in the same way without randomness. Not for free, you usually trade randomness for a bit more running time, but your algorithms stay deterministic. Some believe all probabilistic algorithms can be derandomized (BPP = P), which would be a huge miracle if true.