Theory of Computing Library
Graduate Surveys 3
Graduate Surveys 3
Selected Results in Additive Combinatorics: An Exposition
Published: May 15, 2011 (15 pages)
Keywords: additive combinatorics, linearity testing
Categories: graduate survey, complexity theory, additive combinatorics, property testing, 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).
Licensed under a Creative Commons Attribution License (CC-BY)