What will be the next polymath project? click here for our previous post.
Number on the forehead, communication complexity, and additive combinatorics
Larger Corner-Free Sets from Better NOF Exactly-N Protocols, by Nati Linial and Adi Shraibman
Abstract: A subset of the integer planar grid [N]×[N] is called corner-free if it contains no triple of the form (x,y),(x+δ,y),(x,y+δ). It is known that such a set has a vanishingly small density, but how large this density can be remains unknown. The best previous construction was based on Behrend’s large subset of [N] with no 3-term arithmetic progression. Here we provide the first substantial improvement to this lower bound in decades. Our approach to the problem is based on the theory of communication complexity.
In the 3-players exactly-N problem the players need to decide whether x+y+z=N for inputs x,y,z and fixed N. This is the first problem considered in the multiplayer Number On the Forehead (NOF) model. Despite the basic nature of this problem, no progress has been made on it throughout the years. Only recently have explicit protocols been found for the first time, yet no improvement in complexity has been achieved to date. The present paper offers the first improved protocol for the exactly-N problem. This is also the first significant example where algorithmic ideas in communication complexity bear fruit in additive combinatorics.
This is remarkable for various reasons. On the additive combinatorics side, improved constructions are rare. For example, we reported here in 2008 Elkin’s (small) improvements of Behrend’s bound. For the corner-free problem the paper of Nati and Adi goes beyond the Behrend’s (and Elkin’s) constructions. On the communication complexity side this is significant progress on a classical 1983 problem of Chandra, Furst and Lipton. The connection that goes from improved result on communication complexity to additive combinatorics is exciting — certainly a new frontier for Nati and Adi. On the blogging side, I cannot compete with the beautifully written introduction. Click here to read the paper.
Remark 1: The number of the forehead problem is related to Levine’s hat problem that we discussed in this post.
Remark 2: Ryan Alweiss just told me about Ben Green’s new paper New lower bounds for van der Waerden numbers. It gives a construction of a red blue colouring of {1,2,…,N} with no 3 term blue or a k-term red arithmetic progression, where N is super-polynomial! Stay tune for a fuller report.
In Remark 2 I would say “N is super-polynomial”: “N is quasi-polynomial” sounds like an upper bound.
GK: Thanks, Fedor! corrected!
Pingback: To cheer you up in difficult times 20: Ben Green presents super-polynomial lower bounds for off-diagonal van der Waerden numbers W(3,k) | Combinatorics and more
Ben Green just posted a 2-page paper https://arxiv.org/abs/2102.11702 where he improved even further the new lower bound of Nati and Adi. Ben wrote: The construction came about by a careful study of the recent preprint of Linial and Shraibman, where they used ideas from communication complexity to obtain a bound with
≈ 2.402… , improving on the previously best known bound with
≈ 2.828…, which comes from Behrend’s construction. By bypassing the language of communication complexity one may simplify the construction, in particular avoiding the use of entropy methods. This yields a superior bound.”
≈ 1.822…