Theory of Computing Library
Graduate Surveys 3

Selected Results in Additive Combinatorics: An Exposition

by Emanuele Viola

Published: May 15, 2011    (15 pages)

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).

DOI: 10.4086/toc.gs.2011.003

© 2011 Emanuele Viola
Licensed under a Creative Commons Attribution License (CC-BY)