Quasipolynomial bounds for the corners theorem

Abstract

Let $G$ be a finite abelian group and $A$ be a subset of $G\times G$ which is corner--free, meaning that there are no $x,y\in G$ and $d\in G\setminus \{0\}$ such that $(x,y)$, $(x+d,y)$, $(x,y+d)\in A$. We prove that \[|A| \le |G|^2 \cdot \exp(-(\log |G|)^{Ω(1)}).\] As a consequence, we obtain polynomial (in the input length) lower bounds on the nondeterministic communication complexity of Exactly-N in the 3-player Number-on-Forehead model. We also obtain the first "reasonable'' lower bounds on the coloring version of the $3$-dimensional corners problem, as well as on the nondeterministic communication complexity of Exactly-N in the 4-player Number-on-Forehead model.

73 pages