2026-07-26T19:54:01Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19617 2024-03-06T11:04:29Z ddc:004 open_access

On Generalized Corners and Matrix Multiplication Pratt, Kevin Algebraic computation fast matrix multiplication additive combinatorics Suppose that S ⊆ [n]² contains no three points of the form (x,y), (x,y+δ), (x+δ,y'), where δ ≠ 0. How big can S be? Trivially, n ≤ |S| ≤ n². Slight improvements on these bounds are obtained from Shkredov’s upper bound for the corners problem [Shkredov, 2006], which shows that |S| ≤ O(n²/(log log n)^c) for some small c > 0, and a construction due to Petrov [Fedor Petrov, 2023], which shows that |S| ≥ Ω(n log n/√{log log 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 and Umans, 2003; Cohn et al., 2005] (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 [Cohn et al., 2005]. Along the way, we encounter several problems that have much stronger constraints and that would already have these implications. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Kevin Pratt 2024 Is Part Of LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2024.89 urn:nbn:de:0030-drops-196174 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.89 eng https://creativecommons.org/licenses/by/4.0/legalcode