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

DOI10.19086/DA.1245MaRDI QIDQ4645008zbMATH OpenOpenAlexWikidataFDO

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)

Copyright license Creative Commons Attribution 4.0 International

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

Mathematics Subject Classification ID

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

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.

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.

Cites work

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

Cited in

(69)

• Bounds for matchings in nonabelian groups
• A polynomial bound for the arithmetic k-cycle removal lemma in vector spaces
• A tight bound for Green's arithmetic triangle removal lemma in vector spaces
• Erdős-Ginzburg-Ziv constants by avoiding three-term arithmetic progressions
• Improved estimates for polynomial Roth type theorems in finite fields
• Caps and progression-free sets in \(\mathbb{Z}_m^n\)
• A gap in the slice rank of \(k\)-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
• Tensor slice rank and Cayley's first hyperdeterminant
• Bounds on the size of progression-free sets in \(\mathbb{Z}_m^n\)
• The G-stable rank for tensors and the cap set problem
• On the Bhattacharya-Mesner rank of third order hypermatrices
• Exponential bounds for the Erdős-Ginzburg-Ziv constant
• The partition rank of a tensor and \(k\)-right corners in \(\mathbb{F}_q^n\)
• Improved bounds for progression-free sets in C₈^n
• Towards a geometric approach to Strassen's asymptotic rank conjecture
• Algebraic geometry and representation theory in the study of matrix multiplication complexity and other problems in theoretical computer science
• Weighted slice rank and a minimax correspondence to Strassen's spectra
• Upgrading subgroup triple-product-property triples
• A note on the triple product property for subsets of finite groups.
• On sunflowers and matrix multiplication
• New applications of the polynomial method: the cap set conjecture and beyond
• Fast matrix multiplication and its algebraic neighbourhood
• Sumsets as unions of sumsets of subsets
• Proof of a conjecture of Kleinberg-Sawin-Speyer
• Alternating minimization, scaling algorithms, and the null-cone problem from invariant theory
• Further limitations of the known approaches for matrix multiplication
• Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication
• Universal points in the asymptotic spectrum of tensors
• Sets avoiding six-term arithmetic progressions in \(\mathbb{Z}_6^n\) are exponentially small
• Slice rank of block tensors and irreversibility of structure tensors of algebras
• Limits on the Universal method for matrix multiplication
• Barriers for fast matrix multiplication from irreversibility
• scientific article; zbMATH DE number 7561763 (Why is no real title available?)
• Strength conditions, small subalgebras, and Stillman bounds in degree 4
• Monochromatic equilateral triangles in the unit distance graph
• Limits on the universal method for matrix multiplication
• Barriers for fast matrix multiplication from irreversibility
• A distribution on triples with maximum entropy marginal
• The analytic rank of tensors and its applications
• Popular progression differences in vector spaces II
• UPPER BOUNDS FOR SUNFLOWER-FREE SETS
• Removal lemmas and approximate homomorphisms
• On the strength of general polynomials
• Finding solutions with distinct variables to systems of linear equations over \(\mathbb{F}_p\)
• A Gap in the Subrank of Tensors
• Exponentially larger affine and projective caps
• Stability of the Levi-Civita tensors and an Alon-Tarsi type theorem
• scientific article; zbMATH DE number 7731180 (Why is no real title available?)
• Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication
• Irreversibility of structure tensors of modules
• On the size of subsets of \(\mathbb{F}_q^n\) avoiding solutions to linear systems with repeated columns
• Subrank and optimal reduction of scalar multiplications to generic tensors
• Notions of tensor rank
• A refined laser method and faster matrix multiplication
• On generalized corners and matrix multiplication
• Discreteness of asymptotic tensor ranks (extended abstract)
• Tensor ranks and the fine-grained complexity of dynamic programming
• On matrix multiplication and polynomial identity testing
• Greedy capsets
• Partition rank and partition lattices
• Combinatorial optimization. Abstracts from the workshop held November 10--15, 2024
• Generalized polynomials and hyperplane functions in \((\mathbb{Z} / p^k \mathbb{Z})^n\)
• Barriers for rectangular matrix multiplication
• Asymptotic spectra: theory, applications, and extensions
• The symmetric geometric rank of symmetric tensors
• Algebraic capsets
• The asymptotic induced matching number of hypergraphs: balanced binary strings

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)