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

DOI10.19086/da.1245zbMath1405.65058arXiv1605.06702OpenAlexW2407637222WikidataQ60468501 ScholiaQ60468501MaRDI QIDQ4645008

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)

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

Mathematics Subject Classification ID

Related Items (50)

UPPER BOUNDS FOR SUNFLOWER-FREE SETS ⋮ Popular progression differences in vector spaces II ⋮ The analytic rank of tensors and its applications ⋮ Removal lemmas and approximate homomorphisms ⋮ Universal points in the asymptotic spectrum of tensors ⋮ On the strength of general polynomials ⋮ Bounds for matchings in nonabelian groups ⋮ Bounds on the size of progression-free sets in \(\mathbb{Z}_m^n\) ⋮ New applications of the polynomial method: The cap set conjecture and beyond ⋮ Sets Avoiding Six-Term Arithmetic Progressions in $\mathbb{Z}_6^{n}$ are Exponentially Small ⋮ Alternating minimization, scaling algorithms, and the null-cone problem from invariant theory ⋮ The \(G\)-stable rank for tensors and the cap set problem ⋮ A polynomial bound for the arithmetic \(k\)-cycle removal lemma in vector spaces ⋮ 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\) ⋮ A tight bound for Green's arithmetic triangle removal lemma in vector spaces ⋮ Improved bounds for progression-free sets in \(C_8^n\) ⋮ Algebraic geometry and representation theory in the study of matrix multiplication complexity and other problems in theoretical computer science ⋮ 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 ⋮ On the size of subsets of \(\mathbb{F}_q^n\) avoiding solutions to linear systems with repeated columns ⋮ Strength conditions, small subalgebras, and Stillman bounds in degree ≤4 ⋮ Weighted slice rank and a minimax correspondence to Strassen's spectra ⋮ Fast matrix multiplication and its algebraic neighbourhood ⋮ Unnamed Item ⋮ Monochromatic equilateral triangles in the unit distance graph ⋮ Further Limitations of the Known Approaches for Matrix Multiplication ⋮ Towards a geometric approach to Strassen's asymptotic rank conjecture ⋮ Sumsets as unions of sumsets of subsets ⋮ Proof of a conjecture of Kleinberg-Sawin-Speyer ⋮ 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 ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A DISTRIBUTION ON TRIPLES WITH MAXIMUM ENTROPY MARGINAL ⋮ On the size of subsets of \(\mathbb{F}_p^n\) without \(p\) distinct elements summing to zero ⋮ Limits on the Universal method for matrix multiplication ⋮ Barriers for fast matrix multiplication from irreversibility ⋮ The asymptotic induced matching number of hypergraphs: balanced binary strings ⋮ Tensor slice rank and Cayley's first hyperdeterminant ⋮ Unnamed Item ⋮ Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication ⋮ Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication

Cites Work

• Unnamed Item
• On sunflowers and matrix multiplication
• 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
• Matrix multiplication via arithmetic progressions
• Typical tensorial rank
• Stability of projective varieties
• Combinatorial properties of systems of sets
• Approximate formulas for some functions of prime numbers
• Improved bound for complexity of matrix multiplication
• Powers of tensors and fast matrix multiplication
• Partial and Total Matrix Multiplication
• On the Asymptotic Complexity of Matrix Multiplication
• Proof of a conjecture of Kleinberg-Sawin-Speyer
• Probability Inequalities for Sums of Bounded Random Variables
• Multiplying matrices faster than coppersmith-winograd
• Geometric complexity theory and tensor rank
• Fast matrix multiplication using coherent configurations

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