The Space Complexity of Sampling
summary
Shows explicit lower bounds: any read-once branching program of width 2^{0.01N} outputs a distribution exponentially far from the uniform distribution over a good code (constant rate and distance), and proves a direct product theorem for sampling with ROBPs that amplifies delta to exponential distance for T copies. Key tools are decomposing ROBP outputs into convex combinations of low-width product distributions, an anti‑concentration bound on Hamming balls, and a slice‑property amplification lemma.
AI-written summary · about