Pseudorandomness — Expander Chernoff and ε-Biased Distributions

Corresponds to advanced course, Lecture 12. Classical Chernoff bounds need independent samples; the expander/matrix Chernoff bound shows a walk on an expander gives samples correlated enough to be far cheaper to generate (a short random seed, via the walk, instead of many independent random bits) yet still concentrated almost as tightly — a first concrete payoff of expanders as a “derandomization” tool, in the same spirit as the subgaussian concentration results of concentration-of-measure-for-bandits but for structured, not independent, randomness. $k$-wise independent generators are a different derandomization primitive: a small sample space that looks fully random to any test examining only $k$ coordinates at a time (enough to fool decision trees and low-degree polynomials). ε-biased distributions push this further, fooling every Fourier character (not just low-degree ones) up to bias $\varepsilon$, and are shown equivalent (the pseudorandom triad) to two other objects: ε-balanced codes (coding-theoretic) and ε-spectral expanders over $\mathbb Z_2^n$ (graph-theoretic) — three different-looking objects that are secretly the same, which is exactly why the explicit constructions in the next note can freely borrow tools across all three.

Outline (TODO — flesh out each)

• The expander (matrix) Chernoff bound
• Expansion of Cayley graphs over general groups
• $k$-wise independent generators — fooling decision trees and low-degree polynomials
• ε-biased distributions — fooling all Fourier characters
• ε-balanced codes
• The pseudorandom triad: ε-biased distributions, ε-balanced codes, ε-spectral expanders