Efficiently-Verifiable Strong Uniquely Solvable Puzzles and Matrix Multiplication
This work addresses a fundamental problem in computational complexity and algorithm design, offering incremental improvements in matrix multiplication efficiency.
The paper tackles the problem of developing fast matrix multiplication algorithms by introducing simplifiable strong uniquely solvable puzzles (SUSPs), which are efficiently verifiable and can achieve strong bounds on the matrix multiplication exponent. It reports a computational search that strengthens the upper bound on the exponent from 2.66 to 2.505.
We advance the Cohn-Umans framework for developing fast matrix multiplication algorithms. We introduce, analyze, and search for a new subclass of strong uniquely solvable puzzles (SUSP), which we call simplifiable SUSPs. We show that these puzzles are efficiently verifiable, which remains an open question for general SUSPs. We also show that individual simplifiable SUSPs can achieve the same strength of bounds on the matrix multiplication exponent $ω$ that infinite families of SUSPs can. We report on the construction, by computer search, of larger SUSPs than previously known for small width. This, combined with our tighter analysis, strengthens the upper bound on the matrix multiplication exponent from $2.66$ to $2.505$ obtainable via this computational approach, and nears the results of the handcrafted constructions of Cohn et al.