Limits on the Universal Method for Matrix Multiplication
share
In a recent work, Alman and Vassilevska Williams [FOCS 2018, arXiv:1810.08671 [cs.CC]] proved limitations on designing matrix multiplication algorithms using the Galactic method applied to many tensors of interest, including the family of Coppersmith-Winograd tensors. In this note, we extend all their lower bounds to the more powerful Universal method, which can use any degeneration of a tensor instead of just monomial degenerations. Our main result is that the Universal method applied to any Coppersmith-Winograd tensor cannot yield a bound on ω better than 2.16805. We also study a slightly restricted form of Strassen's Laser method and prove that it is optimal: when it applies to a tensor T, it achieves ω=2 if and only if it is possible for the Universal method applied to T to achieve ω=2.
READ FULL TEXT