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

10/02/2017 6:00 pm - 10/06/2017 6:01 pm

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.

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:

Co-organizers of this workshop include Ben GreenSwastik KoppartyRyan O’DonnellTamar 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

Large deviations for arithmetic progressions

Abstract: We determine the asymptotics of the log-probability that the number of k-term arithmetic progressions in a random subset of integers exceeds its expectation by a constant factor. This is the arithmetic analog of subgraph counts in a random graph. I will highlight some open problems in additive combinatorics that we encountered in our work, namely concerning the “complexity” of the dual functions of AP-counts.

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 Bounds on capsets via properties of spectra

This is a continuation of the previous talk by Olof Sisask.

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

The arithmetic regularity lemma in the finite-field model, proved by Green in 2005, states that given a subset A of a finite-dimensional vector space over a prime field, there exists a subspace H of bounded codimension such that A is Fourier-uniform with respect to almost all cosets of H. It is known that in general, the growth of the codimension of H is required to be of tower type depending on the degree of uniformity, and that one must allow for a small number of non-uniform cosets.

Our main result is that, under a natural model-theoretic assumption of stability, the tower-type bound and non-uniform cosets in the arithmetic regularity lemma are not necessary.  Specifically, we prove an arithmetic regularity lemma for k-stable subsets in which the bound on the codimension of the subspace is a polynomial (depending on k) in the degree of uniformity, and in which there are no non-uniform cosets.

This is joint work with Caroline Terry.

12:00-1:30pm Lunch  
1:30-2:20pm Will Sawin

Constructions of Additive Matchings

Abstract: I will explain my work, with Robert Kleinberg and David Speyer, constructing large tri-colored sum-free sets in vector spaces over finite fields, and how it shows that some additive combinatorics problems over finite fields are harder than corresponding problems over the integers. 

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

12:00-1:30pm Lunch
1:30-2:20pm Guy Kindler

From the Grassmann graph to Two-to-Two games

Abstract: In this work we show a relation between the structure of the so called Grassmann graph over Z_2 and the Two-to-Two conjecture in computational complexity. Specifically, we present a structural conjecture concerning the Grassmann graph (together with an observation by Barak et. al., one can view this as a conjecture about the structure of non-expanding sets in that graph) which turns out to imply the Two-to-Two conjecture.

The latter conjecture its the lesser-known and weaker sibling of the Unique-Games conjecture [Khot02], which states that unique games (a.k.a. one-to-one games) are hard to approximate. Indeed, if the Grassmann-Graph conjecture its true, it would also rule out some attempts to refute the Unique-Games conjecture, as these attempts provide potentially efficient algorithms to solve unique games, that would actually also solve two-to-two games if they work at all.

These new connections between the structural properties of the Grassmann graph and complexity theoretic conjectures highlight the Grassmann graph as an interesting and worthy object of study. We may indicate some initial results towards analyzing its structure.

This is joint work with Irit Dinur, Subhash Khot, Dror Minzer, and Muli Safra.