47.05.05 · theoretical-cs / 05-randomized-algorithms

Derandomization: Pairwise Independence and the Method of Conditional Expectations

shipped3 tiersLean: none

Anchor (Master): Arora and Barak 2009 Computational Complexity: A Modern Approach (Cambridge) Ch. 16; Nisan 1992 Pseudorandom Generators for Space-Bounded Computation (Combinatorica) (Nisan's generator, BPL = L, k-wise independence)

Intuition Beginner

A randomised algorithm flips coins to make decisions. Sometimes it performs well on average but poorly in the worst case. Derandomisation asks: can we replace the coin flips with deterministic choices that are just as good?

The answer is often yes, and the techniques are surprisingly concrete. The method of conditional expectations works by fixing one random bit at a time. At each step, you compute what happens if the bit is 0 versus 1, and choose the better option. Since the expectation over both choices is good, at least one choice must be good. Repeating this for every bit gives a deterministic solution as good as the expected random outcome.

Pairwise independence is another key tool. A collection of random variables is pairwise independent if every pair is independent, even though the whole collection may not be. This is much cheaper than full independence: you can generate $n$ pairwise independent bits from only $O (lo g n)$ truly random bits. If an algorithm only needs pairwise independence (and many do), you can reduce the randomness drastically.

Together, these techniques suggest a deeper conjecture: every efficient randomised algorithm has an efficient deterministic counterpart. This is the P = BPP conjecture, and while unproven, the derandomisation tools we have give substantial evidence in its favour.

Visual Beginner

Method of conditional expectations for MAX-CUT:

  Graph: a--b--c (3 vertices, 2 edges)
  
  Random partition: each vertex independently L/R
  Expected cut edges: 1.0 (each edge cut with prob 1/2)
  
  Fix v_a = L: E[cut | v_a=L] = 1/2 + 1/2 + 1/2 = 1.5
  
  Fix v_b = R (conditional on v_a = L):
    E[cut | v_a=L, v_b=R] = 1 + 1/2 = 1.5
  
  Fix v_c = L:
    Cut = {a-b: L,R = cut! b-c: R,L = cut!} = 2 edges
    Deterministic solution: 2 edges >= expected 1.0

Technique	Randomness reduction	Deterministic guarantee
Conditional expectations	Eliminates all randomness	Achieves expected value
Pairwise independence	$n$ bits from $O (lo g n)$ seed	Same variance properties
Nisan's PRG	$n$ bits from $O (lo g n)$ seed	Fool space-bounded machines

Worked example Beginner

We derandomise a simple randomised algorithm for MAX-CUT on a triangle graph with vertices ${a, b, c}$ and edges $(a, b), (b, c), (a, c)$ .

The randomised algorithm: assign each vertex independently and uniformly to side $L$ or $R$ . Each edge is cut (endpoints on different sides) with probability $1/2$ . The expected number of cut edges is $3 \times 1/2 = 1.5$ .

Derandomise via conditional expectations. Define $Z$ = number of cut edges.

Step 1. Compute $E [Z ∣ v_{a} = L]$ . Edges $(a, b)$ and $(a, c)$ are cut with prob $1/2$ each (since $v_{b}, v_{c}$ are random). Edge $(b, c)$ is cut with prob $1/2$ . So $E [Z ∣ v_{a} = L] = 1/2 + 1/2 + 1/2 = 1.5$ . Similarly $E [Z ∣ v_{a} = R] = 1.5$ . Both equal the unconditional expectation. Choose $v_{a} = L$ .

Step 2. Compute $E [Z ∣ v_{a} = L, v_{b} = L]$ . Edge $(a, b)$ : both $L$ , not cut. Edge $(a, c)$ : cut with prob $1/2$ . Edge $(b, c)$ : cut with prob $1/2$ . $E = 0 + 1/2 + 1/2 = 1.0$ .

Compute $E [Z ∣ v_{a} = L, v_{b} = R]$ . Edge $(a, b)$ : $L, R$ , cut. Edge $(a, c)$ : cut with prob $1/2$ . Edge $(b, c)$ : cut with prob $1/2$ . $E = 1 + 1/2 + 1/2 = 2.0$ .

$2.0 \geq 1.5$ , so choose $v_{b} = R$ .

Step 3. Compute $E [Z ∣ v_{a} = L, v_{b} = R, v_{c} = L]$ . Cut edges: $(a, b)$ yes, $(b, c)$ yes, $(a, c)$ yes. $Z = 3$ .

Compute $E [Z ∣ v_{a} = L, v_{b} = R, v_{c} = R]$ . Cut edges: $(a, b)$ yes, $(b, c)$ no, $(a, c)$ no. $Z = 1$ .

$3 \geq 2.0$ , so choose $v_{c} = L$ .

The deterministic partition ${a, c} \to L, {b} \to R$ cuts all 3 edges. The derandomised algorithm found the optimal max-cut.

Check your understanding Beginner

Formal definition Intermediate+

Definition (pairwise independence). Random variables $X_{1}, \dots, X_{n}$ over ${0, 1}$ are pairwise independent if for every $i \neq = j$ and every $a, b \in {0, 1}$ :

Pr [X_{i} = a \land X_{j} = b] = Pr [X_{i} = a] \cdot Pr [X_{j} = b] = \frac{1}{4} .

Definition (pairwise independent hash family). A family of functions $H = {h : [n] \to [m]}$ is pairwise independent if for uniformly random $h \in H$ , for all $i \neq = j$ and $a, b$ :

Pr [h (i) = a \land h (j) = b] = \frac{1}{m ^{2}} .

Definition (method of conditional expectations). Given a random variable $Z (X_{1}, \dots, X_{n})$ with $E [Z] \geq μ$ , the method fixes $X_{1}, \dots, X_{n}$ sequentially: at step $i$ , choose $x_{i} \in {0, 1}$ such that:

E [Z ∣ X_{1} = x_{1}, \dots, X_{i} = x_{i}] \geq E [Z ∣ X_{1} = x_{1}, \dots, X_{i - 1} = x_{i - 1}] .

Such an $x_{i}$ always exists because $E [Z ∣ \dots, X_{i - 1}] = \frac{1}{2} E [Z ∣ \dots, X_{i} = 0] + \frac{1}{2} E [Z ∣ \dots, X_{i} = 1]$ .

Definition (Nisan's pseudorandom generator). A PRG $G : {0, 1}^{s} \to {0, 1}^{n}$ $ε$ -fools space- $S$ algorithms if for every space- $S$ algorithm $A$ :

∣ r \in {0, 1}^{n} Pr [A (r) = 1] - z \in {0, 1}^{s} Pr [A (G (z)) = 1] ∣ \leq ε .

Counterexamples to common slips

"Pairwise independence implies full independence." No. Three pairwise independent bits $X_{1}, X_{2}, X_{3} = X_{1} \oplus X_{2}$ are pairwise independent but $X_{3}$ is determined by $X_{1}, X_{2}$ , so they are not fully independent.
"The method of conditional expectations works for any random variable." It requires that the conditional expectations $E [Z ∣ X_{1} = x_{1}, \dots, X_{i} = x_{i}]$ are efficiently computable. This is the case for many natural objectives (cut size, satisfied clauses) but not in general.
"Derandomisation means BPP = P." This is conjectured but not proven. The techniques here derandomise specific algorithms; a full derandomisation would require stronger pseudorandom generators than currently known.

Key theorem with proof Intermediate+

Theorem (derandomising MAX-CUT via conditional expectations). There is a deterministic polynomial-time algorithm that, given a graph $G = (V, E)$ , finds a partition cutting at least $∣ E ∣/2$ edges.

Proof. The randomised algorithm assigns each vertex independently to $L$ or $R$ with probability $1/2$ . Each edge $(u, v)$ is cut with probability $1/2$ (the two endpoints are in different sides). By linearity of expectation, the expected number of cut edges is $∣ E ∣/2$ .

For derandomisation, order the vertices $v_{1}, \dots, v_{n}$ . At step $i$ , the algorithm has fixed sides for $v_{1}, \dots, v_{i - 1}$ and computes:

E_{i} (0) = E [Z ∣ v_{1} = s_{1}, \dots, v_{i - 1} = s_{i - 1}, v_{i} = L]

E_{i} (1) = E [Z ∣ v_{1} = s_{1}, \dots, v_{i - 1} = s_{i - 1}, v_{i} = R]

where $Z$ is the number of cut edges. Since $v_{i}$ is uniform in the original algorithm:

\frac{E _{i} ( 0 ) + E _{i} ( 1 )}{2} = E [Z ∣ v_{1} = s_{1}, \dots, v_{i - 1} = s_{i - 1}] \geq \frac{∣ E ∣}{2} .

So $max (E_{i} (0), E_{i} (1)) \geq ∣ E ∣/2$ . Choose $s_{i}$ corresponding to the larger value.

After all $n$ steps, all vertices are fixed. The resulting partition cuts $Z$ edges, and $Z = E [Z ∣ v_{1} = s_{1}, \dots, v_{n} = s_{n}] \geq ∣ E ∣/2$ .

The conditional expectation at each step is computable in $O (∣ E ∣)$ time by summing over edges: for each edge $(u, v)$ , the probability it is cut given the current partial assignment depends only on whether $u$ and $v$ are already fixed. The total running time is $O (n ∣ E ∣)$ . $□$

Bridge. The method of conditional expectations is the foundational reason many randomised algorithms can be made deterministic: the existence of a good expected value guarantees that some deterministic choice achieves it, and sequential fixing finds that choice efficiently. This builds toward the more powerful derandomisation tools of Nisan's PRG which handles algorithms whose analysis requires more than expectation (e.g., variance, tail bounds). This is exactly the pattern that appears again in 47.05.01 where pairwise independent hash families reduce randomness for universal hashing, and it generalises to the conjecture BPP = P which would mean all efficient randomised algorithms can be derandomised. The central insight is that expectation-based derandomisation is a combinatorial shadow of the deeper algebraic structure of pseudorandomness, and putting these together with the randomised approximation schemes of 47.05.04 yields a complete toolkit: randomise for convenience, then derandomise for efficiency.

Exercises Intermediate+

Exercise 3 (medium, symbolic).

Derandomise the randomised 7/8-approximation for MAX-3SAT using the method of conditional expectations. Show that the deterministic algorithm satisfies at least $7 m /8$ clauses where $m$ is the total number of clauses.

Hint

Define $Z$ as the number of satisfied clauses. Show that $E [Z ∣ X_{1}, \dots, X_{i - 1}]$ can be computed by summing over clauses, and that fixing each variable maintains the invariant.

Answer

Let $Z$ be the number of satisfied clauses under a random assignment. $E [Z] = 7 m /8$ (each clause is satisfied with prob $7/8$ ). Order variables $x_{1}, \dots, x_{n}$ . At step $i$ , compute:

$E [Z ∣ x_{1} = v_{1}, \dots, x_{i - 1} = v_{i - 1}, x_{i} = 0]$ and $E [Z ∣ x_{1} = v_{1}, \dots, x_{i - 1} = v_{i - 1}, x_{i} = 1]$ .

For each clause $C_{j}$ : if $C_{j}$ is already satisfied by $x_{1}, \dots, x_{i - 1}$ , it contributes 1 to both expectations. If $C_{j}$ is already falsified (all its literals are false), it contributes 0 to both. If $C_{j}$ contains $x_{i}$ (or $\overset{x}{ˉ}_{i}$ ) and no earlier variable, fixing $x_{i}$ updates the probability of satisfaction.

Since the average of the two conditional expectations equals the current conditional expectation, which is at least $7 m /8$ by the invariant, the maximum is also at least $7 m /8$ . Fix $x_{i}$ to the value giving the larger conditional expectation.

After all $n$ variables are fixed, $Z = E [Z ∣ x_{1} = v_{1}, \dots, x_{n} = v_{n}] \geq 7 m /8$ . The assignment satisfies at least $7 m /8$ clauses. Running time: $O (nm)$ to evaluate all conditional expectations.

Exercise 5 (medium, short answer).

Explain why Nisan's PRG fools space-bounded machines but is not known to fool time-bounded machines. What is the key difference?

Answer

A space- $S$ machine has at most $2^{S}$ distinct configurations. Nisan's PRG uses a hybrid argument: partition the pseudorandom tape into blocks, and show that if the machine could distinguish block $k$ of the PRG from truly random bits, this would give a circuit that breaks the PRG's seed. The bound depends on the number of configurations, which is $2^{S}$ . For time- $T$ machines, the number of configurations is $2^{T}$ , so the argument gives a seed of length $O (T lo g T)$ , which is too large to be useful. The key difference is that space-bounded machines revisit configurations, allowing a recycling argument that time-bounded machines do not support.

Exercise 6 (hard, symbolic).

Construct a pairwise independent hash family $H = {h_{a, b} : {0, 1}^{k} \to {0, 1}^{k}}$ of size $2^{2 k}$ where $h_{a, b} (x) = a x + b$ over $F_{2^{k}}$ . Prove it satisfies the pairwise independence property.

Hint

For $x \neq = y$ , show that the pair $(h (x), h (y)) = (a x + b, a y + b)$ is uniform over $F_{2^{k}}^{2}$ when $a, b$ are uniform.

Answer

For $x \neq = y$ , the pair $(h_{a, b} (x), h_{a, b} (y)) = (a x + b, a y + b)$ . Given $(a, b)$ uniform over $F_{2^{k}}^{2}$ :

For any target $(u, v) \in F_{2^{k}}^{2}$ , we need $Pr [a x + b = u \land a y + b = v] = 1/ 2^{2 k}$ . The system is $a x + b = u, a y + b = v$ . Subtracting: $a (x - y) = u - v$ . Since $x \neq = y$ , $x - y \neq = 0$ , so $a = (u - v) (x - y)^{- 1}$ . Then $b = u - a x$ . This gives a unique $(a, b)$ for each $(u, v)$ , so $Pr = 1/∣ F_{2^{k}} ∣^{2} = 1/ 2^{2 k}$ . The family has size $2^{2 k}$ (indexed by $(a, b) \in F_{2^{k}}^{2}$ ) and the seed length is $2 k$ . Rubric: full credit for the field-inversion argument.

Exercise 7 (hard, symbolic).

Prove that BPL (bounded-error probabilistic logspace) is contained in $L^{3/2}$ (deterministic space $O (lo g^{3/2} n)$ ) using Nisan's PRG.

Hint

Use the PRG to generate pseudorandom tapes of length $n$ from seeds of length $O (lo g n \cdot S)$ , then enumerate all seeds in deterministic space $O (S + seed length)$ .

Answer

Let $M$ be a BPL machine using space $S = O (lo g n)$ and $n$ random bits. Nisan's PRG $G : {0, 1}^{O (S l o g n)} \to {0, 1}^{n}$ $ε$ -fools $M$ for $ε = 1/4$ .

The derandomised algorithm enumerates all $2^{O (S l o g n)}$ seeds $z$ . For each seed, it simulates $M$ using the pseudorandom tape $G (z)$ in space $S + O (S lo g n) = O (S lo g n)$ . It counts the fraction of seeds on which $M$ accepts.

If $x \in L$ , $M$ accepts with probability $\geq 2/3$ on truly random tapes. Since $G$ $ε$ -fools $M$ , the acceptance probability on pseudorandom tapes is $\geq 2/3 - 1/4 > 1/3$ . Similarly, if $x \in / L$ , it is $\leq 1/3 + 1/4 < 1/2$ .

The deterministic simulation uses space $O (S lo g n) = O (lo g n \cdot lo g n) = O (lo g^{2} n)$ . This gives BPL $\subseteq$ DSPACE $(lo g^{2} n) = L^{2}$ . Nisan's tighter analysis gives $L^{3/2}$ by recycling the seed across computation blocks. Rubric: full credit for the enumeration argument and space bound.

Exercise 8 (hard, short answer).

Why does the method of conditional expectations fail to derandomise FPRAS algorithms for counting problems like the permanent? What goes wrong?

Answer

The method of conditional expectations requires that the conditional expectation of the objective function is efficiently computable at each step. For an FPRAS like the Karp-Luby estimator for DNF counting or the JSV algorithm for the permanent, the objective is an estimate of a #P-complete quantity. Computing the conditional expectation at each step would require knowing (or being able to compute) partial counts, which is itself #P-hard. The self-reducibility telescoping product helps for some problems, but the intermediate conditional expectations are often as hard to compute as the original problem. Moreover, FPRAS algorithms use variance reduction (not just expectation), and conditional expectations alone cannot control variance. The derandomisation would need to preserve concentration properties, which the simple fixing method does not guarantee.

Lean formalization Intermediate+

Mathlib has pairwise independence in its probability theory library (Probability.Independence) but no connection to derandomisation. The method of conditional expectations has no formalization. Nisan's PRG is absent entirely. A natural formalization target would be a proof that the conditional-expectations method produces a partition achieving the expected cut size, using Mathlib's SimpleGraph and Finset structures for the graph. This unit ships without a lean_module.

Advanced results Master

Three directions push derandomisation beyond the basic techniques.

Result 1 (Nisan-Wigderson generator). For hardness-based derandomisation, the Nisan-Wigderson generator (1994) converts any function $f$ that is hard for circuits of size $s$ into a PRG that fools circuits of size $s^{'} < s$ . Given a function $f : {0, 1}^{l} \to {0, 1}$ that no circuit of size $2^{Ω (l)}$ can compute, the generator $G$ stretches $O (l)$ random bits to $2^{Ω (l)}$ pseudorandom bits. The construction uses a combinatorial design (a set system with small pairwise intersections) to extract many pseudorandom bits from a single hard function evaluation. The key theorem: if $E$ requires exponential-size circuits, then $B P P = P$ ^{[Arora-Barak Ch. 16]}.

Result 2 (Impagliazzo-Wigderson hardness-vs-randomness). Impagliazzo and Wigderson (1997) proved that if there exists a language in $E = D T I M E (2^{O (n)})$ that requires exponential-size circuits, then $B P P = P$ . This is the strongest known result connecting circuit lower bounds to derandomisation. The converse direction (derandomisation implies lower bounds) is also known in a weaker form: $B P P \neq = P$ implies circuit lower bounds. This establishes that derandomisation and circuit complexity are two faces of the same question ^{[Arora-Barak Ch. 16]}.

Result 3 (Reingold's theorem: SL = L). Omer Reingold (2005) proved that undirected $s$ - $t$ connectivity can be solved in deterministic logspace (SL = L). The algorithm uses the zig-zag product of expander graphs to transform any graph into an expander in logarithmic space, then performs a deterministic traversal. This is a landmark derandomisation result because randomised logspace algorithms for $s$ - $t$ connectivity (random walk on the graph) were known for decades, and derandomising them required fundamentally new graph-theoretic machinery ^{[Arora-Barak Ch. 16]}.

Synthesis. Derandomisation techniques form a hierarchy of power: conditional expectations handles expectation-based analyses, pairwise independence handles variance-based analyses, and pseudorandom generators handle arbitrary statistical tests. The central insight is that each level corresponds to a stronger notion of "randomness-like" behaviour, and this builds toward the hardness-versus-randomness paradigm where circuit lower bounds are the key to full derandomisation. This is exactly the pattern that appears again in 47.06.01 where one-way functions generate pseudorandomness for cryptographic purposes, and it generalises to the conjecture that BPP = P, which would mean that all efficient randomised algorithms are just efficient deterministic algorithms in disguise. Putting these together with the approximation algorithms of 47.04.08 and the FPRAS of 47.05.04 yields the full picture: randomness is a tool of convenience, not of necessity, and the boundary between randomised and deterministic computation maps directly to the boundary between known and unknown circuit lower bounds.

Full proof set Master

Proposition 1 (pairwise independent construction). For any prime power $q$ , there exists a pairwise independent hash family $H_{q, q} = {h_{a, b} : F_{q} \to F_{q}}$ of size $q^{2}$ where $h_{a, b} (x) = a x + b$ , with seed length $2 lo g q$ .

Proof. For any distinct $x, y \in F_{q}$ and any targets $u, v \in F_{q}$ :

a, b Pr [h_{a, b} (x) = u \land h_{a, b} (y) = v] = a, b Pr [a x + b = u \land a y + b = v] .

This is a system of two linear equations in two unknowns $(a, b)$ over $F_{q}$ . Subtracting gives $a (x - y) = u - v$ . Since $x \neq = y$ , $x - y \neq = 0$ and has an inverse in $F_{q}$ , so $a = (u - v) (x - y)^{- 1}$ is uniquely determined. Then $b = u - a x$ is also unique. So exactly one pair $(a, b) \in F_{q}^{2}$ satisfies the system, giving:

Pr = \frac{1}{q ^{2}} = \frac{1}{∣ F _{q} ∣} \cdot \frac{1}{∣ F _{q} ∣} .

This establishes pairwise independence. $□$

Proposition 2 (conditional expectations invariant). Let $Z = Z (X_{1}, \dots, X_{n})$ with $E [Z] \geq μ$ . Define $s_{i} = ar g max_{b \in {0, 1}} E [Z ∣ X_{1} = s_{1}, \dots, X_{i - 1} = s_{i - 1}, X_{i} = b]$ . Then $E [Z ∣ X_{1} = s_{1}, \dots, X_{k} = s_{k}] \geq μ$ for all $k$ .

Proof. By induction on $k$ . Base case $k = 0$ : $E [Z] \geq μ$ by assumption. Inductive step: assume $E [Z ∣ X_{1} = s_{1}, \dots, X_{k - 1} = s_{k - 1}] \geq μ$ . By the law of total expectation:

E [Z ∣ X_{1} = s_{1}, \dots, X_{k - 1} = s_{k - 1}] = \frac{1}{2} E [Z ∣ \dots, X_{k} = 0] + \frac{1}{2} E [Z ∣ \dots, X_{k} = 1] .

Since $s_{k} = ar g max_{b} E [Z ∣ \dots, X_{k} = b]$ , we have $E [Z ∣ \dots, X_{k} = s_{k}] \geq E [Z ∣ \dots, X_{k} = 0]$ and $E [Z ∣ \dots, X_{k} = s_{k}] \geq E [Z ∣ \dots, X_{k} = 1]$ . Therefore:

E [Z ∣ \dots, X_{k} = s_{k}] \geq \frac{1}{2} E [Z ∣ \dots, X_{k} = 0] + \frac{1}{2} E [Z ∣ \dots, X_{k} = 1] = E [Z ∣ X_{1} = s_{1}, \dots, X_{k - 1} = s_{k - 1}] \geq μ . □

Connections Master

47.05.01 — Universal hashing uses pairwise independence for bounded collision probability; this unit shows the same constructions serve as derandomisation tools.
47.03.01 — BPP is the class of problems with efficient randomised algorithms; derandomisation aims to show BPP = P, collapsing randomised and deterministic polynomial time.
47.06.01 — Pseudorandom generators for cryptography (based on one-way functions) are cousins of the PRGs used for derandomisation; the difference is that cryptographic PRGs must fool efficient adversaries, while derandomisation PRGs must fool specific algorithmic tests.
47.05.04 — FPRAS algorithms use randomness for approximate counting; derandomising them would give deterministic approximation schemes, but the conditional expectations method often fails because intermediate expectations are #P-hard to compute.

Historical & philosophical context Master

The method of conditional expectations was implicit in the work of Erdős and Selfridge (1973) on combinatorial games, and was formalised as a derandomisation tool by Beck and Spencer in the 1980s. Pairwise independent hash families were introduced by Carter and Wegman (1979) for universal hashing, and their derandomisation applications were developed by Alon, Babai and Itai (1986) and by Luby (1986).

Nisan's pseudorandom generator for space-bounded computation (1990) was a breakthrough, showing that RL (randomised logspace) is contained in L^{3/2}. Reingold's 2005 proof that SL = L was a landmark derandomisation, resolving a decades-old open problem using expander graph technology rather than pseudorandom generators directly.

The broader question—whether BPP = P—remains open. The Impagliazzo-Wigderson theorem (1997) shows it is equivalent to proving sufficiently strong circuit lower bounds. This places derandomisation squarely within the mainstream of complexity theory: understanding randomness in computation is inseparable from understanding the limits of efficient computation itself ^{[Arora-Barak Ch. 16]}.

Bibliography Master

@book{arora2009computational,
  author    = {Arora, Sanjeev and Barak, Boaz},
  title     = {Computational Complexity: A Modern Approach},
  publisher = {Cambridge University Press},
  year      = {2009},
}
@article{nisan1992pseudorandom,
  author  = {Nisan, Noam},
  title   = {Pseudorandom Generators for Space-Bounded Computation},
  journal = {Combinatorica},
  volume  = {12},
  number  = {4},
  pages   = {449--461},
  year    = {1992},
}
@article{reingold2005undirected,
  author  = {Reingold, Omer},
  title   = {Undirected Connectivity in Log-Space},
  journal = {Journal of the ACM},
  volume  = {55},
  number  = {4},
  year    = {2008},
}
@article{impagliazzo1997p,
  author  = {Impagliazzo, Russell and Wigderson, Avi},
  title   = {$P = BPP$ if $E$ Requires Exponential Circuits: Derandomizing the {XOR} Lemma},
  journal = {Proceedings of the 29th ACM Symposium on Theory of Computing},
  year    = {1997},
  pages   = {220--229},
}

Prerequisites

47.05.01

Tier anchors

beginner: Arora and Barak 2009 Computational Complexity: A Modern Approach (Cambridge) Ch. 16 (removing randomness from algorithms while preserving correctness)
intermediate: Arora and Barak 2009 Computational Complexity: A Modern Approach (Cambridge) Ch. 16 (pairwise independent hash families, conditional expectations method, deterministic MAX-CUT via semidefinite programming)
master: Arora and Barak 2009 Computational Complexity: A Modern Approach (Cambridge) Ch. 16; Nisan 1992 Pseudorandom Generators for Space-Bounded Computation (Combinatorica) (Nisan's generator, BPL = L, k-wise independence)

References

Arora, S. and Barak, B. — Computational Complexity: A Modern Approach · Cambridge University Press (2009). Chapter 16 develops derandomisation techniques, presenting pairwise independent hash families as constructions of $k$ random variables $X_{1}, \dots, X_{k}$ over $F_{2}$ such that for every pair $i \neq = j$ , $Pr [X_{i} = a \land X_{j} = b] = 1/4$ for all $a, b \in {0, 1}$ (achieved by choosing $X_{i} = a_{i} + b_{i} \cdot s$ for random seed $s \in F_{2^{k}}$ ); the method of conditional expectations for derandomising randomised algorithms, showing that if a random variable $Z = Z (X_{1}, \dots, X_{n})$ has $E [Z] \geq μ$ , then one can deterministically fix $X_{1}, \dots, X_{n}$ one at a time so that the conditional expectation never drops below $μ$ ; and Nisan's pseudorandom generator that stretches $O (lo g n)$ truly random bits to $n$ pseudorandom bits that fool space-bounded algorithms, proving $B P L \subseteq L^{3/2}$ .
Nisan, N. — Pseudorandom Generators for Space-Bounded Computation · Combinatorica 12(4):449--461 (1992). Constructs a pseudorandom generator $G : {0, 1}^{O (l o g n)} \to {0, 1}^{n}$ such that any space- $S$ algorithm cannot distinguish $G (s)$ from truly random bits, using a hybrid argument over computation steps and the observation that a space- $S$ machine has at most $2^{S}$ configurations; the seed length is $O (S lo g n)$ , giving $B P L \subseteq D S P A C E (S^{3/2})$ and in particular $B P L \subseteq L^{3/2}$ .

Estimated time

beginner: 15m
intermediate: 40m
master: 90m