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

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

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

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

Recommendations

• Fast matrix multiplication using coherent configurations
• scientific article; zbMATH DE number 6412845
• Further limitations of the known approaches for matrix multiplication
• Limits on all known (and some unknown) approaches to matrix multiplication
• Search and test algorithms for triple product property triples.

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

• 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
• Title not available (Why is that?)
• 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 (57)

• Irreversibility of structure tensors of modules
• Subrank and optimal reduction of scalar multiplications to generic tensors
• Notions of tensor rank
• A refined laser method and faster matrix multiplication
• On the size of subsets of \(\mathbb{F}_q^n\) avoiding solutions to linear systems with repeated columns
• Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication
• 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\)
• Strength conditions, small subalgebras, and Stillman bounds in degree \(\leq 4\)
• Improved bounds for progression-free sets in \(C_8^n\)
• Further limitations of the known approaches for matrix multiplication
• 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
• A note on the triple product property for subsets of finite groups.
• Sets avoiding six-term arithmetic progressions in \(\mathbb{Z}_6^n\) are exponentially small
• On the size of subsets of \(\mathbb{F}_p^n\) without \(p\) distinct elements summing to zero
• 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
• Limits on the Universal method for matrix multiplication
• The \(G\)-stable rank for tensors and the cap set problem
• Upgrading subgroup triple-product-property triples
• 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
• On sunflowers and matrix multiplication
• 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\)
• Weighted slice rank and a minimax correspondence to Strassen's spectra
• Title not available (Why is that?)
• Bounds for matchings in nonabelian groups
• New applications of the polynomial method: the cap set conjecture and beyond
• 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
• A distribution on triples with maximum entropy marginal

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)