On cap sets and the group-theoretic approach to matrix multiplication

DOI10.19086/DA.1245zbMATH Open1405.65058arXiv1605.06702OpenAlexW2407637222WikidataQ60468501 ScholiaQ60468501MaRDI QIDQ4645008FDOQ4645008

Henry Cohn, Eric Naslund, Joshua A. Grochow, Chris Umans, Thomas Church, Jonah Blasiak, William F. Sawin

Publication date: 9 January 2019

Published in: Discrete Analysis (Search for Journal in Brave)

Abstract: In 2003, Cohn and Umans described a framework for proving upper bounds on the exponent $omega$ of matrix multiplication by reducing matrix multiplication to group algebra multiplication, and in 2005 Cohn, Kleinberg, Szegedy, and Umans proposed specific conjectures for how to obtain $omega=2$. In this paper we rule out obtaining $omega=2$ in this framework from abelian groups of bounded exponent. To do this we bound the size of tricolored sum-free sets in such groups, extending the breakthrough results of Croot, Lev, Pach, Ellenberg, and Gijswijt on cap sets. As a byproduct of our proof, we show that a variant of tensor rank due to Tao gives a quantitative understanding of the notion of unstable tensor from geometric invariant theory.

Full work available at URL: https://arxiv.org/abs/1605.06702

Mathematics Subject Classification ID

Complexity and performance of numerical algorithms (65Y20) Torsion groups, primary groups and generalized primary groups (20K10) Extremal set theory (05D05) Arithmetic combinatorics; higher degree uniformity (11B30)

Cites Work

• Title not available (Why is that?)
• Powers of tensors and fast matrix multiplication
• Probability Inequalities for Sums of Bounded Random Variables
• Improved bound for complexity of matrix multiplication
• Partial and Total Matrix Multiplication
• Multiplying matrices faster than coppersmith-winograd
• Matrix multiplication via arithmetic progressions
• Stability of projective varieties
• Approximate formulas for some functions of prime numbers
• Geometric complexity theory and tensor rank
• On the Asymptotic Complexity of Matrix Multiplication
• Combinatorial properties of systems of sets
• On sunflowers and matrix multiplication
• Typical tensorial rank
• Proof of a conjecture of Kleinberg-Sawin-Speyer
• Progression-free sets in \(\mathbb{Z}_4^n\) are exponentially small
• On large subsets of \(\mathbb{F}_q^n\) with no three-term arithmetic progression
• Fast matrix multiplication using coherent configurations

Cited In (53)

• Exponentially larger affine and projective caps
• Title not available (Why is that?)
• Erdős-Ginzburg-Ziv constants by avoiding three-term arithmetic progressions
• Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication
• Improved estimates for polynomial Roth type theorems in finite fields
• Exponential bounds for the Erdős-Ginzburg-Ziv constant
• Caps and progression-free sets in \(\mathbb{Z}_m^n\)
• A gap in the slice rank of \(k\)-tensors
• Alternating minimization, scaling algorithms, and the null-cone problem from invariant theory
• Fast matrix multiplication and its algebraic neighbourhood
• The partition rank of a tensor and \(k\)-right corners in \(\mathbb{F}_q^n\)
• Bounds on the size of progression-free sets in \(\mathbb{Z}_m^n\)
• Improved bounds for progression-free sets in \(C_8^n\)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Barriers for fast matrix multiplication from irreversibility
• UPPER BOUNDS FOR SUNFLOWER-FREE SETS
• Universal points in the asymptotic spectrum of tensors
• Maximum subsets of \(\mathbb{F}^n_q\) containing no right angles
• On the size of subsets of \(\mathbb{F}_p^n\) without \(p\) distinct elements summing to zero
• New applications of the polynomial method: The cap set conjecture and beyond
• Monochromatic equilateral triangles in the unit distance graph
• A Gap in the Subrank of Tensors
• Removal lemmas and approximate homomorphisms
• Proof of a conjecture of Kleinberg-Sawin-Speyer
• On the size of subsets of \(\mathbb{F}_q^n\) avoiding solutions to linear systems with repeated columns
• Limits on the Universal method for matrix multiplication
• The \(G\)-stable rank for tensors and the cap set problem
• A DISTRIBUTION ON TRIPLES WITH MAXIMUM ENTROPY MARGINAL
• A tight bound for Green's arithmetic triangle removal lemma in vector spaces
• On the Bhattacharya-Mesner rank of third order hypermatrices
• Algebraic geometry and representation theory in the study of matrix multiplication complexity and other problems in theoretical computer science
• The analytic rank of tensors and its applications
• Towards a geometric approach to Strassen's asymptotic rank conjecture
• The asymptotic induced matching number of hypergraphs: balanced binary strings
• Finding solutions with distinct variables to systems of linear equations over \(\mathbb{F}_p\)
• Further Limitations of the Known Approaches for Matrix Multiplication
• Weighted slice rank and a minimax correspondence to Strassen's spectra
• Strength conditions, small subalgebras, and Stillman bounds in degree ≤4
• Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication
• Title not available (Why is that?)
• Bounds for matchings in nonabelian groups
• A polynomial bound for the arithmetic \(k\)-cycle removal lemma in vector spaces
• Stability of the Levi-Civita tensors and an Alon-Tarsi type theorem
• Sumsets as unions of sumsets of subsets
• Popular progression differences in vector spaces II
• Tensor slice rank and Cayley's first hyperdeterminant
• On the strength of general polynomials
• Sets Avoiding Six-Term Arithmetic Progressions in $\mathbb{Z}_6^{n}$ are Exponentially Small
• Subrank and optimal reduction of scalar multiplications to generic tensors
• Notions of tensor rank
• A refined laser method and faster matrix multiplication

This page was built for publication: On cap sets and the group-theoretic approach to matrix multiplication

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4645008)