2023/07/12 by Matthew J. Anderson, Anderson, Matthew, Vu Tuan Hieu Le +1
Computer Science · #Artificial Intelligence (cs.AI) #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #F.2.1 #FOS: Computer and information sciences #G.4 #I.2.8 #I.3.2 #Parallel Computing and Optimization Techniques #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2307.06463
openalex publication_date 2023/07/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.