Geodesic
Larger Corner-Free Sets from Better NOF Exactly-$N$ Protocols
Discrete analysis (2021) Cet article a éte moissonné depuis la source Scholastica

Voir la notice de l'article

A subset of the integer planar grid $[N] \times [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.
Publié le : 
@article{DAS_2021_a7,
     author = {Nati Linial and Adi Shraibman},
     title = {Larger {Corner-Free} {Sets} from {Better} {NOF} {Exactly-}$N$ {Protocols}},
     journal = {Discrete analysis},
     year = {2021},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DAS_2021_a7/}
}
TY  - JOUR
AU  - Nati Linial
AU  - Adi Shraibman
TI  - Larger Corner-Free Sets from Better NOF Exactly-$N$ Protocols
JO  - Discrete analysis
PY  - 2021
UR  - http://geodesic.mathdoc.fr/item/DAS_2021_a7/
LA  - en
ID  - DAS_2021_a7
ER  - 
%0 Journal Article
%A Nati Linial
%A Adi Shraibman
%T Larger Corner-Free Sets from Better NOF Exactly-$N$ Protocols
%J Discrete analysis
%D 2021
%U http://geodesic.mathdoc.fr/item/DAS_2021_a7/
%G en
%F DAS_2021_a7
Nati Linial; Adi Shraibman. Larger Corner-Free Sets from Better NOF Exactly-$N$ Protocols. Discrete analysis (2021). http://geodesic.mathdoc.fr/item/DAS_2021_a7/