# Matrix Multiplication: Verifying Strong Uniquely Solvable Puzzles

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 35 references that are in the map.
- First posted on arXiv 30 Dec 2022.

## Builds on (most cited first, 5 of 5)

- [Powers of Tensors and Fast Matrix Multiplication](https://mlsanity.com/paper/1401.7714/) (2014)
- [Fast Matrix Multiplication: Limitations of the Laser Method](https://mlsanity.com/paper/1411.5414/) (2014)
- [Which groups are amenable to proving exponent two for matrix multiplication?](https://mlsanity.com/paper/1712.02302/) (2017)
- [Further limitations of the known approaches for matrix multiplication](https://mlsanity.com/paper/1712.07246/) (2017)
- [Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication](https://mlsanity.com/paper/1810.08671/) (2018)

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

- [Efficiently-Verifiable Strong Uniquely Solvable Puzzles and Matrix Multiplication](https://mlsanity.com/paper/2307.06463/) (2023)

## Abstract (arXiv)

Cohn and Umans proposed a framework for developing fast matrix multiplication algorithms based on the embedding computation in certain groups algebras. In subsequent work with Kleinberg and Szegedy, they connected this to the search for combinatorial objects called strong uniquely solvable puzzles (strong USPs). We begin a systematic computer-aided search for these objects. We develop and implement constraint-based algorithms build on reductions to SAT and IP to verify that puzzles are strong USPs, and to search for large strong USPs. We produce tight bounds on the maximum size of a strong USP for width k ≤ 5, construct puzzles of small width that are larger than previous work, and improve the upper bounds on strong USP size for k ≤ 12. Although our work only deals with puzzles of small-constant width, the strong USPs we find imply matrix multiplication algorithms that run in O(nω) time with exponent ω ≤ 2.66. While our algorithms do not beat the fastest algorithms, our work provides evidence and, perhaps, a path to finding families of strong USPs that imply matrix multiplication algorithms that are more efficient than those currently known.