Derandomization Techniques

Core Idea

Derandomization converts randomized algorithms into deterministic ones while preserving their efficiency guarantees. The central question is whether randomness is truly necessary for efficient computation -- equivalently, whether P = BPP. Techniques range from the elementary (the method of conditional expectations, which converts an existential probabilistic argument into a greedy deterministic construction) to the deep (Nisan-Wigderson pseudorandom generators, which fool bounded computations with short seeds under circuit lower bound assumptions). Limited independence (pairwise, k-wise) often suffices where full independence seems required, enabling derandomization by exhaustive enumeration over a polynomial-size sample space.

Explainer

Randomized algorithms are often simpler and faster than their deterministic counterparts, but the question of whether randomness is truly necessary is one of the deepest in complexity theory. Derandomization techniques systematically remove the need for randomness while preserving efficiency. The most basic technique is the method of conditional expectations, which converts a probabilistic existence argument into a constructive deterministic algorithm. If the expected value of some objective is at least t (so a random assignment achieves t in expectation), then you can fix each random bit greedily: choose the value that keeps the conditional expectation at least t. After all bits are fixed, you have a deterministic assignment achieving at least t. This requires being able to compute conditional expectations efficiently, which is possible for many natural objectives (like the number of satisfied clauses in MAX-SAT).

A more powerful approach exploits limited independence. Many randomized algorithms do not actually need their random variables to be fully independent -- pairwise independence or k-wise independence suffices for the analysis (typically because the proof only uses Chebyshev's inequality or bounded moments). A family of pairwise-independent random variables over n bits can be constructed from just O(log n) seed bits using linear functions over finite fields. Since the seed space has polynomial size, you can enumerate all seeds deterministically and pick the best one. This transforms a randomized algorithm into a deterministic one with only a polynomial overhead, provided the analysis relies on limited independence.

At the deepest level, pseudorandom generators (PRGs) aim to derandomize all of BPP. The Nisan-Wigderson construction builds a PRG that stretches O(log n) truly random bits into polynomially many bits that no polynomial-size circuit can distinguish from truly random bits. The construction uses a combinatorial design to extract pseudorandom bits from a hard function -- one that is computable in exponential time but requires exponential-size circuits. Under this hardness assumption, BPP = P: every efficient randomized algorithm can be made deterministic with only polynomial overhead. The hardness assumption is widely believed (it follows from standard conjectures about circuit lower bounds) but remains unproven, keeping the P vs BPP question formally open.

Expander graphs provide another route to reducing randomness. Standard probability amplification repeats a randomized algorithm independently O(k) times to reduce error probability to 2^-k, but each repetition uses fresh random bits. The expander walk technique replaces independent repetitions with a walk on an expander graph whose vertices represent random seeds. Because expanders have strong mixing properties, consecutive vertices on a random walk are "nearly independent" for the purposes of error analysis. This reduces the random bit requirement from O(k * r) to r + O(k), where r is the number of bits per trial. Combined with limited independence and PRGs, these techniques form a comprehensive toolkit suggesting that randomness, while convenient, may be computationally eliminable -- that the class BPP equals P.

The practical impact of derandomization extends beyond theory. The method of conditional expectations is routinely used to convert randomized approximation algorithms (like the randomized 7/8-approximation for MAX-3SAT) into deterministic ones. Pairwise-independent hashing underlies deterministic data structures and streaming algorithms. Even when full derandomization is impractical, understanding which properties of randomness an algorithm actually needs (full independence? pairwise? k-wise?) often leads to simpler analyses and more efficient implementations that use fewer random bits.