Oded's choices (Nr. 414)

Corners and Communication Complexity

a talk by Shachar Lovett (based on joint work with Michael Jaber, Yang P. Liu, Anthony Ostuni, and Mehtaab Sawhney)

Oded's comments

Needless to say, my interest in this topic arises from its relation to the problem of testinhyg traingle-freeness in the dense graph model. Thus, I found the overview orovided by Shachar most educational. The overview focused on a general introduction to the topic and a bird's eye description of the techniques involved.

The starting point is the 3-term arithmetic progression (3AP) priblem. The question is how large can a set $A \subset [N]$ be such that it contains no 3AP (i.e., no $x$ and $d$ such that $x,x+d,x+2d \in A$). Here is a brief history of the study of this question.

Erdos and Turan conjectured (in 1936) that $|A| \leq N^{1-\eps}$, for some positive constant $\eps$.
This was refuted by Behrend (in 1946), who showed that $|A| \geq N/\exp((\log N)^{1/2})$ may hold, using a construction of $A$ that still yields the best lower bound.
Roth (in 1952) proved that $|A| \leq N/(\log\log N))$, and this was later improved to $|A| \leq N/(\log N))$, by a sequence of works.
Recently, Kelley and Meka (in 2023) proved that $|A| \leq N/\exp((\log N)^{1/12})$, and this was later improved to $|A| \leq N/\exp((\log N)^{1/9})$.

The point is that the bounds are tight up to the constant exponent $e$ in $N/\exp((\log N)^e)$. A two-dimensional version of 3AP refers to a notion of a corner in $[N]^2$, which is a triplet $(x,y)$, $(x+d,y)$, $(x,y+d)$. The question here is how large can a set $A \subset [N]\times[N]$ be such that it contains no corner. Here is a brief history of the study of this question.

Ajtai and Szemeredi (1974) proved that $|A| \geq N^2/\exp((\log N)^{1/2})$ may hold.
Shkredov (in 2005 and then 2006) proved that $|A| \leq N^2/(\log\log N)^c)$ for some positiove $c$.
The current work shows that $|A| \leq N^2/\exp((\log N)^{1/600})$.

Again, the bounds are tight up to the constant exponent $e$ in $N^2/\exp((\log N)^e)$. The proof of the upper bound (as prior ones) uses a density amplification technique. Starting with a set $A_0=A$ of density $\rho$ in $U_0=[N]^2$, in each iteration the density increases withing a universe that does not shrink by too much; that is $|A_i|/|U_i|$ is larger than $|A_{i-1}|/|U_{i-1}|$ (by some factor), whereas $|U_i| = \Omega(|U_{i-1}|)$. Furthermore, $U_i$ maintains some structure that allows to carry out future iterations.

Original abstract

The corners problem is a classical problem in additive combinatorics. A corner is a triple of points (x,y), (x+d,y), (x,y+d). It can be viewed as a 2-dimensional analog of a (one-dimensional) 3-term arithmetic progression. An old question of Ajtai and Szemeredi is: how many points can there be in the n x n integer grid without containing a corner? They proved a qualitative bound of o(n^2), but no effective quantitative bounds.

This question has an equivalent description in the language of communication complexity. Given 3 players with inputs x,y,z which are integers in the range 1 to n, what is the most efficient Number-On-Forehead (NOF) deterministic protocol to check if they sum to n. This connection was first observed in the seminal paper of Chandra, Furst and Lipton that introduced the NOF model back in 1983.

In the language of communication complexity, the trivial protocol sends log(n) bits, but there is a better NOF protocol (based on constructions in additive combinatorics) which only sends (log n)^{1/2} bits. However, the best lower bound until our work was double exponentially far off - of the order of log log log n. In this work, we close this gap, and prove a lower bound of (log n)^c for some absolute constant c.

The work is based on combining the high-level approach of Shkredov, who obtained the previous lower bound, which was based on Fourier analysis; with the recent breakthrough of Kelley and Meka on the 3-term arithmetic progression problem, and the ensuing developments. The main message is that "spreadness" based techniques (a notion that I will explain in the talk) give significantly better quantitative bounds compared to classical Fourier analysis.

See arXiv 2504.07006.

Back to list of Oded's choices.