pdf icon
Theory of Computing Library
Graduate Surveys 3
Selected Results in Additive Combinatorics: An Exposition
Published: May 15, 2011    (15 pages)
Download article from ToC site:
[PDF (232K)]    [PS (819K)]    [PS.GZ (244K)]
[Source ZIP]
Keywords: additive combinatorics, linearity testing
ACM Classification: F.1.2, F.2.2
AMS Classification: 05D99

Abstract: [Plain Text Version]

We give a stripped-down, self-contained exposition of selected results in additive combinatorics over the vector space ${\mathbb F}_2^n$, leading to the result by Samorodnitsky (STOC 2007) stating that linear transformations are efficiently testable. In particular, we prove the theorems known as the Balog-Szemerédi-Gowers theorem (Combinatorica 1994 and GAFA 1998) and the Freiman-Ruzsa theorem (AMS 1973 and Astérisque 1999).