Theory of Computing Library Graduate Surveys
---------------------------------------------------
Title : Selected Results in Additive Combinatorics: An Exposition
Authors : Emanuele Viola
Number : 3
Pages : 1-15
URL : http://www.theoryofcomputing.org/articles/gs003
Abstract
--------
We give a stripped-down, self-contained exposition of selected
results in additive combinatorics over the vector space
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-Szemeredi-Gowers
theorem (Combinatorica 1994 and GAFA 1998) and the
Freiman-Ruzsa theorem (AMS 1973 and Astérisque 1999).