Opening Sanders's Theorem (Analysis of Boolean Functions, CMU 15-859S, Lecture 22)
Sanders's Theorem (Analysis of Boolean Functions, CMU 15-859S, Lecture 22)
- Length
- 1 h 16 min
- Level
- Graduate
- Recorded
- Carnegie Mellon University2017
Chapter 1 of 8: Sanders's theorem
Combines Chang's lemma with the Croot-Sisask theorem to find a polylog-codimension subspace inside .
Sanders's theorem states that for any subset of with density , its sumset contains a large affine subspace of codimension bounded by a polylogarithmic function of . The lecture proves this result by combining Chang's lemma on the Fourier spectrum of dense sets with the Croot-Sisask theorem concerning translation-invariant statistical closeness of probability distributions. Through iterative convolutions, the argument shows that the sumset captures nearly all of the perpendicular space of the characters spanned by large Fourier coefficients. This structural guarantee implies the polynomial Freiman-Ruzsa conjecture when applied iteratively.
Sanders's theorem states that for any subset of with density , its sumset contains a large affine subspace of codimension bounded by a polylogarithmic function of . The lecture proves this result by combining Chang's lemma on the Fourier spectrum of dense sets with the Croot-Sisask theorem concerning translation-invariant statistical closeness of probability distributions. Through iterative convolutions, the argument shows that the sumset captures nearly all of the perpendicular space of the characters spanned by large Fourier coefficients. This structural guarantee implies the polynomial Freiman-Ruzsa conjecture when applied iteratively.

This lecture
Lecture 22 of 23 of Analysis of Boolean Functions.
Choose a node to see how it connects to this lecture. What comes before is on the leftat the top. What comes after is on the rightat the bottom. The ring is what it teaches. People and places are above. Other lectures and books are below.
Press a chosen node again to open it.
Your comment is kept while you sign up.Sign in