The Zig-Zag Product and SL = L
Stub. Reingold's Zig-Zag product: an explicit, elementary combinatorial construction of bounded-degree expanders from a smaller expander, with provable expansion and clean composition behavior under iteration; and its most celebrated application, the proof that SL = L — undirected graph connectivity (a priori a symmetric-nondeterministic-space problem) is actually solvable in deterministic logarithmic space.
Corresponds to advanced course, Lectures 16–20. The last missing ingredient for explicit ε-biased distributions is an explicit, bounded-degree expander family, which the Zig-Zag product supplies: a combinatorial operation combining a large graph with a small one to produce a new, bounded-degree graph whose expansion is provably related to both inputs’, simple enough to iterate from a tiny base case up to any size needed, with no probabilistic or algebraic machinery required. Beyond its role as a pseudorandomness ingredient, the Zig-Zag product is the key tool in Reingold’s celebrated theorem SL = L: undirected graph connectivity — the canonical complete problem for symmetric logspace (SL, nondeterministic logspace with a symmetry restriction), and a priori a candidate for needing more than deterministic log space — is in fact solvable deterministically in log space, via repeatedly “squaring” the input graph’s expansion using the Zig-Zag product until connectivity becomes trivial to check, undoing the squaring carefully to stay within a logspace budget.
Outline (TODO — flesh out each)
- The Zig-Zag product — construction
- Expansion guarantees of the Zig-Zag product
- Composition behavior under iteration
- SL = L — undirected connectivity in deterministic log space
- Derandomized squaring of graphs
- The low-expansion-regime analysis and spectral gap lower bounds