On generalized corners and matrix multiplication

09/07/2023
by   Kevin Pratt, et al.
0

Suppose that S ⊆ [n]^2 contains no three points of the form (x,y), (x,y+δ), (x+δ,y'), where δ≠ 0. How big can S be? Trivially, n ≤ |S| ≤ n^2. Slight improvements on these bounds are obtained from Shkredov's upper bound for the corners problem [Shk06], which shows that |S| ≤ O(n^2/(loglog n)^c) for some small c > 0, and a construction due to Petrov [Pet23], which shows that |S| ≥Ω(n log n/√(loglog n)). Could it be that for all ε > 0, |S| ≤ O(n^1+ε)? We show that if so, this would rule out obtaining ω = 2 using a large family of abelian groups in the group-theoretic framework of Cohn, Kleinberg, Szegedy and Umans [CU03,CKSU05] (which is known to capture the best bounds on ω to date), for which no barriers are currently known. Furthermore, an upper bound of O(n^4/3 - ε) for any fixed ε > 0 would rule out a conjectured approach to obtain ω = 2 of [CKSU05]. Along the way, we encounter several problems that have much stronger constraints and that would already have these implications.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset