3 ms·
Prescient. Nowadays, most computer scientists don't explicitly worry about hardware failures, but we still love randomized algorithms. Often it's easy to prove
by blt 7y ago
Prescient. Nowadays, most computer scientists don't explicitly worry about hardware failures, but we still love randomized algorithms.
Often it's easy to prove that a randomized algorithm has a desirable property with probability 1 asymptotically, or with high probability in finite time.
In contrast, it's often hard to prove the analogous desirable property always holds for a deterministic algorithm.
In other words, we use a trick to make a combinatoric problem more like an analysis problem, because analysis problems are easier to handle -- exactly what Von Neumann was writing about!
Turns out, the power of analytical methods was its own motivation, and we didn't need unreliable hardware to push us in that direction.