Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

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: 3266
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