Derandomization

Randomized algorithms can solve problems that seem to demand much more work deterministically. A single coin flip can replace a complicated search. But is any of that power real, or is every randomized algorithm just a deterministic one we haven't been clever enough to find?

Four kinds of coin flipping#

A randomized algorithm flips coins during execution and might give different answers on different runs. The classes sort algorithms by error behavior. RP is one-sided error: a yes instance is accepted with probability at least one half, a no instance always rejected. coRP is the mirror image. ZPP is their intersection, the Las Vegas class: always correct, with variable running time. BPP is two-sided bounded error: every answer is correct with probability at least $\frac{2}{3}$. The containments run $P\subseteq ZPP\subseteq RP\subseteq BPP$, with coRP inside BPP too. The two-thirds threshold is a convention: take the majority of $k$ runs, and by a Chernoff bound any constant edge over one half boosts to near certainty at polynomial cost.

MaxCut with coin flips#

MaxCut: given a graph with $n$ vertices and $m$ edges, partition the vertices into two sets $S$ and $T$ to maximize the number of edges crossing between them. Solving it exactly is NP-hard, so we approximate. The randomized algorithm is almost trivially simple: for each vertex, flip a fair coin. Heads, put it in $S$. Tails, $T$. Done. The two endpoint coins of any edge are independent, so the endpoints land on opposite sides with probability exactly one half. By linearity of expectation,

$$E\left[\text{cut}\right]=\sum _{(u,v)}\frac{1}{2}=\frac{m}{2}.$$

The maximum possible cut is at most $m$, so the expected cut is at least half the optimum, and since the average over all coin sequences is $\frac{m}{2}$, at least one assignment achieves it: the probabilistic method. A guaranteed approximation for an NP-hard problem, from coin flips and a one-line analysis.

So: can we always remove the coins? Formally, is BPP equal to P? Most complexity theorists believe yes. No one has proved it.

Try every coin sequence#

The obvious approach: the algorithm uses $r\left(n\right)$ random bits, so run it on all $2^{r\left(n\right)}$ random strings and take the majority answer. Correct, but most BPP algorithms use polynomially many random bits, and two to a polynomial is exponential: BPP inside EXP, not P. The special case is the insight: with only $O\left(\log n\right)$ random bits, enumeration costs $2^{O\left(\log n\right)}$, polynomial. The obstacle is not randomness itself. It is the number of random bits.

Even amplification can be thrifty with bits: instead of $k$ independent trials at $nk$ bits, take a $k$-step random walk on an expander graph whose vertices are the $2^n$ random strings, at $n+O\left(k\right)$ bits total, and by the expander walk theorem the error still falls like $2^{-\mathrm{\Omega }\left(k\right)}$.

There is also Adleman's nonuniform shortcut: amplify the error below $2^{-n}$ and union bound over the $2^n$ inputs, so some single random string works for every input of one length. Hardwiring it gives BPP inside P/poly, but nonuniformly and nonconstructively: circuits, not algorithms.

The method of conditional expectations#

Think of a BPP algorithm's execution as a binary tree of depth $r$, one level per random bit: internal nodes are partial assignments of random bits, leaves are complete assignments with deterministic outcomes. Let $\rho$ be the conditional probability of success given the bits fixed so far. At the root, $\rho \ge \frac{2}{3}$; at a leaf, $\rho$ is 0 or 1. The key observation: $\rho$ at any node is the average of $\rho$ at its two children, so at least one child is at least as large as the parent. Walk down the tree greedily, always taking the better child. The invariant never drops, so the leaf you reach has $\rho \ge \frac{2}{3}$, which forces $\rho =1$. Always correct, no coins.

The catch is the greedy step: computing the conditional success probability can mean summing over exponentially many leaves, as hard as the original problem. The method works when the conditional expectation has a closed form, and MaxCut is exactly such a case: the conditional expected cut is the number of edges already cut plus half the edges touching an undecided vertex. The rule that falls out is to place each vertex opposite the majority of its already-placed neighbors: a deterministic $O(n+m)$ time algorithm guaranteed to cut at least $\frac{m}{2}$ edges, derived systematically from the probabilistic analysis.

Pause and try: derive the greedy rule from the conditional expectation.

Write $e$ for the conditional expected cut: edges already cut contribute 1, edges with an undecided endpoint contribute $\frac{1}{2}$. Placing the next vertex $v$ in $S$ cuts its edges to placed $T$-neighbors and uncuts its edges to placed $S$-neighbors; comparing with placing $v$ in $T$, the unplaced terms cancel and the difference is (placed neighbors in $T$) minus (placed neighbors in $S$). Going opposite the majority never decreases $e$, which starts at $\frac{m}{2}$.

Pairwise independence#

The second derandomization asks a different question: how much randomness did we actually need? The MaxCut analysis used only that each coin is unbiased and that the two coins on each edge are independent, never mutual independence of all $n$ coins. Pairwise independence is enough.

And pairwise independence is cheap. Take $k$ truly random seed bits, and for each nonempty subset $S$ of the seed positions define $r_S$ as the XOR of the seed bits indexed by $S$: that is $2^k-1$ output bits, each unbiased, and any two are jointly uniform, because two distinct subsets decompose into at least two nonempty groups of independent bits. For $k=3$, eight seeds produce seven pairwise-independent bits.

Apply this to MaxCut with $k$ about ${\log }_{2}n+1$: at least $n$ pairwise-independent bits from only $O\left(n\right)$ possible seeds. The expected cut under any pairwise-independent distribution is still $\frac{m}{2}$, so some seed achieves it; enumerate every seed and keep the best cut. Deterministic, guaranteed, polynomial time.

Pseudorandom generators#

Both attacked the randomness itself, one by simulating the coins greedily, one by shrinking how many you need. The general strategy: build a function $G$ stretching a $d$-bit seed into $m$ bits that look random to any efficient computation. Formally, $G$ is an $(s,ϵ)$ pseudorandom generator if it runs in polynomial time and no circuit of size at most $s$ distinguishes $G\left(z\right)$ from a truly random $m$-bit string with advantage more than $ϵ$.

Why this settles the question: drive a BPP algorithm's error down to $\frac{1}{6}$, so on true randomness it succeeds with probability at least $\frac{5}{6}$. If $G$ fools circuits of the algorithm's size with advantage at most $\frac{1}{6}$, swapping true random bits for $G\left(z\right)$ moves the success probability by at most $\frac{1}{6}$, leaving $\frac{2}{3}$. With $d=O\left(\log n\right)$, enumerate all $2^d$ seeds and take the majority: BPP equals P, if such a generator exists. Pairwise independence fools only tests that look at pairs; Nisan and Wigderson built a generator that fools all small circuits.

Hardness versus randomness#

The Nisan-Wigderson generator starts from a Boolean function $f$ on $l$ bits that is hard for small circuits, and evaluates $f$ on many overlapping windows of a short seed: sets $S_1$ through $S_m$ of seed positions, each of size $l$, any two overlapping in at most $a$ positions. Such designs come from finite fields, with windows the graphs of low-degree polynomials over a $q$ by $q$ grid of seed positions.

The security proof uses hybrids, interpolating between the generator's output and true randomness one bit at a time. A circuit distinguishing the ends with advantage $ϵ$ must distinguish some adjacent pair with advantage $\frac{ϵ}{m}$, meaning it predicts one output bit of $f$ from the earlier bits. Because the windows barely overlap, those earlier bits constrain only a few of the relevant window's inputs, and hardcoding them yields a small circuit for $f$. If $f$ requires large circuits, no small distinguisher exists: the harder $f$, the stronger the generator.

The basic construction gives a polylogarithmic seed, so quasi-polynomial deterministic time. Impagliazzo and Wigderson closed the gap in 1997: if E, deterministic time $2^{O\left(n\right)}$, contains a function requiring circuits of size $2^{\mathrm{\Omega }\left(n\right)}$, then BPP equals P. The proof amplifies worst-case hardness into average-case hardness with XOR lemmas and direct product theorems, feeds the result into a refined Nisan-Wigderson generator with seed length $O\left(\log n\right)$, and enumerates the seeds.

And there is an irony. The natural proofs barrier says that if pseudorandom functions exist, the known proof strategies cannot establish circuit lower bounds. Impagliazzo-Wigderson says that if circuit lower bounds hold, pseudorandom generators exist. Lower bounds give generators, generators give BPP equals P, and strong pseudorandomness blocks the very proofs that might establish the lower bounds. Whether randomness is necessary and whether computation has provable structure are the same question.

If you remember three things#

1. The obstacle to derandomization is the number of random bits: $O\left(\log n\right)$ bits can be brute-forced, and for MaxCut, conditional expectations and pairwise independence get all the way there.
2. A pseudorandom generator with seed length $O\left(\log n\right)$ that fools small circuits would prove BPP equals P; the question reduces to whether such generators exist.
3. Hardness yields randomness: exponential circuit lower bounds for a function in E imply BPP equals P, and those are the very lower bounds the natural proofs barrier guards.