Quasipolynomial Bounds for the Corners Theorem

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 \backslash\{0\}$ such that $(x, y),(x+d, y),(x, y+d) \in A$. We prove that equation*|A| |G|^2 (-(|G|)^1)equation*As a consequence, we obtain polynomial (in the input length) lower bounds on the non-deterministic 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 non-deterministic communication complexity of Exactly-N in the 4-player Number-on-Forehead model. This is an extended abstract. The full version of the paper can be found at https://arxiv.org/abs/2504.07006.