ECCC-Report TR07-103https://eccc.weizmann.ac.il/report/2007/103Comments and Revisions published for TR07-103en-usFri, 19 Oct 2007 16:43:54 +0200
Paper TR07-103
| Selected Results in Additive Combinatorics: An Exposition |
Emanuele Viola
https://eccc.weizmann.ac.il/report/2007/103We 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.
Fri, 19 Oct 2007 16:43:54 +0200https://eccc.weizmann.ac.il/report/2007/103