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 \begin{equation*}|A| \leq|G|^{2} \cdot \exp \left(-(\log |G|)^{\Omega{1}}\right)\end{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.

We define a class of problems whose input is an n-sized set of d-dimensional vectors, and where the problem is first-order definable using comparisons between coordinates. This class captures a wide variety of tasks, such as complex types of orthogonal range search, model-checking first-order properties on geometric intersection graphs, and elementary questions on multidimensional data like verifying Pareto optimality of a choice of data points. Focusing on constant dimension d, we show that any k-quantifier, d-dimensional such problem is solvable in O(n^{k-1} log^{d-1} n) time. Furthermore, this algorithm is conditionally tight up to subpolynomial factors: we show that assuming the 3-uniform hyperclique hypothesis, there is a k-quantifier, (3k-3)-dimensional problem in this class that requires time Ω(n^{k-1-o(1)}). Towards identifying a single representative problem for this class, we study the existence of complete problems for the 3-quantifier setting (since 2-quantifier problems can already be solved in near-linear time O(nlog^{d-1} n), and k-quantifier problems with k > 3 reduce to the 3-quantifier case). We define a problem Vector Concatenated Non-Domination VCND_d (Given three sets of vectors X,Y and Z of dimension d,d and 2d, respectively, is there an x ∈ X and a y ∈ Y so that their concatenation x∘y is not dominated by any z ∈ Z, where vector u is dominated by vector v if u_i ≤ v_i for each coordinate 1 ≤ i ≤ d), and determine it as the "unique" candidate to be complete for this class (under fine-grained assumptions).