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.

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.

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

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.

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

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

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.

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.

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.

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

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.

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.

 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.

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.

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. 

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.

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

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

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.