2025/04/09 by Michael Jaber, Jaber, Michael, Yang P. Liu +7 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory #Number Theory (math.NT)
paper · pdf · doi:10.48550/arxiv.2504.07006
openalex publication_date 2025/04/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let G be a finite abelian group and A be a subset of G × G which is corner--free, meaning that there are no x, y ∈ G and d ∈ G ∖ \0\ such that (x, y), (x+d, y), (x, y+d) ∈ A. We prove that |A| ≤ |G|2 ⋅ 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.