Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR25-047 | 10th April 2025 05:30

Quasipolynomial bounds for the corners theorem

RSS-Feed




TR25-047
Authors: Michael Jaber, Yang P. Liu, Shachar Lovett, Anthony Ostuni, Mehtaab Sawhney
Publication: 13th April 2025 09:54
Downloads: 69
Keywords: 


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|)^{\Omega(1)}).$
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 and equivalently the deterministic communication complexity of Exactly-N in the 4-player Number-on-Forehead model.



ISSN 1433-8092 | Imprint