Explicit Constructions of ε-Biased Distributions and Error-Correcting Codes

Corresponds to advanced course, Lectures 13–15. Having shown ε-biased distributions, ε-balanced codes, and spectral expanders are all the same object, this note carries out the “quest” to build one explicitly (no probabilistic existence argument, an actual polynomial-time-computable construction), needing three separate ingredients assembled in sequence. First, Reed-Muller codes (evaluations of low-degree polynomials over $\mathbb F_2$) and the Sipser-Spielman Tanner-graph construction give a good explicit binary LDPC code (constant rate, constant relative distance) built directly from a bipartite expander graph. An interlude covers the classical coding-theory background needed to appreciate this: the Hamming vs. Shannon (worst-case vs. average-case) noise models, list decoding, Reed-Solomon codes and the Singleton bound on their parameters, folded Reed-Solomon codes, and the Alon-Edmonds-Luby (AEL) construction, which uses an expander to approach list-decoding capacity. Second, derandomized XOR amplification shows that summing several ε-biased samples reduces bias multiplicatively, and doing the summing along an expander walk (rather than over all $2^k$ combinations) keeps the construction’s seed length small — analyzed via exponential decay of operator norms. The third ingredient, an explicit family of bounded-degree expanders, is exactly what the-zig-zag-product-and-sl-equals-l supplies.

Outline (TODO — flesh out each)

• Polynomials over $\mathbb F_2$ and Reed-Muller codes
• The Sipser-Spielman Tanner code construction of LDPC codes
• Interlude: Hamming vs. Shannon error models; list decoding
• Reed-Solomon codes; the Singleton bound; folded Reed-Solomon codes
• The Alon-Edmonds-Luby (AEL) construction; the generalized Singleton bound
• XOR/direct-sum amplification via complete hypergraphs
• Derandomized XOR amplification using expander walks
• Bias reduction in spectral terms; exponential decay of operator norms
• Assembling an explicit ε-biased distribution for arbitrary ε