Efficiently-Verifiable Strong Uniquely Solvable Puzzles and Matrix Multiplication

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 bounds on the matrix multiplication exponent \(\omega \) that infinite families of SUSPs can. We construct, by computer search, larger SUSPs than known for small width. This, combined with our tighter analysis, strengthens the upper bound on \(\omega \) from 2.66 to 2.505 obtainable via this computational approach, nearing the handcrafted constructions of Cohn-Umans.