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

We consider the task of testing properties of Boolean functions that
are invariant under linear transformations of the Boolean cube. Previous
work in property testing, including the linearity test and the test
for Reed-Muller codes, has mostly focused on such tasks for linear
properties. The one exception is a test ... more >>>

We study two conjectures in additive combinatorics. The first is the polynomial Freiman-Ruzsa conjecture, which relates to the structure of sets with small doubling. The second is the inverse Gowers conjecture for $U^ $, which relates to functions which locally look like quadratics. In both cases a weak form, with ... more >>>

A Locally Correctable Code (LCC) is an error correcting code that has a probabilistic
self-correcting algorithm that, with high probability, can correct any coordinate of the
codeword by looking at only a few other coordinates, even if a fraction $\delta$ of the
coordinates are corrupted. LCC's are a stronger form ... more >>>

Decomposition theorems in classical Fourier analysis enable us to express a bounded function in terms of few linear phases with large Fourier coefficients plus a part that is pseudorandom with respect to linear phases. The Goldreich-Levin algorithm can be viewed as an algorithmic analogue of such a decomposition as it ... more >>>

For a {0,1}-valued matrix $M$ let CC($M$) denote the deterministic communication complexity of the boolean function associated with $M$. The log-rank conjecture of Lovasz and Saks [FOCS 1988] states that CC($M$) is at most $\log^c({\mbox{rank}}(M))$ for some absolute constant $c$ where rank($M$) denotes the rank of $M$ over the field ... more >>>

Invariance with respect to linear or affine transformations of the domain is arguably the most common symmetry exhibited by natural algebraic properties. In this work, we show that any low complexity affine-invariant property of multivariate functions over finite fields is testable with a constant number of queries. This immediately reproves, ... more >>>

The polynomial Freiman-Ruzsa conjecture is one of the important conjectures in additive combinatorics. It asserts than one can switch between combinatorial and algebraic notions of approximate subgroups with only a polynomial loss in the underlying parameters. This conjecture has also already found several applications in theoretical computer science. Recently, Tom ... more >>>