The workshop on additive combinatorics will take place October 26, 2017 at the Center of Mathematical Sciences and Applications, located at 20 Garden Street, Cambridge, MA.
Additive combinatorics is a mathematical area bordering on number theory, discrete mathematics, harmonic analysis and ergodic theory. It has achieved a number of successes in pure mathematics in the last two decades in quite diverse directions, such as:
 The first sensible bounds for Szemerédi’s theorem on progressions (Gowers);
 Linear patterns in the primes (Green, Tao, Ziegler);
 Construction of expanding sets in groups and expander graphs (Bourgain, Gamburd);
 The Kakeya Problem in Euclidean harmonic analysis (Bourgain, Katz, Tao).
Ideas and techniques from additive combinatorics have also had an impact in theoretical computer science, for example
 Constructions of pseudorandom objects (eg. extractors and expanders);
 Constructions of extremal objects (eg. BCH codes);
 Property testing (eg. testing linearity);
 Algebraic algorithms (eg. matrix multiplication).
The main focus of this workshop will be to bring together researchers involved in additive combinatorics, with a particular inclination towards the links with theoretical computer science. Thus it is expected that a major focus will be additive combinatorics on the boolean cube (Z/2Z)^n , which is the object where the exchange of ideas between pure additive combinatorics and theoretical computer science is most fruitful. Another major focus will be the study of pseudorandom phenomena in additive combinatorics, which has been an important contributor to modern methods of generating provably good randomness through deterministic methods. Other likely topics of discussion include the status of major open problems (the polynomial FreimanRuzsa conjecture, inverse theorems for the Gowers norms with bounds, explicit correlation bounds against low degree polynomials) as well as the impact of new methods such as the introduction of algebraic techniques by Croot–Pach–Lev and Ellenberg–Gijswijt.
Participation: The workshop is open to participation by all interested researchers, subject to capacity. Click here to register.
A list of lodging options convenient to the Center can also be found on our recommended lodgings page.
Confirmed participants include:
 Arnab Bhattacharyya (Indian Institute of Science)
 Thomas Bloom (University of Bristol)
 Jop Briët (Centrum Wiskunde & Informatica, Amsterdam)
 MeiChu Chang (University of California, Riverside)
 Noam Elkies (Harvard University)
 Asaf Ferber (MIT)
 Jacob Fox (Stanford University)
 Shafi Goldwasser (MIT)
 Elena Grigorescu (Purdue University)
 Hamed Hatami (McGill University)
 Pooya Hatami (Institute for Advanced Study)
 Kaave Hosseini (University of California, San Diego)
 Guy Kindler (Hebrew University of Jerusalem)
 Vsevolod Lev (University of Haifa at Oranim)
 Sean Prendiville (University of Manchester)
 Ronitt Rubinfeld (MIT)
 Will Sawin (ETH Zürich)
 Fernando Shao (Oxford University)
 Olof Sisask (KTH Royal Institute of Technology)
 Madhur Tulsiani (University of Chicago)
 Julia Wolf (University of Bristol)
 Emanuele Viola (Northeastern University)
 Yufei Zhao (MIT)
Coorganizers of this workshop include Ben Green, Swastik Kopparty, Ryan O’Donnell, Tamar Ziegler.
Monday, October 2
Time  Speaker  Title/Abstract 
9:009:30am  Breakfast  
9:3010:20am  Jacob Fox  Towertype bounds for Roth’s theorem with popular differences
Abstract: A famous theorem of Roth states that for any $\alpha > 0$ and $n$ sufficiently large in terms of $\alpha$, any subset of $\{1, \dots, n\}$ with density $\alpha$ contains a 3term arithmetic progression. Green developed an arithmetic regularity lemma and used it to prove that not only is there one arithmetic progression, but in fact there is some integer $d > 0$ for which the density of 3term arithmetic progressions with common difference $d$ is at least roughly what is expected in a random set with density $\alpha$. That is, for every $\epsilon > 0$, there is some $n(\epsilon)$ such that for all $n > n(\epsilon)$ and any subset $A$ of $\{1, \dots, n\}$ with density $\alpha$, there is some integer $d > 0$ for which the number of 3term arithmetic progressions in $A$ with common difference $d$ is at least $(\alpha^3\epsilon)n$. We prove that $n(\epsilon)$ grows as an exponential tower of 2’s of height on the order of $\log(1/\epsilon)$. We show that the same is true in any abelian group of odd order $n$. These results are the first applications of regularity lemmas for which the towertype bounds are shown to be necessary. The first part of the talk by Jacob Fox includes an overview and discusses the upper bound. The second part of the talk by Yufei Zhao focuses on the lower bound construction and proof. These results are all joint work with Huy Tuan Pham. 
10:2011:00am  Coffee Break  
11:0011:50am  Yufei Zhao  Towertype bounds for Roth’s theorem with popular differences
Abstract: Continuation of first talk by Jacob Fox. The first part of the talk by Jacob Fox includes an overview and discusses the upper bound. The second part of the talk by Yufei Zhao focuses on the lower bound construction and proof. These results are all joint work with Huy Tuan Pham. 
12:001:30pm  Lunch  
1:302:20pm  Jop Briët  Locally decodable codes and arithmetic progressions in random settings
Abstract: This talk is about a common feature of special types of error correcting codes, socalled locally decodable codes (LDCs), and two problems on arithmetic progressions in random settings, random differences in Szemerédi’s theorem and upper tails for arithmetic progressions in a random set in particular. It turns out that all three can be studied in terms of the Gaussian width of a set of vectors given by a collection of certain polynomials. Using a matrix version of the Khintchine inequality and a lemma that turns such polynomials into matrices, we give an alternative proof for the bestknown lower bounds on LDCs and improved versions of prior results due to Frantzikinakis et al. and Bhattacharya et al. on arithmetic progressions in the aforementioned random settings. Joint work with Sivakanth Gopi 
2:203:00pm  Coffee Break  
3:003:50pm  Fernando Shao  
4:006:00pm  Welcome Reception 
Tuesday, October 3
Time  Speaker  Title/Abstract 
9:009:30am  Breakfast  
9:3010:20am  Emanuele Viola  Interleaved group products
Authors: Timothy Gowers and Emanuele Viola Abstract: Let G be the special linear group SL(2,q). We show that if (a1,a2) and (b1,b2) are sampled uniformly from large subsets A and B of G^2 then their interleaved product a1 b1 a2 b2 is nearly uniform over G. This extends a result of Gowers (2008) which corresponds to the independent case where A and B are product sets. We obtain a number of other results. For example, we show that if X is a probability distribution on G^m such that any two coordinates are uniform in G^2, then a pointwise product of s independent copies of X is nearly uniform in G^m, where s depends on m only. Similar statements can be made for other groups as well. These results have applications in computer science, which is the area where they were first sought by Miles and Viola (2013). 
10:2011:00am  Coffee Break  
11:0011:50am  Vsevolod Lev  On Isoperimetric Stability
Abstract: We show that a nonempty subset of an abelian group with a small edge boundary must be large; in particular, if $A$ and $S$ are finite, nonempty subsets of an abelian group such that $S$ is independent, and the edge boundary of $A$ with respect to $S$ does not exceed $(1c)SA$ with a real $c\in(0,1]$, then $A\ge4^{(11/d)cS}$, where $d$ is the smallest order of an element of $S$. Here the constant $4$ is best possible. As a corollary, we derive an upper bound for the size of the largest independent subset of the set of popular differences of a finite subset of an abelian group. For groups of exponent $2$ and $3$, our bound translates into a sharp estimate for the additive dimension of the popular difference set. We also prove, as an auxiliary result, the following estimate of possible independent interest: if $A\subseteq{\mathbb Z}^n$ is a finite, nonempty downset, then, denoting by $w(z)$ the number of nonzero components of the vector $z\in\mathbb{Z}^n$, we have $$ \frac1{A} \sum_{a\in A} w(a) \le \frac12\, \log_2 A. $$ 
12:001:30pm  Lunch  
1:302:20pm  Elena Grigorescu  NPHardness of ReedSolomon Decoding and the ProuhetTarryEscott Problem
Abstract: I will discuss the complexity of decoding ReedSolomon codes, and some results establishing NPhardness for asymptotically smaller decoding radii than the maximum likelihood decoding radius. These results follow from the study of a generalization of the classical Subset Sum problem to higher moments, which may be of independent interest. I will further discuss a connection with the ProuhetTarryEscott problem studied in Number Theory, which turns out to capture a main barrier in extending our techniques to smaller radii. Joint work with Venkata Gandikota and Badih Ghazi. 
2:203:00pm  Coffee Break  
3:003:50pm  Sean Prendiville  Partition regularity of certain nonlinear Diophantine equations.
Abstract: We survey some results in additive Ramsey theory which remain valid when variables are restricted to sparse sets of arithmetic interest, in particular the partition regularity of a class of nonlinear Diophantine equations in many variables. 
Wednesday, October 4
Time  Speaker  Title/Abstract 
9:009:30am  Breakfast  
9:3010:20am  Olof Sisask  Bounds on capsets via properties of spectra
Abstract: A capset in F_3^n is a subset A containing no three distinct elements x, y, z satisfying x+z=2y. Determining how large capsets can be has been a longstanding problem in additive combinatorics, particularly motivated by the corresponding question for subsets of {1,2,…,N}. While the problem in the former setting has seen spectacular progress recently through the polynomial method of Croot–Lev–Pach and Ellenberg–Gijswijt, such progress has not been forthcoming in the setting of the integers. Motivated by an attempt to make progress in this setting, we shall revisit the approach to bounding the sizes of capsets using Fourier analysis, and in particular the properties of large spectra. This will be a two part talk, in which many of the ideas will be outlined in the first talk, modulo the proof of a structural result for sets with large additive energy. This structural result will be discussed in the second talk, by Thomas Bloom, together with ideas on how one might hope to achieve Behrendstyle bounds using this method. Joint work with Thomas Bloom. 
10:2011:00am  Coffee Break  
11:0011:50am  Thomas Bloom  
12:001:30pm  Lunch  
1:302:20pm  Hamed Hatami  Polynomial method and graph bootstrap percolation
Abstract: We introduce a simple method for proving lower bounds for the size of the smallest percolating set in a certain graph bootstrap process. We apply this method to determine the sizes of the smallest percolating sets in multidimensional tori and multidimensional grids (in particular hypercubes). The former answers a question of Morrison and Noel, and the latter provides an alternative and simpler proof for one of their main results. This is based on a joint work with Lianna Hambardzumyan and Yingjie Qian. 
2:203:00pm  Coffee Break  
3:003:50pm  Arnab Bhattacharyya  Algorithmic Polynomial Decomposition
Abstract: Fix a prime p. Given a positive integer k, a vector of positive integers D = (D_1, …, D_k) and a function G: F_p^k → F_p, we say a function P: F_p^n → F_p admits a (k, D, G)decomposition if there exist polynomials P_1, …, P_k: F_p^n > F_p with each deg(P_i) <= D_i such that for all x in F_p^n, P(x) = G(P_1(x), …, P_k(x)). For instance, an nvariate polynomial of total degree d factors nontrivially exactly when it has a (2, (d1, d1), prod)decomposition where prod(a,b) = ab. When show that for any fixed k, D, G, and fixed bound d, we can decide whether a given polynomial P(x_1, …, x_n) of degree d admits a (k,D,G)decomposition and if so, find a witnessing decomposition, in poly(n) time. Our approach is based on higherorder Fourier analysis. We will also discuss improved analyses and algorithms for special classes of decompositions. Joint work with Pooya Hatami, Chetan Gupta and Madhur Tulsiani. 
Thursday, October 5
Time  Speaker  Title/Abstract 
9:009:30am  Breakfast  
9:3010:20am  Madhur Tulsiani  Higherorder Fourier analysis and approximate decoding of ReedMuller codes
Abstract: Decomposition theorems proved by Gowers and Wolf provide an appropriate notion of “Fourier transform” for higherorder Fourier analysis. I will discuss some questions and techniques that arise from trying to develop polynomial time algorithms for computing these decompositions. I will discuss constructive proofs of these decompositions based on boosting, which reduce the problem of computing these decompositions to a certain kind of approximate decoding problem for codes. I will also discuss some earlier and recent works on this decoding problem. Based on joint works with Arnab Bhattacharyya, Eli BenSasson, Pooya Hatami, Noga RonZewi and Julia Wolf. 
10:2011:00am  Coffee Break  
11:0011:50am  Julia Wolf  Stable arithmetic regularity
Joint work with Caroline Terry 
12:001:30pm  Lunch  
1:302:20pm  Will Sawin  
2:203:00pm  Coffee Break  
3:003:50pm  MeiChu Chang  Arithmetic progressions in multiplicative groups of finite fields
Abstract: Let G be a multiplicative subgroup of the prime field F_p of size G> p^{1\kappa} and r an arbitrarily fixed positive integer. Assuming \kappa=\kappa(r)>0 and p large enough, it is shown that any proportional subset A of G contains nontrivial arithmetic progressions of length r. 
Friday, October 6
Time  Speaker  Title/Abstract 
9:009:30am  Breakfast  
9:3010:20am  Asaf Ferber  On a resilience version of the LittlewoodOfford problem
Abstract: In this talk we consider a resilience version of the classical LittlewoodOfford problem. That is, consider the sum X=a_1x_1+…a_nx_n, where the a_is are nonzero reals and x_is are i.i.d. random variables with (x_1=1)= P(x_1=1)=1/2. Motivated by some problems from random matrices, we consider the question: how many of the x_is can we typically allow an adversary to change without making X=0? We solve this problem up to a constant factor and present a few interesting open problems. Joint with: Afonso Bandeira (NYU) and Matthew Kwan (ETH, Zurich). 
10:2011:00am  Coffee Break  
11:0011:50am  Pooya Hatami  
12:001:30pm  Lunch  
1:302:20pm  Guy Kindler  
2:203:00pm  Coffee Break  
3:003:50pm  Kaave Hosseini  Protocols for XOR functions and Entropy decrement
Abstract: Let f:F_2^n –> {0,1} be a function and suppose the matrix M defined by M(x,y) = f(x+y) is partitioned into k monochromatic rectangles. We show that F_2^n can be partitioned into affine subspaces of codimension polylog(k) such that f is constant on each subspace. In other words, up to polynomial factors, deterministic communication complexity and parity decision tree complexity are equivalent. This relies on a novel technique of entropy decrement combined with Sanders’ BogolyubovRuzsa lemma. Joint work with Hamed Hatami and Shachar Lovett
