The method of conditional expectations derandomizes a randomized algorithm by doing what?
AReplacing all random bits with zeros
BGreedily fixing each random bit to the value that keeps the conditional expectation of the objective at least as good as the unconditional expectation
CRunning the randomized algorithm many times and taking the best result
DReplacing the random number generator with a hash function
The method of conditional expectations uses the probabilistic method constructively. If E[X] >= t, then at least one setting of the random bits achieves X >= t. Fix the first bit to whichever value (0 or 1) keeps E[X | b1] >= t. Then fix the second bit to maintain E[X | b1, b2] >= t, and so on. Each step is deterministic and computable (provided the conditional expectation can be efficiently evaluated), and the final fully-determined assignment achieves X >= t. This converts the randomized MAX-SAT 7/8-approximation into a deterministic one.
Question 2 Multiple Choice
A randomized algorithm uses n independent random bits, but its analysis only requires pairwise independence among O(n) random variables. How many truly random bits suffice for derandomization via pairwise-independent hash families?
AO(1) bits
BO(log n) bits
CO(n / log n) bits
DO(n) bits
A family of pairwise-independent random variables over {0,1}^n can be constructed from O(log n) truly random bits using linear hash functions over a finite field. Since only O(log n) seed bits are needed, we can enumerate all 2^O(log n) = poly(n) seeds deterministically, evaluate the algorithm on each, and return the best result. The total running time is polynomial times the original algorithm's running time. This technique derandomizes any algorithm whose correctness proof only uses pairwise independence (e.g., Chebyshev-based analyses).
Question 3 True / False
The Nisan-Wigderson pseudorandom generator construction assumes the existence of a function computable in E = DTIME(2^O(n)) that requires circuits of size 2^(epsilon * n). Under this assumption, BPP = P.
TTrue
FFalse
Answer: True
Nisan and Wigderson showed that a sufficiently hard function (hard for exponential-size circuits) can be used to construct a pseudorandom generator that stretches O(log n) random bits into poly(n) bits that are indistinguishable from truly random bits by any polynomial-size circuit. Since BPP algorithms are polynomial-size circuits, they cannot distinguish the pseudorandom bits from real randomness. Enumerating all poly(n) seeds (2^O(log n) of them) and taking a majority vote derandomizes any BPP algorithm. The assumption -- that E contains functions requiring exponential circuits -- is widely believed but unproven, which is why BPP = P remains a conjecture.
Question 4 Short Answer
Explain why expander graphs are useful for derandomization, particularly in the context of reducing the number of random bits needed for probability amplification.
Think about your answer, then reveal below.
Model answer: Standard probability amplification by independent repetition requires O(k) independent runs to reduce error to 2^(-k), using O(k * r) random bits if each run uses r bits. The expander walk technique replaces independent samples with a random walk on an expander graph whose vertices are the 2^r possible random strings. Starting from a random vertex and taking k steps on the expander uses only r + O(k) random bits total (r for the starting vertex, O(1) per step for the neighbor choice). The expander mixing lemma guarantees that the walk visits vertices that are 'nearly independent' -- specifically, the fraction of bad starting points that lead to too many failures along the walk decreases exponentially in k. This achieves the same exponential error reduction with far fewer random bits.
This is a key result by Ajtai-Komlos-Szemeredi and Impagliazzo-Zuckerman. The expander walk essentially provides a cheap source of nearly-independent samples. The savings from O(k * r) bits to r + O(k) bits can be dramatic -- for example, amplifying a BPP algorithm with error 1/3 to error 2^(-n) uses O(n * poly(n)) random bits naively but only poly(n) + O(n) bits with expander walks. Combined with the Nisan-Wigderson generator, this is part of the toolkit suggesting that randomness can be eliminated entirely under plausible complexity assumptions.