Bounded Independence Plus Noise, and the Communication Complexity of Decoding

on YouTube ↗34m

" summary

Proves that bounded-independence plus small-noise fools products of K functions once T is about the row length L, giving error exponentially small in T (removing dependence on K), using a concrete Fourier high/low decomposition plus Cauchy‑Schwarz to make noise kill high coefficients. Applies this to multi‑party decoding of Reed–Solomon: recovering one symbol when a codeword has e errors requires Ω(e) bits of communication (up to logs), a tight lower bound. The work combines explicit spectral bounds with communication‑complexity reductions.

AI-written summary · about

" chapters (13)

1. 0:00Introduction
2. 2:13Noise and noisy independence
3. 4:02Prior work on fooling distributions
4. 5:08Product testers and D+N
5. 8:59Pseudorandomness applications
6. 10:27Decoding communication complexity
7. 12:47Reed-Solomon setup
8. 16:25Lower bound proof sketch
9. 20:36Fourier analysis technique
10. 28:43Open questions
11. 30:17Decoding in small classes
12. 31:48DNF lower bounds
13. 33:56Q&A