Theory of Computing
-------------------
Title : Barriers for Fast Matrix Multiplication from Irreversibility
Authors : Matthias Christandl, Peter Vrana, and Jeroen Zuiddam
Volume : 17
Number : 2
Pages : 1-32
URL : http://www.theoryofcomputing.org/articles/v017a002
Abstract
--------
Determining the asymptotic algebraic complexity of matrix
multiplication, succinctly represented by the matrix multiplication
exponent $\omega$, is a central problem in algebraic complexity
theory. The best upper bounds on $\omega$, leading to the state-of-
the-art $\omega \leq 2.37..$, have been obtained via Strassen's laser
method and its generalization by Coppersmith and Winograd. Recent
barrier results show limitations for these and related approaches to
improve the upper bound on $\omega$. We introduce a new and more
general barrier, providing stronger limitations than in previous work.
Concretely, we introduce the notion of irreversibility of a tensor,
and we prove (in some precise sense) that any approach that uses an
irreversible tensor in an intermediate step (e.g., as a starting tensor
in the laser method) cannot give $\omega = 2$. In quantitative terms,
we prove that the best upper bound achievable is at least twice the
irreversibility of the intermediate tensor. The quantum functionals
and Strassen support functionals give (so far, the best) lower bounds
on irreversibility. We provide lower bounds on the irreversibility of
key intermediate tensors, including the small and big Coppersmith--
Winograd tensors, that improve limitations shown in previous work.
Finally, we discuss barriers on the group-theoretic approach in terms
of monomial irreversibility.
----------------
A conference version of this paper appeared in the Proceedings
of the 34th Computational Complexity Conference, 2019.