Skip to content

Randomness in Algorithms

Abstract

For most of computing’s history a program was supposed to be a deterministic recipe: same input, same steps, same answer. Then theorists discovered that letting an algorithm flip coins could make it faster, simpler, or possible at all. A randomized primality test made RSA practical in 1977; a randomized pivot rescued quicksort from its worst case; randomized routing and load balancing hold up the internet. The deep question that followed was whether randomness is ever truly necessary, or only a convenient shortcut. Decades of work now suggest the coins can, in principle, be removed. This article follows the idea from Monte Carlo dice to the theorems that argue randomness may be dispensable.

Two Ways to Gamble

Randomized algorithms split into two families, named after gambling towns. A Monte Carlo algorithm runs for a fixed amount of time and gives an answer that is probably right; run it again and the chance of error shrinks. A Las Vegas algorithm never gives a wrong answer, but the time it takes is a gamble; it keeps going until it is certain. The term “Las Vegas algorithm” was coined by László Babai in 1979, working on graph isomorphism, to name the contrast with the Monte Carlo methods that Stanislaw Ulam and John von Neumann had introduced for numerical simulation in the 1940s. The distinction is the whole design vocabulary: you choose which of the two you can tolerate gambling with, the correctness or the clock.

The Pivot That Saved Quicksort

The cleanest example of buying performance with randomness is Tony Hoare’s quicksort. It partitions the data around a chosen “pivot” element, then sorts the two halves. Pick pivots well and it runs in n·log n time; pick badly (say, always the first element of an already-sorted list) and it degrades to n², the disaster case. The classic fix is to stop letting the input choose: pick the pivot at random. No particular arrangement of the data can then be the worst case, because the algorithm’s behavior no longer depends on the input’s order, only on its own coin flips. Randomized quicksort is a Las Vegas algorithm; it always sorts correctly, and its running time is n·log n with overwhelming probability whatever the input. The same move (randomize the choice the adversary would exploit) recurs throughout the field: randomized pivots, random hash functions, randomly shuffled inputs.

The Test That Made RSA Real

Randomness did more than speed up existing algorithms; in one case it made a whole industry practical. Public-key cryptography needs large prime numbers, hundreds of digits long, generated on demand. In 1977 nobody knew how to prove such a number prime quickly. Robert Solovay and Volker Strassen published “A Fast Monte-Carlo Test for Primality” that year: pick a random number, run a cheap arithmetic check, and if the candidate is composite the check exposes it with probability at least one-half. Repeat with fresh random numbers, and the chance of a composite slipping through drops by half each round; after a hundred rounds it is far below the chance of a hardware fault. The test never proves primality with certainty, it makes the error astronomically unlikely, and that was enough. It “showed the practical feasibility of the RSA cryptosystem”, which had been published only months earlier and needed exactly this.

Better tests followed the same year. Gary Miller had given a deterministic primality test in 1976, but its correctness depended on the unproven extended Riemann hypothesis. In 1980 Michael Rabin converted it into an unconditional randomized test with a 2⁻ᵏ error bound, cleaner and sharper than Solovay-Strassen. The Miller-Rabin test is what actually runs inside RSA and TLS key generation today: every time a browser sets up a secure connection, randomized primality testing has almost certainly happened somewhere behind it. In 2002 three Indian researchers, Manindra Agrawal, Neeraj Kayal, and Nitin Saxena, finally produced AKS, a deterministic polynomial-time primality test with no unproven assumptions, settling the theoretical question (“PRIMES is in P”) and winning the Gödel and Fulkerson prizes. In a fine irony, nobody uses it: the randomized tests are many orders of magnitude faster, so practice kept the coins even after theory proved they were not logically required.

Is the Randomness Real?

That irony points at the field’s central question. Randomized algorithms defined a complexity class, BPP, the problems solvable in polynomial time with bounded error using coin flips. Is BPP actually larger than P, the problems solvable without randomness? Does randomness give real computational power, or only convenience? Starting in the 1980s the surprising answer emerged: probably convenience. Avi Wigderson, with Noam Nisan and later Russell Impagliazzo, built the theory of derandomization, showing that if certain hard problems are genuinely hard (a mild and widely believed assumption), then every efficient randomized algorithm can be converted into an efficient deterministic one. The slogan of the Impagliazzo-Wigderson result of 1997 is that hardness can be traded for randomness: a hard-enough function can be stretched into a pseudorandom generator whose output no fast algorithm can distinguish from true coin flips, so the algorithm cannot tell it has been cheated. Under these assumptions P = BPP, and the coins were never necessary in principle.

For this reshaping of the role of randomness in computation, Wigderson received the 2023 Turing Award, having already shared the 2021 Abel Prize with László Lovász. The practical upshot is a peace treaty between the two views. Randomness remains the easiest way to write a fast primality test, a load balancer, a sublinear sampler, or a Monte Carlo simulation, and every serious system uses it. Theory, meanwhile, holds that this ease is a human convenience rather than a computational necessity: the dice make algorithms simpler to design, not more powerful in the end.

📚 Sources