REVIEW 2 cited by
Quasipolynomial bounds for the corners theorem
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
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|)^{\Omega(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.
Forward citations
Cited by 2 Pith papers
-
On hyperbolic corners and unit-area triangles in planar sets of large measure
Measurable sets in [0,R]² avoiding upward right triangles of area 1/2 satisfy |A| = O_c(R²/(log R)^c) for c<1/4 with Ω(R log R) example; for fixed-area triangles the bound sharpens to c<1/2 using a hyperbolic trilinea...
-
Polynomial Corners Over finite Fields
In (F_p)^2, any set avoiding the polynomial corner configuration has density o(1) as p grows, with a bound stronger than the corresponding integer result under stated conditions on P.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.