On cap sets and the group-theoretic approach to matrix multiplication
From MaRDI portal
Publication:4645008
Abstract: In 2003, Cohn and Umans described a framework for proving upper bounds on the exponent 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 . In this paper we rule out obtaining 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
- scientific article; zbMATH DE number 976329 (Why is no real title available?)
- 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
- 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
(57)- On the strength of general polynomials
- A distribution on triples with maximum entropy marginal
- Exponentially larger affine and projective caps
- scientific article; zbMATH DE number 7559388 (Why is no real title available?)
- 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\)
- Strength conditions, small subalgebras, and Stillman bounds in degree \(\leq 4\)
- Irreversibility of structure tensors of modules
- Further limitations of the known approaches for matrix multiplication
- Subrank and optimal reduction of scalar multiplications to generic tensors
- scientific article; zbMATH DE number 7564426 (Why is no real title available?)
- scientific article; zbMATH DE number 7561763 (Why is no real title available?)
- 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
- Notions of tensor rank
- A note on the triple product property for subsets of finite groups.
- A refined laser method and faster matrix multiplication
- On the size of subsets of \(\mathbb{F}_p^n\) without \(p\) distinct elements summing to zero
- Sets avoiding six-term arithmetic progressions in \(\mathbb{Z}_6^n\) are exponentially small
- 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
- The G-stable rank for tensors and the cap set problem
- Limits on the Universal method for matrix multiplication
- 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
- Limits on the universal method for 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
- Weighted slice rank and a minimax correspondence to Strassen's spectra
- Finding solutions with distinct variables to systems of linear equations over \(\mathbb{F}_p\)
- Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication
- scientific article; zbMATH DE number 7731180 (Why is no real title available?)
- Bounds for matchings in nonabelian groups
- A polynomial bound for the arithmetic k-cycle removal lemma in vector spaces
- New applications of the polynomial method: the cap set conjecture and beyond
- Stability of the Levi-Civita tensors and an Alon-Tarsi type theorem
- Sumsets as unions of sumsets of subsets
- Tensor slice rank and Cayley's first hyperdeterminant
- Popular progression differences in vector spaces II
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)
