ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR07-103 | 28th September 2007 00:00

Selected Results in Additive Combinatorics: An Exposition

RSS-Feed




TR07-103
Authors: Emanuele Viola
Publication: 19th October 2007 16:43
Downloads: 1075
Keywords: 


Abstract:

We give a self-contained exposition of selected results in additive
combinatorics over the group {0,1}^n. In particular, we prove the
celebrated theorems known as the Balog-Szemeredi-Gowers theorem ('94 and '98) and
the
Freiman-Ruzsa theorem ('73 and '99), leading to the remarkable result
by Samorodnitsky ('07) that linear transformations are efficiently testable.

No new result is proved here. However, we strip down the available proofs to the bare
minimum needed to derive the efficient testability of linear transformations over
{0,1}^n, thus hoping to provide a computer science-friendly introduction to the marvelous
field of additive combinatorics.



ISSN 1433-8092 | Imprint