Workshop on Additive Combinatorics, Oct. 2-6, 2017

The workshop on additive combinatorics will take place October 2-6, 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 Freiman-Ruzsa 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.

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

Co-organizers of this workshop include Ben Green, Swastik Kopparty, Ryan O’Donnell, Tamar Ziegler.

Monday, October 2

Time Speaker Title/Abstract
9:00-9:30am Breakfast  
9:30-10:20am Jacob Fox Tower-type 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 3-term 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 3-term 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 3-term 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 tower-type 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:20-11:00am Coffee Break  
11:00-11:50am Yufei Zhao Tower-type 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:00-1:30pm Lunch  
1:30-2: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, so-called 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 best-known 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:20-3:00pm Coffee Break  
3:00-3:50pm Fernando Shao  
4:00-6:00pm Welcome Reception

Tuesday, October 3

Time Speaker Title/Abstract
9:00-9:30am Breakfast
9:30-10: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:20-11:00am Coffee Break
11:00-11:50am Vsevolod Lev On Isoperimetric Stability

Abstract: We show that a non-empty subset of an abelian group with a small edge boundary must be large; in particular, if $A$ and $S$ are finite, non-empty subsets of an abelian group such that $S$ is independent, and the edge boundary of $A$ with respect to $S$ does not exceed $(1-c)|S||A|$ with a real $c\in(0,1]$, then $|A|\ge4^{(1-1/d)c|S|}$, 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, non-empty downset, then, denoting by $w(z)$ the number of non-zero 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:00-1:30pm Lunch
1:30-2:20pm Elena Grigorescu NP-Hardness of Reed-Solomon Decoding and the Prouhet-Tarry-Escott Problem

Abstract: I will discuss the complexity of decoding Reed-Solomon codes, and some results establishing NP-hardness 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 Prouhet-Tarry-Escott 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:20-3:00pm Coffee Break
3:00-3:50pm Sean Prendiville Partition regularity of certain non-linear 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 non-linear Diophantine equations in many variables.

Wednesday, October 4

Time Speaker Title/Abstract
9:00-9:30am Breakfast  
9:30-10: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 Behrend-style bounds using this method.

Joint work with Thomas Bloom.

10:20-11:00am Coffee Break  
11:00-11:50am Thomas Bloom  
12:00-1:30pm Lunch  
1:30-2: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:20-3:00pm Coffee Break
3:00-3: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 n-variate polynomial of total degree d factors nontrivially exactly when it has a (2, (d-1, d-1), 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 higher-order 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:00-9:30am Breakfast
9:30-10:20am Madhur Tulsiani Higher-order Fourier analysis and approximate decoding of Reed-Muller codes

 Abstract: Decomposition theorems proved by Gowers and Wolf provide an appropriate notion of “Fourier transform” for higher-order 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 Ben-Sasson, Pooya Hatami, Noga Ron-Zewi and Julia Wolf.

10:20-11:00am Coffee Break
11:00-11:50am Julia Wolf Stable arithmetic regularity

Joint work with Caroline Terry

12:00-1:30pm Lunch  
1:30-2:20pm Will Sawin  
2:20-3:00pm Coffee Break
3:00-3:50pm Mei-Chu 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 non-trivial arithmetic progressions of length r.

Friday, October 6

Time Speaker Title/Abstract
9:00-9:30am Breakfast
9:30-10:20am Asaf Ferber On a resilience version of the Littlewood-Offord problem

Abstract:  In this talk we consider a resilience version of the classical Littlewood-Offord problem. That is, consider the sum X=a_1x_1+…a_nx_n, where the a_i-s are non-zero reals and x_i-s 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_i-s  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:20-11:00am Coffee Break
11:00-11:50am Pooya Hatami
12:00-1:30pm Lunch
1:30-2:20pm Guy Kindler
2:20-3:00pm Coffee Break
3:00-3: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 co-dimension 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’ Bogolyubov-Ruzsa lemma.

Joint work with Hamed Hatami and Shachar Lovett


Comments are closed.