Both topics in my title are well-known areas of research. What is perhaps less known is that there is a close and intimate relation between them. The most thoroughly studied part of communication complexity theory deals with the 2-players case: Two players are presented with a matrix $A$ (usually a 0-1 matrix) and they develop together their protocol. Then they get separated. One of them receives (secretly, only he sees the input) an index i and the other player receives likewise an input j. Their goal is to find out the value of $A_{ij}$ using as little communication as possible. There is a rich an beautiful theory that tells what can and cannot be done in such scenarios. What about 3 players or more? It turns out that the most interesting version of the problem is the number on the forehead (NOF) model, where the inputs are placed on the players' foreheads. Namely Player 1 gets to see inputs 2 and 3, Player 2 sees inputs 1 and 3 and Player 3 inputs 1 and 2. It turns out that all the rich machinery that was developed in the 2-players theory becomes essentially useless when 3 players or more are involved.
The corners theorem of Ajtai and Szemerédi says that for every $\epsilon>0$ and every $N > n_0(\epsilon)$, every set of $\epsilon N^2$ points in $[N]\times [N]$ contains a corner, i.e., three points of the form $(x,y)$, $(x+d,y)$, $(x, y+d)$. We still do not know much about how $n_0$ depends on $\epsilon$.
It may sound strange but these two problems are very closely related. I will first explain the connection and then show how algorithmic ideas in the NOF domain allow us to improve the known bounds on $n_0$.
This is joint work with Adi Shraibman.