How Randomness Improves Algorithms | Quanta Magazine

randomized-algorithmscomputational-complexityalgorithm-designgraph-theory

Abstraction: Why randomness makes hard algorithmic problems tractable

Key points:

Fermat's little theorem basis for probabilistic primality test — after a few dozen random trials, error probability is lower than an asteroid hitting Earth
Nisan and Wigderson (1994): either all problems solvable by randomized algorithms also have fast deterministic algorithms, or many notoriously hard problems are secretly easy
De-randomization of primality testing achieved in 2002 (AKS algorithm) but is far slower in practice than the best randomized versions
Graph shortest-path breakthrough: researchers used randomness to pick which edges to delete — proving most random choices are good enough without knowing the optimal solution
Key insight: "Randomness is basically a way to ensure that something is true about the optimal solution without knowing the optimal solution" — Aaron Bernstein

Connections: Avi Wigderson · Randomized Algorithms · Computational Complexity · Algorithm Design · Graph Theory