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

arXiv: https://arxiv.org/abs/1605.06702 · HTML: https://mlsanity.com/paper/1605.06702/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 May 2016.

## Built on by (most cited first, 2 of 2)

- [Computing linear sections of varieties: quantum entanglement, tensor decompositions and beyond](https://mlsanity.com/paper/2212.03851/) (2022)
- [Tensor Denoising via Amplification and Stable Rank Methods](https://mlsanity.com/paper/2301.03761/) (2023)

## Abstract (arXiv)

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 ω=2. In this paper we rule out obtaining ω=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.