2018/10/19 by Josh Alman, Virginia Vassilevska Williams, Alman, Josh +1
Computer Science · Mathematics · #Coding theory and cryptography #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Quantum Computing Algorithms and Architecture #Tensor decomposition and applications
paper · pdf · doi:10.48550/arxiv.1810.08671
openalex publication_date 2018/10/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the known techniques for designing Matrix Multiplication algorithms.\nThe two main approaches are the Laser method of Strassen, and the Group\ntheoretic approach of Cohn and Umans. We define a generalization based on\nzeroing outs which subsumes these two approaches, which we call the Solar\nmethod, and an even more general method based on monomial degenerations, which\nwe call the Galactic method.\n We then design a suite of techniques for proving lower bounds on the value of\n\ω, the exponent of matrix multiplication, which can be achieved by\nalgorithms using many tensors T and the Galactic method. Some of our\ntechniques exploit `local' properties of T, like finding a sub-tensor of T\nwhich is so `weak' that T itself couldn't be used to achieve a good bound on\n\ω, while others exploit `global' properties, like T being a monomial\ndegeneration of the structural tensor of a group algebra.\n Our main result is that there is a universal constant \ℓ>2 such that a\nlarge class of tensors generalizing the Coppersmith-Winograd tensor CWq\ncannot be used within the Galactic method to show a bound on \ω better\nthan \ℓ, for any q. We give evidence that previous lower-bounding\ntechniques were not strong enough to show this. We also prove a number of\ncomplementary results along the way, including that for any group G, the\nstructural tensor of \ℂ[G] can be used to recover the best bound on\n\ω which the Coppersmith-Winograd approach gets using CW|G|-2 as\nlong as the asymptotic rank of the structural tensor is not too large.\n