Emanuele Viola

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

Arnab Bhattacharyya, Victor Chen, Madhu Sudan, Ning Xie

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

Shachar Lovett

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

Arnab Bhattacharyya, Zeev Dvir, Shubhangi Saraf, Amir Shpilka

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

Madhur Tulsiani, Julia Wolf

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

Eli Ben-Sasson, Shachar Lovett, Noga Ron-Zewi

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

Arnab Bhattacharyya, Eldar Fischer, Shachar Lovett

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

Shachar Lovett

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

Eli Ben-Sasson, Noga Ron-Zewi, Madhur Tulsiani, Julia Wolf

We give new combinatorial proofs of known almost-periodicity results for sumsets of sets with small doubling in the spirit of Croot and Sisask [Geom. Funct. Anal. 2010], whose almost-periodicity lemma has had far-reaching implications in additive combinatorics. We provide an alternative (and $L^p$-norm free) point of view, which allows for ... more >>>

Chaim Even-Zohar, Shachar Lovett

Let $G$ be a finite abelian group of torsion $r$ and let $A$ be a subset of $G$.

The Freiman-Ruzsa theorem asserts that if $|A+A| \le K|A|$

then $A$ is contained in a coset of a subgroup of $G$ of size at most $K^2 r^{K^4} |A|$. It was ...
more >>>

Daniel Apon, Jonathan Katz, Alex Malozemoff

We consider an instance of the following problem: Parties $P_1,..., P_k$ each receive an input $x_i$, and a coordinator (distinct from each of these parties) wishes to compute $f(x_1,..., x_k)$ for some predicate $f$. We are interested in one-round protocols where each party sends a single message to the coordinator; ... more >>>

Divesh Aggarwal, Yevgeniy Dodis, Shachar Lovett

Non-malleable codes provide a useful and meaningful security guarantee in situations where traditional error-correction (and even error-detection) is impossible; for example, when the attacker can completely overwrite the encoded message. Informally, a code is non-malleable if the message contained in a modified codeword is either the original message, or a ... more >>>

Eli Ben-Sasson, iddo Ben-Tov, Ivan Bjerre Damgard, Yuval Ishai, Noga Ron-Zewi

Several well-known public key encryption schemes, including those of Alekhnovich (FOCS 2003), Regev (STOC 2005), and Gentry, Peikert and Vaikuntanathan (STOC 2008), rely on the conjectured intractability of inverting noisy linear encodings. These schemes are limited in that they either require the underlying field to grow with the security parameter, ... more >>>

Naomi Kirshner, Alex Samorodnitsky

Given a subset $A\subseteq \{0,1\}^n$, let $\mu(A)$ be the maximal ratio between $\ell_4$ and $\ell_2$ norms of a function whose Fourier support is a subset of $A$. We make some simple observations about the connections between $\mu(A)$ and the additive properties of $A$ on one hand, and between $\mu(A)$ and ... more >>>

Amey Bhangale, Subhash Khot, Dor Minzer

For a prime $p$, a restricted arithmetic progression in $\mathbb{F}_p^n$ is a triplet of vectors $x, x+a, x+2a$ in which the common difference $a$ is a non-zero element from $\{0,1,2\}^n$. What is the size of the largest $A\subseteq \mathbb{F}_p^n$ that is free of restricted arithmetic progressions? We show that the ... more >>>