Integrated Calendar

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.

Joint work with Michael Jaber, Yang P. Liu, Anthony Ostuni and Mehtaab Sawhney


Paper will appear in FOCS 2025
https://arxiv.org/abs/2504.07006