Authors Matthias Christandl, P\'eter Vrana, Jeroen Zuiddam,
License CC-BY-3.0
T HEORY OF C OMPUTING, Volume 17 (2), 2021, pp. 1–32
www.theoryofcomputing.org
S PECIAL ISSUE : CCC 2019
Barriers for Fast Matrix Multiplication
from Irreversibility
Matthias Christandl∗ Péter Vrana† Jeroen Zuiddam‡
Received July 5, 2019; Revised October 5, 2020; Published September 16, 2021
Abstract. Determining the asymptotic algebraic complexity of matrix multiplication,
succinctly represented by the matrix multiplication exponent ω, is a central problem in
algebraic complexity theory. The best upper bounds on ω, leading to the state-of-the-
art ω ≤ 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 ω.
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 ω = 2. In quantitative terms,
A conference version of this paper appeared in the Proceedings of the 34th Computational Complexity Conference,
2019 [14].
∗ Supported by European Research Council (ERC Grant Agreement No. 337603 and 81876) and VILLUM FONDEN via the
QMATH Centre of Excellence (Grant No. 10059).
† Supported by National Research, Development and Innovation Fund of Hungary within the Quantum Technology National
Excellence Program (Project Nr. 2017-1.2.1-NKP-2017-00001) and via the research grants K124152, KH129601.
‡ Supported by National Science Foundation Grant No. DMS-1638352 and indirectly supported by the National Science
Foundation Grant No. CCF-1900460.
ACM Classification: F.2.1
AMS Classification: 68Q17, 68Q25
Key words and phrases: algebraic complexity, matrix multiplication, barriers, tensors, tensor rank
© 2021 Matthias Christandl, Péter Vrana, and Jeroen Zuiddam
c b Licensed under a Creative Commons Attribution License (CC-BY) DOI: 10.4086/toc.2021.v017a002
M ATTHIAS C HRISTANDL , P ÉTER V RANA , AND J EROEN Z UIDDAM
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.
1 Introduction
Determining the asymptotic algebraic complexity of matrix multiplication is a central open problem
in algebraic complexity theory. Several methods for constructing fast matrix multiplication algorithms
have been developed, but at a high level they typically consist of two parts: an efficient reduction of
matrix multiplication to an intermediate problem (some bilinear map, i. e., some 3-tensor) and an efficient
algorithm for the intermediate problem. Recent results have shown barriers for such constructions to
yield fast matrix multiplication algorithms [4, 8, 9, 2, 3]. We give a barrier, based on a new notion called
irreversibility, that is more general and in some cases stronger than the barriers from previous work.
1.1 Matrix multiplication barriers
The matrix multiplication exponent ω is defined as the infimum over all real numbers β such that any two
n × n matrices can be multiplied with O(nβ ) algebraic operations, and thus ω represents the asymptotic
algebraic complexity of matrix multiplication. The bounds 2 ≤ ω ≤ 3 hold trivially. Strassen published
the first non-trivial upper bound ω ≤ log2 7 in 1969 [28]. In the decades that followed, through the
development of several ingenious methods by various people, the upper bound was improved to the
state-of-the-art bound ω ≤ 2.37.., and the pursuit to prove whether ω = 2 or ω > 2 has been ongoing
[17, 27, 35, 23, 15, 16]. As mentioned before, these upper bound methods typically consist of a reduction
of matrix multiplication to an intermediate problem and an efficient algorithm for the intermediate
problem.
Ambainis, Filmus and Le Gall [4], for the first time, proved a barrier result for some collection of
such methods. Namely, they showed that a variety of methods that go via the big Coppersmith–Winograd
tensor as an intermediate problem cannot give ω = 2, and in fact not even ω ≤ 2.30... We call any
lower bound for all upper bounds on ω that can be obtained by some method, a barrier for that method.
In general, barriers in the sense of limitations to proof methods have a long history in computational
complexity theory and recognizing barriers is a natural step towards finding proof methods that do solve
the problem at hand.
Next, Alman and Williams [2, 3] extended the realm of barriers beyond the scope of the Ambainis et
al. barrier, to a larger collection of methods. Also Blasiak, Church, Cohn, Grochow, Naslund, Sawin, and
Umans [8] and Blasiak, Church, Cohn, Grochow, and Umans [9] studied barriers, namely barriers for a
subset of the group-theoretic method. Both the Blasiak et al. and the Alman and Williams barriers rely on
studying versions of asymptotic subrank of an intermediate problem.
We give a barrier that applies more generally than all previous barriers and that is in some cases
stronger. Our barrier also relies on studying versions of asymptotic subrank, which together with the
T HEORY OF C OMPUTING, Volume 17 (2), 2021, pp. 1–32 2
BARRIERS FOR FAST M ATRIX M ULTIPLICATION FROM I RREVERSIBILITY
notion of asymptotic rank we combine into a single parameter called irreversibility. Our barrier simplifies
and generalizes previous barriers and tightly connects the barrier literature to central notions from the
framework of Strassen [29, 30, 31, 12]. Alman [1] reported very similar independent results shortly after
our manuscript appeared on the arXiv, which we jointly presented at the Computational Complexity
Conference 2019 in New Brunswick. For all the tensors mentioned, the barriers of Alman are identical to
ours. A subtle difference between the two papers is that Alman considers asymptotic slice rank instead of
asymptotic subrank.
1.2 Our barrier: informal explanation
Our barrier relies on two ideas: (i) we think of computational problems as resources that can be reduced
to one another and (ii) such reductions satisfy a triangle inequality which limits the possible chains of
reductions. An informal explanation of our barrier is as follows. The matrix multiplication exponent ω
is the optimal rate at which the problem of multiplying matrices can be reduced to the problem of
multiplying numbers, or in other words, the optimal rate at which the problem of multiplying numbers
can be transformed into the problem of multiplying matrices,
ω
multiplying numbers −→ multiplying matrices. (1.1)
By this we mean that for any n the problem of multiplying n × n matrices can be reduced to the problem
of multiplying nω+o(1) pairs of numbers (and some additions, but they do not have an influence on the
complexity). We will make these notions precise later. For now, we stick to the high-level picture. Rates
of transformation naturally satisfy a triangle inequality. Therefore, upper bounds on ω can be obtained by
combining the rate of transformation α1 from the problem of multiplying numbers to some intermediate
problem and the rate of transformation α2 from the intermediate problem to the problem of multiplying
matrices; this is the two-component approach alluded to earlier,
1 α 2 α
multiplying numbers −→ intermediate problem −→ multiplying matrices. (1.2)
That is, α1 α2 ≥ ω. We define the irreversibility of the intermediate tensor, roughly speaking, as the
optimal rate of transformation from the problem of multiplying numbers to the intermediate problem and
back to the problem of multiplying numbers. Strassen [30] (see Section 2.1) showed that the transformation
rate from the matrix multiplication problem to the problem of multiplying numbers is 12 , so we can extend
the chain in (1.2) to
1 α 2 α
multiplying numbers −→ intermediate problem −→ multiplying matrices
1/2
−−→ multiplying numbers. (1.3)
Using the triangle inequality again we see that α1 α2 /2 is at least the irreversibility of the intermediate
problem, and hence the irreversibility of the intermediate problem provides limitations on the upper
bounds α1 α2 ≥ ω that can be obtained from (1.2). This is formalized in Theorem 3.1.
T HEORY OF C OMPUTING, Volume 17 (2), 2021, pp. 1–32 3
M ATTHIAS C HRISTANDL , P ÉTER V RANA , AND J EROEN Z UIDDAM
1.3 Explicit numerical barriers
To exemplify our barrier we show that the support functionals [31] and quantum functionals [12] give
(so far, the best) lower bounds on the irreversibility of the following families of intermediate problems.
These intermediate problems are encoded as tensors. A tensor is a 3-dimensional array of numbers. We
use ei, j,k to denote the tensor that is zero everywhere except for a one in coordinate (i, j, k). We will
discuss tensors in more details later. The families of intermediate tensors we consider are:
• the small Coppersmith–Winograd tensors
q
cwq = ∑ e0,i,i + ei,0,i + ei,i,0 ,
i=1
• the big Coppersmith–Winograd tensors
q
CWq = e0,0,q+1 + e0,q+1,0 + eq+1,0,0 + ∑ e0,i,i + ei,0,i + ei,i,0 ,
i=1
• the reduced polynomial multiplication tensors
n−1
tn = ∑ ei, j,k .
i, j,k=0:
i+ j=k
Our irreversibility lower bounds lead to the following explicit barriers (Section 5.1 and Section 5.2),
rounded to five decimal places.
q cwq -barrier q CWq -barrier n tn -barrier
2 2 1 2.16805 2 2.17795
3 2.02538 2 2.17795 3 2.16805
4 2.06244 3 2.19146 4 2.15949
5 2.09627 4 2.20551 5 2.15237
6 2.12549 5 2.21913 6 2.14641
7 2.15064 6 2.23201 7 2.14135
In Appendix A we provide code to compute the values in these tables to arbitrary precision and for
arbitrary parameters q and n. As suggested by the values in the above tables, both the cwq -barrier and
CWq -barrier increase when q grows, and converge to 3 when q goes to infinity. The tn -barrier, on the
other hand, decreases when n grows, and converges to 2 when n goes to infinity. Families of tensors for
which the barrier converges to 2 in the limit, like tn , may be crucial in proving that ω = 2.
We stress that our method can be applied to any tensor, not only the ones above. The tensors
listed above play a special role in the literature and that is why we single them out. The small and big
Coppersmith–Winograd tensors come from the paper [17]. They first analyze cw5 to get an upper bound
on ω, and then improve it by analyzing CW6 and its Kronecker square. All papers from then on (Stothers,
Vassilevska–Williams, Le Gall) use powers of CW5 to get upper bounds on ω. The reduced polynomial
multiplication tensors tn give an example of a family of tensors for which the irreducibility goes to 1
when n goes to infinity and hence the barrier becomes trivial in the limit.
T HEORY OF C OMPUTING, Volume 17 (2), 2021, pp. 1–32 4
BARRIERS FOR FAST M ATRIX M ULTIPLICATION FROM I RREVERSIBILITY
1.4 Comparison and other applications
Compared to [4], whose barriers apply to the laser method, our barriers are valid for a larger class of
approaches (and naturally we obtain lower barriers). Compared to [3], whose barriers apply to what we
call monomial degeneration, our barriers are valid for a larger class of approaches but our barriers are
also higher. As a variation on our barrier we introduce a monomial version. Compared to [8] and [9]
our monomial barriers are valid for a class of approaches that includes their simultaneous triple product
property (STPP) approach, and thus we provide a uniform view on the barriers that have appeared in the
literature. We have not tried to optimize the barriers that we obtain, but focus instead on introducing the
barrier itself. The barrier in [1] is very similar to ours, except for using asymptotic slice rank instead of
asymptotic subrank.
It will become clear to the reader during the development of our ideas that they not only apply to
the problem of fast matrix multiplication, but extend to give barriers for the more general problem of
constructing fast rectangular matrix multiplication algorithms (see the follow-up results on barriers for
rectangular matrix multiplication in [11]) or even transformations between arbitrary powers of tensors.
Such transformations may represent, for example, asymptotic SLOCC (stochastic local operations and
classical communication) reductions among multipartite quantum states [6, 18, 36, 20].
We define irreversibility in Section 2. In Section 3 we discuss how irreversibility implies a barrier.
In Section 4 we discuss methods to analyze irreversibility. Finally, in Section 5 we exhibit explicit
irreversibility barriers.
2 Irreversibility of tensors
We begin by introducing some standard terminology and results regarding tensors and matrix multipli-
cation. Then we discuss a useful notion called the relative exponent of two tensors and we define the
irreversibility of a tensor. After that we introduce the monomial versions of these ideas. Finally, we
discuss what values the irreducibility can take.
2.1 Tensors and matrix multiplication
We begin with some standard terminology and results regarding tensors and matrix multiplication.
Standard references for this material are [10] and [7]. Let F be a field. Everything we discuss works over
all fields, except when mentioned otherwise. An n1 × n2 × n3 tensor (over F) is a three-dimensional array
t = (ti1 ,i2 ,i3 )i1 ∈[n1 ],i2 ∈[n1 ],i3 ∈[n1 ]
of field elements ti1 ,i2 ,i3 ∈ F. We denote the set of all n1 × n2 × n3 tensors by Fn1 ×n2 ×n3 . The support of t
is defined as the set
supp(t) := {(i1 , i2 , i3 ) ∈ [n1 ] × [n2 ] × [n3 ] : ti1 ,i2 ,i3 6= 0} .
We use ei, j,k to denote the tensor that is zero everywhere except for a one in coordinate (i, j, k). For any
mi × ni matrices Ai over F we define the tensor (A1 , A2 , A3 ) · t ∈ Fm1 ×m2 ×m3 by
((A1 , A2 , A3 ) · t) j1 , j2 , j3 = ∑ (A1 ) j1 ,i1 (A2 ) j2 ,i2 (A3 ) j3 ,i3 ti1 ,i2 ,i3 .
i1 ,i2 ,i3
T HEORY OF C OMPUTING, Volume 17 (2), 2021, pp. 1–32 5
M ATTHIAS C HRISTANDL , P ÉTER V RANA , AND J EROEN Z UIDDAM
For t ∈ Fn1 ×n2 ×n3 and s ∈ Fm1 ×m2 ×m3 we write t ≥ s and say that t restricts to s if there are matrices Ai
such that (A1 , A2 , A3 ) ·t = s. We say t and s are equivalent if t ≥ s and s ≥ t. We say t and s are isomorphic
and write s ∼= t if s = (A1 , A2 , A3 ) · t for invertible matrices Ai . We will often simplify the notation and
simply write s = t when s and t are isomorphic.
For n ∈ N we define the rank-n unit tensor hni := ∑ni=1 ei,i,i ∈ Fn×n×n . A simple tensor is a tensor that
is an outer product ∑i, j,k ui v j wk ei, j,k of three vectors u, v and w. The tensor rank of t is defined as the
smallest r such that t can be written as a sum of r simple tensors, that is,
r
(`) (`) (`)
t = ∑ ∑ ui v j wk ei, j,k (2.1)
`=1 i, j,k
for vectors u(`) , v(`) and w(`) . It is crucial for us, but not hard to see, that we can phrase tensor rank
in terms of the restriction preorder and diagonal tensors via R(t) = min{n ∈ N : t ≤ hni}. Indeed, if
t = (A1 , A2 , A3 ) · hri, then the columns of the matrices A1 , A2 and A3 provide the vectors u(`) , v(`) and w(`)
for a tensor rank upper bound, and in the other direction such vectors u(`) , v(`) and w(`) provide the matrices
A1 , A2 and A3 . What is nice about this definition is that it naturally gives rise to the following tensor
parameter, which is central for our barriers: The subrank of t is defined as Q(t) := max{n ∈ N : hni ≤ t}.
Extending the definition of Kronecker product for matrices, we define the Kronecker product s ⊗ t ∈
F(m1 n2 )×(m2 n2 )×(m3 n3 ) for tensors s ∈ Fm1 ×m2 ×m3 and t ∈ Fn1 ×n2 ×n3 as the tensor that has coefficients given
by all pairwise products of coefficients of s and t. Extending the definition of direct sum for matrices, we
define the direct sum s ⊕ t ∈ F(m1 +n2 )×(m2 +n2 )×(m3 +n3 ) as the tensor obtained by placing s and t as blocks
in a block-diagonal tensor. In long expressions we will often write t n to denote t ⊗n . The product ⊗,
the sum ⊕ and the diagonal tensors hni behave well with respect to each other. One fact we will use
frequently is that the direct sum of n copies of a tensor t is isomorphic to the Kronecker product of the
diagonal tensor hni and t.
For any tensor t ∈ Fn1 ×n2 ×n3 we define linear maps t1 : Fn1 → Fn2 ×n3 : v 7→ ∑i, j,k viti, j,k e j,k , t2 : Fn2 →
×n
F n1 3 : v 7→
∑i, j,k v j ti, j,k ei,k and t3 : Fn3 → Fn1 ×n2 : v 7→ ∑i, j,k vk ti, j,k ei, j . These are called the flattenings
of t. We call each function t 7→ rk(ti ) a flattening rank of t. A basic observation and tool is that each
flattening rank is multiplicative under the Kronecker product on tensors, additive under the direct sum on
tensors, and monotone under the preorder ≤ on tensors.
The asymptotic rank of t is defined as
R(t) := lim R(t ⊗n )1/n = inf R(t ⊗n )1/n (2.2)
e n→∞ n
and the asymptotic subrank of t is defined as
Q(t) := lim Q(t ⊗n )1/n = sup Q(t ⊗n )1/n . (2.3)
n→∞ n
e
We need to argue that the limits in the definitions exist. If t ≤ hni and s ≤ hmi, then we also have
t ⊗ s ≤ hnmi. It follows from this that tensor rank is submultiplicative under ⊗. Similarly, subrank
is super-multiplicative under ⊗. Therefore, by Fekete’s lemma,1 the above limits exist and equal
1 Fekete’s lemma is as follows. Let r , r , r , . . . ∈ R
1 2 3 ≥0 satisfy rn+m ≤ rn + rm for all n, m. Then it holds that limn→∞ rn /n =
infn rn /n. See, e. g., [24, No. 98].
T HEORY OF C OMPUTING, Volume 17 (2), 2021, pp. 1–32 6
BARRIERS FOR FAST M ATRIX M ULTIPLICATION FROM I RREVERSIBILITY
the respective infimum and supremum. We note that asymptotic rank and asymptotic subrank may
equivalently be defined using border rank and border subrank, respectively, which are the approximative
versions of rank and subrank (see, e. g., [7]).
For a, b, c ∈ N≥1 the matrix multiplication tensor ha, b, ci is defined as
a b c
ha, b, ci := ∑ ∑ ∑ e(i, j), ( j,k), (k,i) ∈ Fab×bc×ca . (2.4)
i=1 j=1 k=1
To see how hn, n, ni encodes multiplication of n × n matrices, let Ei, j be the n × n matrix that is all-
zero except for a 1 at coordinate (i, j), so that the Ei, j form the standard basis of the vector space of
n × n matrices. Note that Ei, j E j,k = Ei,k and that ∑ni=1 ∑nj=1 ∑nk=1 A(i, j) B( j,k) Ei,k = AB. Thus suitable
contractions of hn, n, ni with the matrices A and B produces the product AB. It is a standard result ([7,
Section 4]) that the tensor rank of hn, n, ni equals, up to a constant factor, the arithmetic complexity of
multiplying two n × n matrices. The argument is roughly as follows. Tensor rank upper bounds lead
directly to matrix multiplication algorithms by the aforementioned contractions. On the other hand,
any arithmetic matrix multiplication algorithm can be made into an arithmetic circuit with an addition
layer followed by a bilinear multiplication layer followed by an addition layer, in such a way that the
number of bilinear multiplication nodes is at most twice the number of multiplications in the arithmetic
algorithm. The blow-up by a factor of two is because we only allow bilinear multiplications in our
arithmetic circuit. This representation leads directly to a tensor rank upper bound. As we said before, the
matrix multiplication exponent ω is defined as the infimum over all β for which the arithmetic complexity
of multiplying two n × n matrices is at most O(nβ ). Matrix multiplication tensors are multiplicative in
the sense that ha, b, ci ⊗ hd, e, f i is isomorphic to had, be, c f i. From the multiplicativity of the matrix
multiplication tensors it is easy to derive that ω is characterized by the asymptotic rank of h2, 2, 2i as
follows.
Proposition 2.1 (see, e. g., [7, Theorem 5.2]). ω = log2 R(h2, 2, 2i).
e
The difficulty of determining the asymptotic rank of h2, 2, 2i is to be contrasted with the situation for
the asymptotic subrank; to put it in Strassen’s words: Unlike the cynic, who according to Oscar Wilde
knows the price of everything and the value of nothing, we can determine the asymptotic value of hh, h, hi
precisely.
Proposition 2.2 ([30]). 2 = log2 Q(h2, 2, 2i). More precisely, for any h ∈ N it holds that
e
Q(hh, h, hi) = h2 . (2.5)
e
For completeness of the paper we give a proof of Proposition 2.2. The proof we provide here is based
on Salem–Spencer sets and is slightly different from the proof in [30]. However, the two proofs become
very similar when the construction of Salem–Spencer sets is unrolled.
Proof. Since each flattening rank of the diagonal tensor In equals n and since the flattening rank of hh, h, hi
equals h2 we find by multiplicativity and monotonicity of the flattening rank that Q(hh, h, hi) ≤ h2 .
We must prove the matching lower bound. Let p be a large prime. There is a subset e A ⊆ Z/pZ (a
T HEORY OF C OMPUTING, Volume 17 (2), 2021, pp. 1–32 7
M ATTHIAS C HRISTANDL , P ÉTER V RANA , AND J EROEN Z UIDDAM
Salem–Spencer set in Z/pZ) that is free of nontrivial three-term arithmetic progressions and that has
size |A| = p1−o(1) [25, 5]. The support of the tensor hp, p, pi is the set of triples
E = {((i, j), ( j, k), (k, i)) : i, j, k ∈ [p]} .
We think of E as a 3-partite 3-uniform hypergraph E ⊆ V1 × V2 × V3 with vertex sets V` = [p] × [p].
Consider the subhypergraph F ⊆ E induced by the vertex sets
W1 = {(x, x + a) ∈ V1 : x ∈ [p], a ∈ A} .
W2 = {(x, x + a) ∈ V2 : x ∈ [p], a ∈ A} .
W3 = {(x + 2a, x) ∈ V3 : x ∈ [p], a ∈ A} .
That is, F = E ∩ (W1 ×W2 ×W3 ). Then
F = {((i, j), ( j, k), (k, i)) : (i, j, k) = (x, x + a, x + 2a) for some x ∈ [p] and a ∈ A} .
Indeed, a priori, ((i, j), ( j, k), (k, i)) ∈ F if and only if
(i, j, k) = (x, x + a, x + a + b = x + 2c)
for some x ∈ [p] and a, b, c ∈ A. Then a, (a + b)/2, b is a three-term arithmetic progression in A, and thus
a = b and the claim follows. We see that the set F has p |A| = p2−o(1) elements. We also see that for
any triple ((i, j), ( j, k), (k, i)) in F, the first vertex (i, j) determines the second vertex ( j, k) and the third
vertex (k, i), and similarly the second vertex determines the first and third vertex and the third vertex
determines the first and second vertex. In other words, the edges in F are disjoint in all coordinates,
that is, they form a matching. Restrict the tensor hp, p, pi ∈ FV1 ×V2 ×V3 to FW1 ×W2 ×W3 by restricting the
coordinates in each direction from V` to W` . The support of the resulting tensor is the matching F. After a
suitable permutation of each W` , this tensor becomes a diagonal tensor of size |F| = p2−o(1) . We conclude
that for every prime p we have Q(hp, p, pi) ≥ p2−o(1) . By a simple tensor product argument this implies
the claim for all h ∈ N. Namely, for every h ∈ N we take a prime p such that hn is not much bigger
than an integer power of p, that is, hn ≥ pm ≥ hn /p. Then hhn , hn , hn i ≥ hpm , pm , pm i and we find that
Q(hhn , hn , hn i) ≥ h2n−o(n) .
Remark 2.3. We remarked before that Strassen’s proof of Proposition 2.2 in [30] takes a slightly different
route. Namely, it makes use of an approximative relaxation of subrank called border subrank, which is
denoted by Q. He shows that Q(hm, m, mi) ≥ d 34 m2 e. (This lower bound, and all Strassen’s lower bounds
for Q(ha, b, ci), are in fact tight [21].) Strassen then relates the border subrank to the asymptotic subrank
via a simple polynomial interpolation argument to get that Q(hm, m, mi) = m2 .
e
2.2 Relative exponent
For a clean exposition of our barrier we will use the notion of relative exponent, which we will define in
this section. This notion is inspired by the notion of rate from information theory and alternatively can be
T HEORY OF C OMPUTING, Volume 17 (2), 2021, pp. 1–32 8
BARRIERS FOR FAST M ATRIX M ULTIPLICATION FROM I RREVERSIBILITY
seen as a versatile version of the notion of the asymptotic preorder for tensors of Strassen.2 In the context
of tensors, the relative exponent previously appeared in [38],[37] and [13].
To avoid technicalities, we will from now on, without further mentioning, only consider tensors that
are not of tensor rank one or zero. This assumption is explicitly used in the proof of Theorem 2.5(i) and
its applications.
Definition 2.4. For two tensors t ∈ Fn1 ×n2 ×n3 and s ∈ Fm1 ×m2 ×m3 we define the relative exponent from t
to s as
ω(t, s) := lim n1 min{m ∈ N≥1 : t ⊗m ≥ s⊗n } (2.6)
n→∞
= sup 1n min{m ∈ N≥1 : t ⊗m ≥ s⊗n }. (2.7)
n
The limit is a supremum by Fekete’s lemma. Let us briefly relate the relative exponent to the basic
notions and results stated earlier. The reader verifies directly that the identities
ω(h2i,t) = log2 R(t) (2.8)
ω(t, h2i) = 1/(log2 Q(t))
e
(2.9)
e
hold by approximating integers by powers of 2, or see [13, Proposition 1.1.16] for a proof. From the fact
that ω := log2 R(h2, 2, 2i) (Proposition 2.1) it follows that
e
ω(h2i, h2, 2, 2i) = ω . (2.10)
We know from (2.5) that Q(h2, 2, 2i) = 4 and so
e
ω(h2, 2, 2i, h2i) = 21 . (2.11)
The relative exponent has the following two basic properties.
Proposition 2.5. Let s, t and u be tensors.
(i) ω(t,t) = 1.
(ii) ω(s,t) ω(t, u) ≥ ω(s, u) (triangle inequality).
Proof. (i) Clearly ω(t,t) ≤ 1 by reflexivity of the restriction preorder ≥. Since t is not of rank 1, we
can flatten t into a matrix in one of the three directions, so that the matrix rank is some number r > 1. It
follows from multiplicativity of matrix rank, that if t ⊗m ≥ t ⊗n , then rm ≥ rn and so m ≥ n. This implies
the claim. (ii) follows from the transitivity of the restriction preorder ≥.
2 The asymptotic preorder & is defined as follows: s & t if s⊗n+o(n) ≥ t ⊗n when n → ∞.
T HEORY OF C OMPUTING, Volume 17 (2), 2021, pp. 1–32 9
M ATTHIAS C HRISTANDL , P ÉTER V RANA , AND J EROEN Z UIDDAM
2.3 Irreversibility
Our barrier framework relies crucially on the irreversibility of a tensor, a new notion that we define now.
Definition 2.6. We define the irreversibility of a tensor t as the product of the relative exponent from h2i
to t and the relative exponent from t to h2i, i. e.,
i(t) := ω(h2i,t) ω(t, h2i) . (2.12)
Thus i(t) measures the extent to which the asymptotic conversion from h2i to t is irreversible, explaining
the name. Equivalently, the irreversibility is the ratio of the logarithms of the asymptotic rank and the
asymptotic subrank, i. e.,
log2 R(t)
i(t) = e . (2.13)
log2 Q(t)
e
Proposition 2.7. For any tensor t it holds that
i(t) ≥ 1 . (2.14)
Proof. From the basic properties of the relative exponent (Proposition 2.5) it follows directly that the
inequality i(t) = ω(h2i,t) ω(t, h2i) ≥ ω(h2i, h2i) = 1 holds.
Definition 2.8. We call a tensor t reversible if i(t) = 1 and irreversible otherwise (in which case it holds
that i(t) > 1 by Proposition 2.7).
For example, for any n ∈ N the diagonal tensor hni = ∑ni=1 ei,i,i is reversible. In fact, every reversible
tensor t, that we know of, is equivalent to hni for some n, in the sense that hni ≤ t ≤ hni. In other words,
we do not know whether every reversible tensor t is equivalent to hni for some n.
This question is closely related to whether the matrix multiplication exponent ω equals 2. For the
matrix multiplication tensor h2, 2, 2i we have that 2 i(h2, 2, 2i) = ω (using (2.11)). Thus ω = 2 if and
only if h2, 2, 2i is reversible. (In fact, for any n ∈ N it holds that ω = 2 if and only if hn, n, ni is reversible.)
As we will see in Section 3, this is ultimately the source of our barrier.
Irreversible tensors do in fact exist. For example, the tensor W = e0,0,1 + e0,1,0 + e1,0,0 is irreversible.
Namely, it is known that log2 R(W ) = 1 and that log2 Q(W ) = h(1/3) = 0.918.. [31, Theorem 6.7],
so i(W ) = 1.088.. > 1. In Section e 5 we will compute lower e bounds on the irreversibility of the small and
big Coppersmith–Winograd tensors (which play a crucial role in the best upper bounds on ω).
2.4 Monomial relative exponent and monomial irreversibility
The following restricted version of relative exponent and irreversibility will be relevant. A generalized
subpermutation matrix is a matrix for which every row and every column has at most one nonzero
coefficient. For two tensors t ∈ Fn1 ×n2 ×n3 and s ∈ Fm1 ×m2 ×m3 we write t ≥M s and say t monomially
restricts to s if there are linear maps Ai : Fni → Fmi , the corresponding matrices of which are generalized
subpermutation matrices in the standard basis, such that (A1 , A2 , A3 ) · t = s [29, Section 6]. Thus s is a
monomial restriction of t if we can obtain s from t by rescaling (also to zero) and permuting the slices
of t. Monomial restriction plays a central role in the existing upper bounds on ω.
T HEORY OF C OMPUTING, Volume 17 (2), 2021, pp. 1–32 10
BARRIERS FOR FAST M ATRIX M ULTIPLICATION FROM I RREVERSIBILITY
Replacing the preorder ≥ by ≥M in Section 2 gives the notions of monomial subrank QM , monomial
asymptotic subrank QM and monomial relative exponent ωM . (For simplicity we will use monomial
e results will also hold with ≥M replaced by monomial degeneration DM defined
restriction here, but our
in [29, Section 6]. Monomial degeneration is the approximative version of monomial restriction. It is
reflexive and transitive like monomial restriction.) Note that the notions QM and QM only depend on the
support of the tensor, and not on the particular values of the nonzero coefficients. We
e define the monomial
irreversibility iM (t) of t as the product of the (normal) relative exponent from h2i to t and the monomial
relative exponent from t to h2i,
iM (t) := ω(h2i,t) ωM (t, h2i) . (2.15)
Equivalently, we have
log2 R(t)
iM (t) = . (2.16)
log2 QM (t)
e
e
We stress that the monomial irreversibility uses the monomial asymptotic subrank, but the regular
asymptotic rank. This is in fact what is used in practice. We note that monomial (asymptotic) rank
is a useless concept, since any monomial restriction of a unit tensor is again a unit tensor. In other
words, using the monomial asymptotic rank is too restrictive and gives bad algorithms from the start. In
particular, monomial irreversibility depends on the tensor and not only on its support.
Proposition 2.9. Let s, t and u be tensors.
(i) ωM (t,t) = 1.
(ii) ωM (s,t) ωM (t, u) ≥ ωM (s, u) (triangle inequality).
(iii) ωM (s,t) ≥ ω(s,t).
(iv) iM (t) ≥ i(t).
Proof. The first two statements follow from reflexivity and transitivity of the monomial restriction
preorder ≥M , just like in the proof of Proposition 2.5. The other two statements follow from the fact that
s ≥M t implies s ≥ t.
Definition 2.10. We call a tensor t monomially reversible if iM (t) = 1 and monomially irreversible
otherwise (in which case it holds that iM (t) > 1 by Proposition 2.9 (iv) and Proposition 2.7).
There exist tensors that are reversible and monomially irreversible. We give an example.
Example 2.11. For any finite group G, we define the tensor hGiF ∈ FG×G×G by
hGiF := ∑ eg,h,gh .
g,h∈G
The tensor hGiF is often referred to as the structure tensor of the group algebra F[G]. The group algebra
F[G] is the vector space FG that has a bilinear multiplication operation defined on it by setting eg · eh = egh
for the basis elements {eg : g ∈ G} and extending bilinearly to F[G]. Thus hGiF precisely encodes this
multiplication. We stress that in the notation hGiF the parameter G determines the support and the
T HEORY OF C OMPUTING, Volume 17 (2), 2021, pp. 1–32 11
M ATTHIAS C HRISTANDL , P ÉTER V RANA , AND J EROEN Z UIDDAM
parameter F denotes over which field we consider the tensor. Even though all coefficients of hGiF are 0
or 1, the choice of base field F determines what linear maps are allowed in the restriction preorder ≥ and
thus the notion of equivalence and the notion of isomorphism. Crucially, for the monomial restriction
preorder ≥M applied to tensors with coefficients that are only 0 or 1, the choice of base field does not
make a difference.
We consider the structure tensor
hZ/3ZiF = e0,0,0 + e0,1,1 + e1,0,1 + e2,0,2 + e0,2,2 + e1,1,2 + e1,2,0 + e2,1,0 + e2,2,1 . (2.17)
First of all, hZ/3ZiC is isomorphic to the diagonal tensor h3i. In general, for any finite abelian group A,
the structure tensor hAiC is isomorphic to the diagonal tensor h|A|i, using the Fourier transform on A to
diagonalize the multiplication (see, e. g., [8] or [12] for a discussion of this). Therefore, R(hZ/3ZiC ) = 3
and Q(hZ/3ZiC ) = 3 and hence hZ/3ZiC is reversible. e
e fact, for general F, we have R(hZ/3ZiF ) = 3 because there is a monomial degeneration from the
In
restricted polynomial multiplicatione tensor to hZ/3ZiF , see [12, Theorem 4.16]. On the other hand, it is
known that QM (hZ/3ZiF ) = 2.755... This is proven in [19, 33], see also [12] for the connection to [31].
It follows fore any field F that iM (hZ/3ZiF ) = 1.08.. and that hZ/3ZiF is monomially irreversible.
Regarding matrix multiplication, Strassen’s construction for (2.11) (see also our proof of Proposi-
tion 2.2) in fact shows that
ωM (h2, 2, 2i, h2i) = 21 . (2.18)
2.5 Upper bounds on irreversibility
We finish this section by discussing the possible values that the irreversibility can take, as a first step
towards a systematic understanding of where we may find reversible tensors or almost reversible tensors.
We will see that, surprisingly at first sight, the matrix multiplication exponent ω provides bounds on the
irreversibility of arbitrary tensors.
First of all, if Q(t) ≤ 1, then i(t) = ∞. Thus, a priori, the irreversibility of a tensor could be any
number in [1, ∞]. Recall
e that we defined the flattenings of any tensor t ∈ Fn1 ×n2 ×n3 as the linear maps
n
t1 : F → F
1 n2 ×n3 , t2 : F → Fn1 ×n3 and t3 : Fn3 → Fn1 ×n2 that are naturally associated to t. For any
n2
tensor t that has a flattening with rank (as a linear map) at most 1 it holds that Q(t) ≤ 1. For example,
Q(hn, 1, 1i) = 1. If none of the flattening ranks is at most 1, then the asymptotic subrank
e is at least some
absolute
e constant c > 1, as follows from [30, Lemma 3.7]. Thus in that case the irreversibility is finite.
On the other hand, for any t ∈ Fn×n×n the upper bound R(t) ≤ R(t) ≤ n2 holds. We conclude that, for
t ∈ Fn×n×n , if any flattening rank is at most 1, then i(t) =e∞, and otherwise
1 ≤ i(t) ≤ d log2 n
for some absolute constant d. This gives us an idea of the order of magnitude of the irreversibility. We
will refine this upper bound in the rest of this discussion.
As the first step towards gaining more control on the possible values of the irreversibility, we note
that for asymptotic rank we have the following general upper bound.
Proposition 2.12 ([30, Proposition 3.6]). For t ∈ Fn×n×n it holds that R(t) ≤ n2ω/3 .
e
T HEORY OF C OMPUTING, Volume 17 (2), 2021, pp. 1–32 12
BARRIERS FOR FAST M ATRIX M ULTIPLICATION FROM I RREVERSIBILITY
Proof. We give a sketch of the argument. For any tensor t ∈ Fn×n×n it holds that t ≤ hn, n, 1i and
t ≤ hn, 1, ni and t ≤ h1, n, ni. By multiplying these inequalities, it follows that t ⊗3 ≤ hn2 , n2 , n2 i. It is not
hard to see that therefore R(t) ≤ R(hn, n, ni)2/3 = n2ω/3 .
e e
It is possible that ω = 2, in which case it follows from Proposition 2.12 that R(t) ≤ n4/3 for every
t ∈ Fn×n×n . More generally, it is possible that for every tensor t ∈ Fn×n×n we have ethe highly non-trivial
upper bound R(t) ≤ n, see [10, Problem 15.5]. Strassen conjectured this to be true for a subset of all
tensors calledetight tensors [32, Conjecture 5.3].
Proposition 2.12 gives us some control over the possible values of the irreversibility. As the next step
in that direction we must understand how small the asymptotic subrank can be. First, we give an example
of a tensor for which the asymptotic subrank and the asymptotic rank are far apart.
Example 2.13. Let t ∈ Fn×n×n be the tensor t = e1,n,1 + en,1,1 + e2,n,2 + en,2,2 + · · · + en,n,n . Then Q(t) = 2
while R(t) = n and so we have that i(t) = log2 (n). e
e
For the rest of the discussion we require our tensors to satisfy a property called balanced. This
property was introduced in [30, page 121]. Not all tensors are balanced, but in any tensor space Fn×n×n
over an algebraically closed field F, being balanced is a generic condition in the sense of algebraic
geometry. In particular, almost all elements in Fn×n×n are balanced. We define a tensor t ∈ Fn1 ×n2 ×n3 to
be balanced if the three flattenings that we defined before are full-rank as linear maps and for each i ∈ [3]
there is an element v ∈ Fn such that the element ti (v) has full rank (as a matrix). Balanced tensors are
called 1-generic tensors in [22]. An example of a non-balanced tensor is the tensor in Example 2.13. An
example of a balanced tensor is the matrix multiplication tensor hn, n, ni.
Proposition 2.14. Let t ∈ Fn×n×n be balanced. Then
1 ≤ i(t) ≤ ω .
Proof. The claim follows from the following two ingredients. The first ingredient is the general upper
bound R(t) ≤ n2ω/3 from Proposition 2.12. The second ingredient is the lower bound Q(t) ≥ n2/3
[30, Proposition
e 3.6] for balanced tensors. We give a sketch of the argument. From the balancedness
e
assumption it follows that hn, 1, 1i ≤ t and h1, n, 1i ≤ n and h1, 1, ni ≤ t. By multiplying these inequalities
we get hn, n, ni ≤ t ⊗3 . Therefore, using Proposition 2.2, we have n2 ≤ Q(hn, n, ni) ≤ Q(t)3 .
e e
Again, it is possible that ω = 2, in which case it follows from Proposition 2.14 that 1 ≤ i(t) ≤ 2 for
balanced t. More generally, it is possible that for every tensor t ∈ Fn×n×n we have the highly non-trivial
upper bound R(t) ≤ n. In that case we have the following bounds.
e
Proposition 2.15. Let t ∈ Fn×n×n be balanced and satisfy R(t) ≤ n. Then
e
1 ≤ i(t) ≤ 1.5 .
Proof. The claim follows directly from combining Q(t) ≥ n2/3 , which follows from balancedness as we
saw in the proof of Proposition 2.14, and the assumption
e R(t) ≤ n.
e
Example 2.16. The upper bound in Proposition 2.15 is tight. Namely, let t = cwq be the small
Coppersmith–Winograd tensor with parameter q. We will see from Theorem 5.1 that i(t) → 1.5 when q
goes to infinity.
T HEORY OF C OMPUTING, Volume 17 (2), 2021, pp. 1–32 13
M ATTHIAS C HRISTANDL , P ÉTER V RANA , AND J EROEN Z UIDDAM
3 Irreversibility implies barriers
With the new notion of irreversibility available, we present a barrier for approaches to upper bound ω via
an intermediate tensor t. As we have discussed before, all recent successful upper bounds on ω have been
obtained with constructions via an intermediate tensor. The results in this section tell us which tensors
not to use as intermediate tensors and what necessary quality a good intermediate tensor has.
3.1 The irreversibility barrier
For any tensor t the inequality
ω(h2i,t) ω(t, h2, 2, 2i) ≥ ω (3.1)
holds by the triangle inequality. Any such approach to upper bound ω respects the following barrier in
terms of the irreversibility i(t) of t.
Theorem 3.1. For any tensor t it holds that
ω(h2i,t) ω(t, h2, 2, 2i) ≥ 2 i(t) . (3.2)
Proof. By the triangle inequality (Proposition 2.5),
ω(h2i,t) ω(t, h2, 2, 2i) ω(h2, 2, 2i, h2i) ≥ ω(h2i,t) ω(t, h2i) = i(t) . (3.3)
Therefore, using the fact ω(h2, 2, 2i, h2i) = 21 from (2.11), we have
i(t)
ω(h2i,t) ω(t, h2, 2, 2i) ≥ = 2 i(t) . (3.4)
ω(h2, 2, 2i, h2i)
This proves the claim.
Theorem 3.1, in particular, implies that if i(t) > 1, then ω(h2i,t) ω(t, h2, 2, 2i) > 2. In other words, we
cannot prove ω = 2 via an irreversible intermediate tensor. However, it is possible that there exists a
sequence of irreversible intermediate tensors with irreversibility converging to 1 that can be used to prove
ω = 2.
To conclude, the barrier just introduced describes what quality makes a tensor a good intermediate
tensor, or put differently what intermediate tensors definitely not to use when we want to prove good
upper bounds on ω. Of course the barrier does not tell us explicitly which intermediate tensor to pick,
but it provides a strong heuristic of what to look for, namely low asymptotic rank and high asymptotic
subrank.
3.2 Better barriers when the method has more structure
The barrier discussed in Section 3.1 does not tell the full story, and we will now discuss the natural
and more subtle continuation. Namely, not only will we lose the game when the intermediate tensor is
irreversible, we lose even more when we use this intermediate tensor in a catalytic fashion, meaning that
our algorithm is obtained from transforming a diagonal tensor to the tensor product of a diagonal tensor
T HEORY OF C OMPUTING, Volume 17 (2), 2021, pp. 1–32 14
BARRIERS FOR FAST M ATRIX M ULTIPLICATION FROM I RREVERSIBILITY
and a matrix multiplication tensor (via the intermediate tensor). We will explain this more, but for now it
is important to know that this strategy is commonly used in the literature (with great success). However,
as we will see in this section, such a catalytic approach boosts the previous barrier even more. Thus this
section gives rise to a more precise heuristic which says that, while looking for intermediate tensors with
small irreversibility, we may at the same time want to think about intermediate tensors that require less
use of catalysis.
Catalysis in the general context of tensors is the phenomenon that for tensors s, t and u, the inequal-
ity s ≥ t may be false, while the inequality s ⊗ u ≥ t ⊗ u may be true. The latter inequality is called
catalytic with the tensor u acting as a catalyst.
Catalysis is widely used in matrix multiplication algorithms albeit not under this explicit terminology.
We will now discuss more quantitatively what we mean when we say that an approach to upper bound
ω uses catalysis. Without loss of generality we may impose that the final step of any construction of a
matrix multiplication algorithm is an application of the Schönhage τ-theorem. The Schönhage τ-theorem
(Strassen’s general version [30]) says that
Mq q
R hai , bi , ci i ≥ ∑ (ai bi ci )ω/3 . (3.5)
e i=1 i=1
In particular, for ai = bi = ci = a, it holds that
R hqi ⊗ ha, a, ai ≥ qaω . (3.6)
e
(And this inequality is in fact tight, although we will not go into that here.) We are using here that the
direct sum of q copies of a tensor t is isomorphic to the tensor product of the diagonal tensor hqi and t.
Equivalently, in the language of rates, for any α, β ∈ N it holds that
ω(h2i, h2iα h2, 2, 2iβ ) ≥ α + β ω (3.7)
that is
ω(h2i, h2iα h2, 2, 2iβ ) − α
≥ω. (3.8)
β
(Here α corresponds to log2 q and β corresponds to log2 a. For simplicity and concreteness we will
consider only integer α and β .) Thus for any tensor t and for any α, β ∈ N it holds that
ω(h2i,t) ω(t, h2iα h2, 2, 2iβ ) − α
≥ω. (3.9)
β
Inequality (3.9) is a method for giving upper bounds on ω and we say that it is catalytic when α > 0,
the catalyst being the tensor h2iα . In fact, upper bounds coming from the approach in the Coppersmith–
Winograd paper and its follow-ups take the form of this inequality for specific t, α and β . The following
barrier in terms of α, β and the irreversibility i(t) of t for any method of the form (3.9) says that catalysis
boosts the irreversibility barrier.
T HEORY OF C OMPUTING, Volume 17 (2), 2021, pp. 1–32 15
M ATTHIAS C HRISTANDL , P ÉTER V RANA , AND J EROEN Z UIDDAM
Theorem 3.2. For any tensor t and α, β ∈ N it holds that
ω(h2i,t) ω(t, h2iα h2, 2, 2iβ ) − α α
≥ 2 i(t) + i(t) − 1 ≥ 2 i(t) . (3.10)
β β
Proof. By the triangle inequality,
ω(h2i,t) ω(t, h2iα h2, 2, 2iβ ) ω(h2iα h2, 2, 2iβ , h2i) ≥ ω(h2i,t) ω(t, h2i) = i(t) . (3.11)
Therefore,
i(t)
ω(h2i,t) ω(t, h2iα h2, 2, 2iβ ) ≥ . (3.12)
ω(h2iα h2, 2, 2iβ , h2i)
We can bound this by
i(t)
≥ (α + 2β ) i(t) (3.13)
ω(h2iα h2, 2, 2iβ , h2i)
since for any tensors s,t, u the inequality ω(s ⊗ t, u)−1 ≥ ω(s, u)−1 + ω(t, u)−1 holds. (The inequality in
(3.13) is actually known to be an equality, since the asymptotic subrank is known to be additive on any
collection of tensors of the form {⊕it ⊗ni : ni ∈ N} for any fixed tensor t. This for example follows from
the asymptotic subrank being characterized by the asymptotic spectrum of tensors that we will discuss in
the next section.) Combining (3.12) and (3.13), subtracting α, dividing by β and using that i(t) − 1 ≥ 0
(Proposition 2.7) gives the barrier
ω(h2i,t) ω(t, h2iα h2, 2, 2iβ ) − α (α + 2β ) i(t) − α α
≥ = 2 i(t) + (i(t) − 1) ≥ 2 i(t) . (3.14)
β β β
This proves the claim.
As a corollary of the above theorem, we present a barrier on any approach of the following form. The
Schönhage τ-theorem implies that for any a, b, c ∈ N≥1 and any tensor t it holds that
ω(h2i,t) ω(t, h2iα ha, b, ci) − α
1
≥ω. (3.15)
3 log2 (abc)
Again, we think of this inequality as a method for upper bounding ω. To prove a barrier for this
method we define a cyclic symmetrization of t. For any tensor t = (ti jk ) ∈ Fn×n×n we define the cyclic
permutations (1, 2, 3) · t and (1, 2, 3)2 · t by cyclically permuting the indices i, j and k. We define the
3 3 3
cyclic symmetrization cyc(t) by cyc(t) := t ⊗ ((1, 2, 3) · t) ⊗ ((1, 2, 3)2 · t) ∈ Fn ×n ×n . For example,
cyc(ha, b, ci) = ha, b, ci ⊗ hc, a, bi ⊗ hb, c, ai = habc, abc, abci. We prove the following barrier in terms
of a, b, c, α and the irreversibility of cyc(t).
Corollary 3.3. For any tensor t and α ∈ N and a, b, c ∈ N≥1 it holds that
ω(h2i,t) ω(t, h2iα ha, b, ci) − α α
1
≥ 2 i(cyc(t)) + 1 (i(cyc(t)) − 1) (3.16)
3 log2 (abc) 3 log2 (abc)
≥ 2 i(cyc(t)) . (3.17)
T HEORY OF C OMPUTING, Volume 17 (2), 2021, pp. 1–32 16
BARRIERS FOR FAST M ATRIX M ULTIPLICATION FROM I RREVERSIBILITY
One verifies that i(t) ≥ i(cyc(t)). If t is cyclically symmetric, then cyc(t) = t ⊗3 and we have the
equality i(t) = i(cyc(t)).
Proof of Corollary 3.3. We first prove that
1
ω(h2i,t) ≥ ω(h2i, cyc(t) 3 ) .
Suppose that h2im ≥ t n . Then also h2im ≥ ((1, 2, 3) · t)n and h2im ≥ ((1, 2, 3)2 · t)n . Multiplying these
inequalities gives h2i3m ≥ cyc(t)n . We conclude that m/n ≥ ω(h2i, cyc(t)1/3 ). By a similar argument we
find that
1 1
ω(t, h2iα ha, b, ci) ≥ ω(cyc(t) 3 , h2iα h2, 2, 2i 3 log2 (abc) ) . (3.18)
Note that we are using real powers of tensors here inside the relative exponent ω(·, ·). This is justified
by taking powers of the relevant tensors and taking a limit. Using both inequalities and then applying
Theorem 3.2 gives
1
ω(h2i,t) ω(t, h2iα ha, b, ci) − α ω(h2i, cyc(t)) ω(cyc(t), h2iα h2, 2, 2i 3 log2 (abc) ) − α
1
≥ 1
(3.19)
3 log2 (abc) 3 log2 (abc)
≥ 2 i(cyc(t)) . (3.20)
This proves the corollary.
3.3 Better barriers through monomial irreversibility
Finally, we impose as an extra constraint that the transformation from the intermediate tensor t to the
matrix multiplication tensor happens via monomial restriction (Section 2.4), that is, we consider the
approach
ω(h2i,t) ωM (t, h2, 2, 2i) ≥ ω (3.21)
and the more structured approaches
ω(h2i,t) ωM (t, h2iα h2, 2, 2iβ ) − α
≥ω (3.22)
β
and
ω(h2i,t) ωM (t, h2iα ha, b, ci) − α
1
≥ω. (3.23)
3 log2 (abc)
The proofs in the previous sections can be directly adapted to prove:
Theorem 3.4. For any tensor t it holds that
ω(h2i,t) ωM (t, h2, 2, 2i) ≥ 2 iM (t) . (3.24)
Theorem 3.5. For any tensor t and α, β ∈ N it holds that
ω(h2i,t) ωM (t, h2iα h2, 2, 2iβ ) − α α
≥ 2 iM (t) + iM (t) − 1 ≥ 2 iM (t) . (3.25)
β β
T HEORY OF C OMPUTING, Volume 17 (2), 2021, pp. 1–32 17
M ATTHIAS C HRISTANDL , P ÉTER V RANA , AND J EROEN Z UIDDAM
Corollary 3.6. For any tensor t and α ∈ N and a, b, c ∈ N≥1 it holds that
ω(h2i,t) ωM (t, h2iα ha, b, ci) − α α
1
≥ 2 iM (cyc(t)) + 1 (iM (cyc(t)) − 1) (3.26)
3 log2 (abc) 3 log2 (abc)
≥ 2 iM (cyc(t)) . (3.27)
4 Methods for lower bounding irreversibility
We have seen how lower bounds on irreversibility imply barriers. By definition of irreversibility, such
lower bounds come from lower bounds on asymptotic rank and upper bounds on asymptotic subrank. In
this section we discuss lower bounding irreversibility from four points of view: the asymptotic spectrum
of tensors, the support functionals, the quantum functionals and the asymptotic slice rank. We will use
the support functionals to compute explicit barriers in Section 5; the rest of this section serves as a survey
and to provide comparison.
4.1 The asymptotic spectrum of tensors
We begin with an abstract and clean approach to characterizing irreversibility, and will move to practical
bounds in the following sections. Let S be a family of tensors that is closed under ⊗ and ⊕ and that
contains h1i. Strassen [30] introduced the asymptotic spectrum of tensors ∆(S) as the set of all maps
F : S → R≥0 that satisfy for any tensors s and t in S that
• s ≤ t ⇒ F(s) ≤ F(t) ,
• F(s ⊗ t) = F(s)F(t) ,
• F(s ⊕ t) = F(s) + F(t) ,
• F(h1i) = 1 .
Strassen proved in [30] that for any tensor t ∈ S it holds that Q(t) = minF∈∆(S) F(t) and R(t) =
maxF∈∆(S) F(t). From this we directly obtain the following concise e
characterization of irreversibility
e in
terms of the asymptotic spectrum of tensors ∆(S).
Proposition 4.1. Let t be a tensor in S. Then
maxF∈∆(S) log F(t)
i(t) = . (4.1)
minG∈∆(S) log G(t)
This characterization is clean but does not lead to a practical way of computing, or even lower
bounding, the irreversibility i(t) for a general tensor t. This is because our knowledge of ∆(S) is very
limited for any general family of tensors S. Namely, a priori we only know that for every i ∈ [3] the
function t 7→ R(ti ) is in ∆(S), where ti is the flattening as described in Section 2.5. Thus we have the
inequalities Q(t) ≤ mini R(ti ) and R(t) ≥ maxi R(ti ). In fact, maxi R(ti ) is the best lower bound on R(t)
that we know e of. We will keep using
e this lower bound on the asymptotic rank in the coming, more e
practical, sections. There are, however, more powerful tools than the flattening ranks R(ti ) to upper
bound Q(t), which we will discuss now.
e
T HEORY OF C OMPUTING, Volume 17 (2), 2021, pp. 1–32 18
BARRIERS FOR FAST M ATRIX M ULTIPLICATION FROM I RREVERSIBILITY
4.2 The support functionals
The support functionals of Strassen provide an extremely powerful method for upper bounding the
asymptotic subrank of tensors (and hence lower bounding irreversibility). The definition of the support
functionals is technical at first sight, but as a reward these compact objects provide us with the best upper
bounds on the asymptotic subrank. Before we define the support functionals, we need to define some
notions for tensors and for probability distributions. For tensors s,t ∈ Fn1 ×n2 ×n3 we write s ∼ = t and say
that s and t are isomorphic if there are invertible linear maps Ai such that (A1 , A2 , A3 ) · s = t. Recall that
we denote by
supp(s) := {(i1 , i2 , i3 ) ∈ [n1 ] × [n2 ] × [n3 ] : si1 ,i2 ,i3 6= 0}
the support of s. For any probability distribution Q on [n] let H(Q) = ∑i∈[n] Q(i) log2 (1/Q(i)) denote
the Shannon entropy of Q. For any probability distribution P on [n1 ] × [n2 ] × [n3 ] let Pi be the marginal
distribution on [ni ]. That is, the marginal distribution P1 is defined by P1 (i1 ) := ∑i2 ∈[n2 ] ∑i3 ∈[n3 ] P(i1 , i2 , i3 )
and the other marginal distributions are defined similarly. Let P(supp(s)) denote the set of all probability
distributions on supp(s). (Thus for any element P ∈ P(supp(s)) we can talk about its marginal distribu-
tions Pi and their entropies H(Pi ).) For any tensor t and any probability vector θ ∈ R3 Strassen defined
the support functional ζ θ by setting
θ
ζ θ (t) := 2ρ (t)
where
3
ρ θ (t) := min
∼
max ∑ θi H(Pi ) .
s=t P∈P(supp(s))
i=1
(We note that we believe that the name support functional derives from the general concept of support
functions in convex analysis, rather than the support of tensors.) The minimization over all s isomorphic
to t appearing in the definition of ρ θ (t) is generally not well understood, but, fortunately, for the sake of
upper bounding ζ θ (t) it suffices to find one good s isomorphic to t. Note that the Shannon entropy H
is a concave function and thus the weighted marginal entropy ∑3i=1 θi H(Pi ) is a concave function of P.
Therefore, the analysis of the maximization over P, being a convex program over an explicitly given
domain, is usually straightforward.
It is not hard to see that the three flattening ranks R(ti ) are among the support functionals, namely
when we set θ to (1, 0, 0), (0, 1, 0) or (0, 0, 1). Thus the support functionals can be thought of as
interpolations between the three flattening ranks. Strassen proves in [31] the fundamental property that
Q(t) ≤ ζ θ (t) .
e
θ
There are numerous examples where minθ ζ (t) < mini R(ti ), of which we will see some later. It is not
known whether the equality Q(t) = minθ ζ θ (t) holds in general. Strassen proved that equality holds for
e 3 We conclude that we have the following lower bound on the irreducibility
the family of tight tensors [31].
in terms of the flattening ranks and the support functionals:
3 A tensor t is called tight if for some choice of basis there are injective maps α , α , α such that for every a ∈ supp(t)
1 2 3
it holds that α1 (a1 ) + α2 (a2 ) + α3 (a3 ) = 0. Tight tensors play an important role in the laser method for constructing matrix
multiplication algorithms, as the laser method requires the outer structure of the intermediate tensor to be tight.
T HEORY OF C OMPUTING, Volume 17 (2), 2021, pp. 1–32 19
M ATTHIAS C HRISTANDL , P ÉTER V RANA , AND J EROEN Z UIDDAM
Proposition 4.2. Let t be a tensor. Then
maxi log2 R(ti )
i(t) ≥ . (4.2)
minθ ρ θ (t)
We will use the method of the support functionals to lower bound the irreversibility of some explicit
tensors in Section 5.
Since we are primarily interested in using the support functionals to upper bound the asymptotic
subrank, it is worth to observe that by the von Neumann minimax theorem we may for any fixed tensor t
express minθ ρ θ (t) in the concise form
min ρ θ (t) = min
∼
max min H(Pi ) .
θ s=t P∈P(supp(s)) i∈[3]
Indeed, the function (θ , P) 7→ ∑i θi H(Pi ) is convex in θ and concave in P so the minimax theorem allows
us to swap the maximization over P and the minimization over θ . Moreover, minθ ∑i θi H(Pi ) is clearly
attained when θ is one of the vertices (1, 0, 0), (0, 1, 0), (0, 0, 1).
To further familiarize ourselves with the definition of ζ θ , we discuss a simple example. For this
example let t be the so-called W-tensor t = e1,2,2 + e2,1,2 + e2,2,1 . We will upper bound ζ θ (t) for
θ = (1/3, 1/3, 1/3). In the evaluation of ρ θ (t) we take s to be equal to t. (This turns out to be optimal in
this case, since t is tight [31].) Then the support of s is the set
supp(s) = {(1, 2, 2), (2, 1, 2), (2, 2, 1)} .
Let P ∈ P(supp(s)) assign probability a to (1, 2, 2), probability b to (2, 1, 2) and probability c to (2, 2, 1).
The function P 7→ ∑i 31 H(Pi ) is concave and invariant under permuting the values of a, b and c. Thus, the
maximum maxP∈P(supp(s)) ∑i 13 H(Pi ) is attained by the symmetric probability distribution P that assigns
a = b = c = 1/3 to each element in supp(s). Then each marginal distribution Pi assigns probability a to 1
and probability 2a to 2. Thus maxP∈P(supp(s)) ∑i 13 H(Pi ) equals the Shannon entropy of Pi , which is the
binary entropy h(1/3) = − 31 log2 13 − 23 log2 32 = 0.918.... We conclude that for the W-tensor t it holds
that the support functional ζ (1/3,1/3,1/3) (t) is at most 2h(1/3) = 1.88.... Note that 1.88... is strictly smaller
than the flattening rank R(ti ) = 2. We remark that in fact in this case we know the asymptotic monomial
subrank to be QM (t) = ζ (1/3,1/3,1/3) (t) = 2h(1/3) = 1.88... since this t is tight. Since a discussion of
tightness is notein the scope of this paper we refer to [31] for that.
5 Explicit barriers
We exhibit explicit barriers by computing lower bounds on the irreversibility of well-known intermediate
tensors that play a crucial role in the best upper bounds on the matrix multiplication exponent ω. These
tensors are the small and big Coppersmith–Winograd tensors. Then we discuss the reduced polynomial
multiplication tensors. Finally we discuss monomial irreversibility of structure tensors of finite group
algebras and relations to the group-theoretic approach.
T HEORY OF C OMPUTING, Volume 17 (2), 2021, pp. 1–32 20
BARRIERS FOR FAST M ATRIX M ULTIPLICATION FROM I RREVERSIBILITY
5.1 Irreversibility of Coppersmith–Winograd tensors
We now compute lower bounds for the irreversibility of the Coppersmith–Winograd tensors. As mentioned,
we will use the support functionals of Strassen [31] in our computation to upper bound the asymptotic
subrank.
(Upper bounds on the asymptotic subrank of complex tensors may be obtained, not only from the
Strassen support functionals, but also from the quantum functionals. For the tensors in Theorem 5.1 and
Theorem 5.4, however, it is known that the quantum functionals will give the same bound as the support
functionals, since these tensors are free tensors [12, Section 4.3].)
Theorem 5.1 (Small Coppersmith–Winograd tensors [17, Section 6]). For any integer q ≥ 2, the irre-
versibility of the small Coppersmith–Winograd tensor
q
cwq := ∑ e0,i,i + ei,0,i + ei,i,0 (5.1)
i=1
satisfies
log2 (q + 1)
2 i(cwq ) ≥ 2 · . (5.2)
log2 3 − 32 + 23 log2 q
Proof. The rank of each flattening of cwq equals q + 1. Therefore, R(cwq ) ≥ q + 1. To upper bound the
asymptotic subrank Q(cwq ) one can upper bound the Strassen supporte functional with θ = (1/3, 1/3, 1/3)
as in [12, Example 4.22]
e by
2 2
ρ θ (cwq ) ≤ log2 3 − + log2 q . (5.3)
3 3
We find that
log2 (q + 1)
i(cwq ) ≥ . (5.4)
log2 3 − 23 + 32 log2 q
This proves the theorem.
Remark 5.2. If q > 2, then the right-hand side of (5.2) is at least 2.02.. See the table in Section 1 for
more values. If q = 2, however, then the right-hand side of (5.2) equals 2. Theorem 5.1 thus does not rule
out using cw2 to prove that ω = 2. Indeed, as observed in [17, Section 11]), if ω(h2i, cw2 ) = log2 3, then
ω = 2.
Currently, the best upper bound we have on ω(h2i, cwq ) is log2 (q + 2). If ω(h2i, cwq ) = log2 (q + 2),
then instead of (5.2) we get the better barrier
2 log2 (q + 2)
2 i(cwq ) ≥ . (5.5)
log2 3 − 32 + 23 log2 q
The right-hand side of (5.5) has a minimum value of
18
= 2.27.. (5.6)
5 log2 3
attained at q = 6.
T HEORY OF C OMPUTING, Volume 17 (2), 2021, pp. 1–32 21
M ATTHIAS C HRISTANDL , P ÉTER V RANA , AND J EROEN Z UIDDAM
Remark 5.3. The following computation serves as a sanity check for our barrier given by Theorem 3.2.
Namely we see in an example how by putting some extra assumption the barrier given by Theorem 3.2
becomes tight. Coppersmith and Winograd in [17] used cwq as an intermediate tensor in combination
with the laser method and a certain outer structure. Here outer structure refers to the idea of viewing
the intermediate tensor as a block tensor. The outer structure is the block-support of the intermediate
tensor, see also [7, Section 9]. For cwq the outer structure is the W-tensor that we discussed in Section 4.2
which has asymptotic subrank 2h(1/3) . When we impose that we apply the laser method on cwq with
this outer structure to get an upper bound ω̂ ≥ ω we get the following better barrier via Theorem 3.2 or
Corollary 3.3 and α = h(1/3) and β = 13 log2 (q):
h(1/3)
ω̂ ≥ 2 i(cwq ) + 1 (i(cwq ) − 1) . (5.7)
3 log 2 (q)
Some values of (5.7) are as follows, using (5.4) to get a bound on i(cwq ):
q
2 2
3 2.04744
4 2.10545
5 2.15338
6 2.19236
7 2.22455
If in addition we assume that ω(h2i, cwq ) = log2 (q + 2), then we obtain the barrier
h(1/3)
ω̂ ≥ 2 i(cwq ) + 1 (i(cwq ) − 1) . (5.8)
3 log2 (q)
Some values of (5.8) are as follows, using (5.5) to get a bound on i(cwq ):
q
2 3.24511
3 2.65678
4 2.50000
5 2.44072
6 2.41594
7 2.40614
8 2.40363
9 2.40492
10 2.40824
11 2.41266
with minimum value of 2.40... These barriers in fact match the upper bound
4(q + 2)3
ω ≤ logq (5.9)
27
T HEORY OF C OMPUTING, Volume 17 (2), 2021, pp. 1–32 22
BARRIERS FOR FAST M ATRIX M ULTIPLICATION FROM I RREVERSIBILITY
that was obtained by Coppersmith and Winograd by applying the laser method in the way described
above. Thus our sanity check succeeds. Other intermediate tensors with a given outer structure may be
analyzed similarly.
Theorem 5.4 (Big Coppersmith–Winograd tensors [17, Section 7]). For any integer q ≥ 1 the irreversibil-
ity of the big Coppersmith–Winograd tensor
q
CWq := e0,0,q+1 + e0,q+1,0 + eq+1,0,0 + ∑ e0,i,i + ei,0,i + ei,i,0 (5.10)
i=1
satisfies
2 log2 (3)
√ = 2.16.. if q = 1
1
f1 ( 18 ( 33 − 3))
2 log2 (4)
2 i(CWq ) ≥ = 2.17.. if q = 2 (5.11)
f2 ( 91 )
2 log2 (q + 2)
√ if q ≥ 3
3q− 32+q2
fq
6(q2 −4)
where
2 2 1 1
fq (x) −
:= − qx log2 − qx − q · 2x log2 (2x) − − qx log2 − qx . (5.12)
3 3 3 3
Proof. First, we compute the asymptotic rank of CWq . One verifies directly that the matrix rank of each
flattening of CWq equals q + 2, so q + 2 ≤ R(CWq ). On the other hand, the well-known border rank
upper bound R(CWq ) ≤ q + 2 implies that R(CWe
q ) ≤ q + 2. We conclude that R(CWq ) = q + 2.
Second, we will upper bound the asymptotic subrank Q(CWq ) via the eStrassen support func-
e
θ
tional ζ θ (CWq ) with θ = (1/3, 1/3, 1/3). Recall that ζ θ (CWqe) = 2ρ (CWq ) where
3
ρ θ (CWq ) = ∼min max ∑ θi H(Pi ) .
s=CW P∈P(supp(s))
q i=1
We let s = CWq . Then the support of CWq is given by
supp(CWq ) = {(0, i, i), (i, 0, i), (i, i, 0) : i ∈ [q]} ∪ {(0, 0, q + 1), (0, q + 1, 0), (q + 1, 0, 0)} . (5.13)
We will now evaluate maxP∈P(supp(CWq )) ∑3i=1 θi H(Pi ). We first observe that supp(CWq ) is symmetric
under permutation of the three coordinates and under permutation of the elements of [q]. The function
P 7→ ∑3i=1 θi H(Pi ) is concave. Thus by a simple convexity argument we may in our maximization, without
loss of generality, consider only distributions P that assign some probability x to each of (0, i, i), (i, 0, i)
and (0, i, i) for all i ∈ [q], and probability 13 − qx to each of (0, 0, q + 1), (0, q + 1, 0) and (q + 1, 0, 0).
Under this simplification, we have that the average marginal entropy ∑3i=1 θi H(Pi ) equals fq (x) as defined
in the theorem statement. It remains to compute the maximum of fq (x) over all 0 ≤ x for which 3qx ≤ 1.
T HEORY OF C OMPUTING, Volume 17 (2), 2021, pp. 1–32 23
M ATTHIAS C HRISTANDL , P ÉTER V RANA , AND J EROEN Z UIDDAM
From a calculus computation (easy to verify using computer algebra software) it follows that the maximum
of fq (x) over all 0 ≤ x for which 3qx ≤ 1 is attained at
√
1
18 ( 33 − 3) if q = 1
1
if q = 2
x0 = 9 p (5.14)
3q − 32 + q 2
if q ≥ 3 .
6(q2 − 4)
Then Q(CWq ) ≤ 2 fq (x0 ) . Thus we have
e
2 i(CWq ) ≥ 2 log2 R(CWq )/ log2 Q(CWq ) ≥ 2 log2 (q + 2)/ fq (x0 ) ,
e e
which evaluates to the bound in the claim.
Remark 5.5. The lowest value of the right-hand side of (5.11) is 2.16.. attained at q = 1. See the table
in Section 1 for more values and see Appendix A for code to compute any values.
5.2 Irreversibility of reduced polynomial multiplication tensors
The reduced polynomial multiplication tensors tn are an example of a natural family of tensors in which
each tensor is irreversible, but where the irreversibility converges to 1 when n goes to infinity. The
irreversibility of the tensors tn can be computed directly from the computation of the asymptotic rank
and asymptotic subrank of tn in [31, Theorem 6.7], which uses the support functionals. Namely, Strassen
shows that
R(tn ) = n
e
and
Q(tn ) = z(n)
e
where
gn − 1 −2(n−1)/3
z(n) = g
g−1
and g > 1 is the unique positive real solution to the equation
1 n n−1
− n = .
g−1 g −1 3
Thus
log2 (n)
i(tn ) = .
log2 z(n)
The limit limn→∞ z(n)/n equals a constant, namely 0.84143... (see, e. g., [8, Equation 4.11]). It follows
that
lim i(tn ) = lim log2 (n)/ log2 z(n) = 1 .
n→∞ n→∞
Thus tn is “reversible in the limit.” In Appendix A we provide code to compute the values of i(tn ) for
any n.
T HEORY OF C OMPUTING, Volume 17 (2), 2021, pp. 1–32 24
BARRIERS FOR FAST M ATRIX M ULTIPLICATION FROM I RREVERSIBILITY
5.3 Monomial irreversibility of structure tensors of finite group algebras
We now discuss irreversibility and monomial irreversibility in the context of the group-theoretic approach
developed in [15]. This approach produces upper bounds on ω via intermediate tensors that are structure
tensors of complex group algebras of finite groups. As defined earlier, let hGiF denote the structure tensor
of the group algebra F[G] of the finite group G, in the standard basis, that is,
hGiF := ∑ eg,h,gh ∈ FG×G×G . (5.15)
g,h∈G
The group-theoretic approach (in particular [15, Theorem 4.1]) produces an inequality of the form
hGiC ≥M ha, b, ci (5.16)
(the base field that is used in [15] is C, in order to make the representation theory work) which ultimately
(see [15, Eq. (1)]) leads to the bound
ω(h2i, hGiC ) ωM (hGiC , ha, b, ci)
1
≥ω (5.17)
3 log2 (abc)
where ≥M and ωM are the monomial restriction and monomial relative exponent defined in Section 2.4.
Now the monomial irreversibility barrier from Section 3.3 comes into play. Upper bounds on the
monomial asymptotic subrank of hGiF have (using different terminology) been obtained in [8, 9, 26].
Those upper bounds imply that hGiF is monomially irreversible for every nontrivial finite group G.
Together with our results in Section 3.3 and the fact that the tensor hGiF is cyclically symmetric up to a
permutation of the basis of one of the tensor legs, this directly leads to nontrivial barriers for the left-hand
side of (5.17) for any fixed nontrivial group G, thus putting the methods of [8, 9, 26] in a broader context.
We have not tried to numerically optimize the monomial irreversibility barriers for group algebras. We
gave an example of a monomial barrier for G = Z/3Z in Example 2.11.
It should be stressed again that although these results rule out using monomial restrictions from
powers of any one single group, part of the hope of the group-theoretic approach is to use a family of
groups (such as the symmetric group Sn for increasing n) which is not just powers of a single starting
group. For families of abelian groups of bounded exponent (even if they are not powers of a single
group), [8] rules out STPP constructions reaching ω = 2, and for certain families of nilpotent groups
(again, even if they are not just powers of a single group) [9] does similarly.
The results of [8], [9] and [26], in fact, show slightly more than the aforementioned barriers for
monomial restriction. While, over arbitrary fields, they only rule out monomial restrictions, over fields of
bad characteristic (e. g., characteristic p when G is a p-group satisfying the relevant conditions of their
theorems) they also rule out arbitrary degenerations. This is because they show slice rank upper bounds,
the slice rank of a diagonal tensor equals its rank, and having slice rank at most r is a Zariski-closed
condition (proved in [34]).
Finally, we mention that the irreversibility barrier (rather than the monomial irreversibility bar-
rier) does not rule out obtaining ω = 2 via hGiC . Namely, hGiC is isomorphic to a direct sum of
matrix multiplication tensors, hGiC ∼ = i hdi , di , di i and, therefore, the irreversibility satisfies i(hGiC ) =
L
(log2 ∑i diω )/(log2 ∑i di2 ). Thus, if ω = 2, then hGiC is reversible.
T HEORY OF C OMPUTING, Volume 17 (2), 2021, pp. 1–32 25
M ATTHIAS C HRISTANDL , P ÉTER V RANA , AND J EROEN Z UIDDAM
6 Outlook for further barriers
In Section 5 we used the support functionals of Section 4 to upper bound the asymptotic subrank and thus
lower bound the irreversibility of intermediate tensors. There are two other approaches to do this that we
will discuss now. These approaches are at least as powerful as the support functionals for upper bounding
asymptotic subrank, and we expect that there are examples where they perform better.
6.1 The quantum functionals
For tensors over the complex numbers (i. e., when F = C) we have a much deeper understanding of
the theory of upper bounds on the asymptotic subrank. For any probability vector θ ∈ R3 the quantum
functional F θ introduced in [12], or rather its logarithm, is defined as
r
log2 F θ (t) = max ∑ θi H(Pi )
P∈Π(t) i=1
where Π(t) is the moment polytope of t. It is outside the scope of this paper to go into the definition of
the moment polytope. For that and a thorough discussion of all the connections to representation theory,
invariant theory and quantum information theory we refer to [12]. Here we will discuss the properties
of the quantum functionals that are important for upper bounding the asymptotic subrank. The first
crucial fact proven in [12] is that the quantum functionals are in the asymptotic spectrum of all complex
tensors ∆({tensors over C}), which we discussed in Section 4.1. We conclude that we can lower bound
irreversibility in terms of the flattening ranks and the quantum functionals as follows:
Proposition 6.1. Let t be a tensor over the complex numbers. Then
maxi log2 R(ti )
i(t) ≥ . (6.1)
minθ log2 F θ (t)
Comparing to Section 4.2, it is proved in [12] that the quantum functionals are at least as powerful
as the support functionals when it comes to upper bounding the asymptotic subrank. Namely, for any
tensor t over the complex numbers holds that F θ (t) ≤ ζ θ (t). It is an open problem whether this inequality
can be strict. We note that, as opposed to the support functionals, the quantum functionals are defined as
convex programs. It is an open problem whether the quantum functionals are efficiently computable.
6.2 Asymptotic slice rank
We finish Section 5 by discussing the asymptotic slice rank as a method to upper bound asymptotic
subrank, and the relations to the support functionals and the quantum functionals. The slice rank
(introduced by Tao [33] in the context of the cap set problem) of a tensor t is the smallest number r such
that t can be written as a sum of r slice rank one tensors. A slice rank one tensor is a tensor for which
there is an i ∈ [3] such that the flattening ti has matrix rank one. The asymptotic subrank, the slice rank
and the support functionals are related in the following way:
Q(t) ≤ lim sup slicerank(t ⊗n )1/n ≤ min ζ θ (t) . (6.2)
e n θ
T HEORY OF C OMPUTING, Volume 17 (2), 2021, pp. 1–32 26
BARRIERS FOR FAST M ATRIX M ULTIPLICATION FROM I RREVERSIBILITY
(See [12].) Thus, in an asymptotic fashion, the slice rank upper bounds the asymptotic subrank and
hence lower bounds irreducibility. Any analysis of lim supn slicerank(t ⊗n )1/n that we are aware of in the
literature boils down to evaluating minθ ζ θ (t). In particular, we are not aware of any example for which
the right-most inequality in (6.2) is strict.
In fact, for oblique4 tensors the right-most inequality is an equality [34] (see also [39, Section
4.6]) and, as mentioned in Section 4.2, for tight tensors both inequalities are equalities [31]. Over the
complex numbers, the quantum functionals play a special role in this comparison. As we mentioned in
Section 6.1, the quantum functionals satisfy F θ (t) ≤ ζ θ (t). It was shown in [12] that the minimum over
the parameter θ equals the asymptotic slice rank. We thus have
Q(t) ≤ lim sup slicerank(t ⊗n )1/n = min F θ (t) ≤ min ζ θ (t) . (6.3)
e n θ θ
For free5 tensors the right-most inequality in (6.3) is an equality [12].
A Code to verify the numerical examples
The following Mathematica code generates the barrier values in the tables in Section 1 to arbitrary
precision and for arbitrary parameters q and n.
A.1 Small Coppersmith–Winograd tensor cwq
In[1]:= Table[
2 Log2[q + 1]/(Log2[3] - 2/3 + (2/3) Log2[q]), {q, 2, 7}] // N
Out[1]= {2., 2.02538, 2.06244, 2.09627, 2.12549, 2.15064}
A.2 Big Coppersmith–Winograd tensor CWq
In[1]:= g[b_, q_] := -((2 b q Log[2 b])/
Log[2]) - ((1 - 3 b q) Log[1/3 (1 - 3 b q)])/(
3 Log[2]) + ((-b q - 2/3 (1 - 3 b q)) Log[b q + 2/3 (1 - 3 b q)])/
Log[2]
In[2]:= f[q_] :=
Piecewise[{{g[
q/(2 (-4 + q^2)) + 1/6 Sqrt[(32 + q^2)/(-4 + q^2)^2] /. {q -> 1},
1], q == 1}, {g[1/9, q],
q == 2}, {g[-((-3 q + Sqrt[32 + q^2])/(6 (-4 + q^2))), q],
q >= 3}}]
4 A tensor t ∈ Fn1 ⊗ Fn2 ⊗ Fn3 is called oblique if the support supp(t) ∈ [n ] × [n ] × [n ] in some basis is an antichain in the
1 2 3
product of the natural orders on the [ni ]. The matrix multiplication tensors ha, b, ci are examples of oblique tensors.
5 A tensor t is called free if in some basis any two different a, b ∈ supp(t) differ in at least two entries. Every tight tensor is
oblique and every oblique tensor is free.
T HEORY OF C OMPUTING, Volume 17 (2), 2021, pp. 1–32 27
M ATTHIAS C HRISTANDL , P ÉTER V RANA , AND J EROEN Z UIDDAM
In[3]:= Table[2 Log2[q + 2]/f[q], {q, 1, 6}] // N
Out[3]= {2.16805, 2.17795, 2.19146, 2.20551, 2.21913, 2.23201}
A.3 Reduced polynomial multiplication tn
In[1]:= g[n_] := g[n] = g /. FindRoot[1/(g-1)-n/(g^n-1)==(n-1)/3,{g,1+2/n}]
In[2]:= z[n_] := (g[n]^n - 1)/(g[n] - 1) g[n]^(-2 (n - 1)/3)
In[3]:= Table[2 Log2[n]/Log2[z[n]], {n, 2, 7}]
Out[3]= {2.17795, 2.16805, 2.15949, 2.15237, 2.14641, 2.14135}
References
[1] J OSH A LMAN: Limits on the universal method for matrix multiplication. Theory of Com-
puting, 17(1):1–30, 2021. Preliminary version in CCC’19. [doi:10.4086/toc.2021.v017a001,
arXiv:1812.08731] 3, 5
[2] J OSH A LMAN AND V IRGINIA VASSILEVSKA W ILLIAMS: Further limitations of the known
approaches for matrix multiplication. In Proc. 9th Innovations in Theoret. Comp. Sci.
conf. (ITCS’18), pp. 25:1–15. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2018.
[doi:10.4230/LIPIcs.ITCS.2018.25] 2
[3] J OSH A LMAN AND V IRGINIA VASSILEVSKA W ILLIAMS: Limits on all known (and some un-
known) approaches to matrix multiplication. In Proc. 59th FOCS, pp. 580–591. IEEE Comp. Soc.,
2018. [doi:10.1109/FOCS.2018.00061, arXiv:1810.08671] 2, 5
[4] A NDRIS A MBAINIS , Y UVAL F ILMUS , AND F RANÇOIS L E G ALL: Fast matrix multiplication:
limitations of the Coppersmith–Winograd method (extended abstract). In Proc. 47th STOC, pp.
585–593. ACM Press, 2015. [doi:10.1145/2746539.2746554] 2, 5
[5] F ELIX A. B EHREND: On sets of integers which contain no three terms in arithmetical progression.
Proc. Nat. Acad. Sci. USA, 32(12):331–332, 1946. [doi:10.1073/pnas.32.12.331] 8
[6] C HARLES H. B ENNETT, S ANDU P OPESCU , DANIEL ROHRLICH , J OHN A. S MOLIN , AND
A SHISH V. T HAPLIYAL: Exact and asymptotic measures of multipartite pure-state entanglement.
Phys. Rev. A (3), 63(1):012307, 2000. [doi:10.1103/PhysRevA.63.012307] 5
[7] M ARKUS B LÄSER: Fast Matrix Multiplication. Number 5 in Graduate Surveys. Theory of Comput-
ing Library, 2013. [doi:10.4086/toc.gs.2013.005] 5, 7, 22
T HEORY OF C OMPUTING, Volume 17 (2), 2021, pp. 1–32 28
BARRIERS FOR FAST M ATRIX M ULTIPLICATION FROM I RREVERSIBILITY
[8] J ONAH B LASIAK , T HOMAS C HURCH , H ENRY C OHN , J OSHUA A. G ROCHOW, E RIC NASLUND ,
W ILLIAM F. S AWIN , AND C HRIS U MANS: On cap sets and the group-theoretic approach to matrix
multiplication. Discrete Analysis, 3:1–27, 2017. [doi:10.19086/da.1245, arXiv:1605.06702] 2, 5,
12, 24, 25
[9] J ONAH B LASIAK , T HOMAS C HURCH , H ENRY C OHN , J OSHUA A. G ROCHOW, AND C HRIS
U MANS: Which groups are amenable to proving exponent two for matrix multiplication?, 2017.
[arXiv:1712.02302] 2, 5, 25
[10] P ETER B ÜRGISSER , M ICHAEL C LAUSEN , AND M. A MIN S HOKROLLAHI: Algebraic Complexity
Theory. Volume 315 of Grundlehren der Math. Wiss. Springer, 1997. [doi:10.1007/978-3-662-
03338-8] 5, 13
[11] M ATTHIAS C HRISTANDL , F RANÇOIS L E G ALL , V LADIMIR LYSIKOV, AND J EROEN Z UIDDAM:
Barriers for rectangular matrix multiplication, 2020. [arXiv:2003.03019] 5
[12] M ATTHIAS C HRISTANDL , P ÉTER V RANA , AND J EROEN Z UIDDAM: Universal points in
the asymptotic spectrum of tensors. In Proc. 50th STOC, pp. 289–296. ACM Press, 2018.
[doi:10.1145/3188745.3188766, arXiv:1709.07851] 3, 4, 12, 21, 26, 27
[13] M ATTHIAS C HRISTANDL , P ÉTER V RANA , AND J EROEN Z UIDDAM: Asymptotic tensor rank
of graph tensors: Beyond matrix multiplication. Comput. Complexity, 28(1):57–111, 2019.
[doi:10.1007/s00037-018-0172-8, arXiv:1609.07476] 9
[14] M ATTHIAS C HRISTANDL , P ÉTER V RANA , AND J EROEN Z UIDDAM: Barriers for fast matrix
multiplication from irreversibility. In Proc. 34th Comput. Complexity Conf. (CCC’19), pp. 26:1–17.
Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2019. [doi:10.4230/LIPIcs.CCC.2019.26] 1
[15] H ENRY C OHN AND C HRISTOPHER U MANS: A group-theoretic approach to fast matrix multiplica-
tion. In Proc. 44th FOCS, pp. 438–449. IEEE Comp. Soc., 2003. [doi:10.1109/SFCS.2003.1238217]
2, 25
[16] H ENRY C OHN AND C HRISTOPHER U MANS: Fast matrix multiplication using coherent configura-
tions. In Proc. 24th Ann. ACM–SIAM Symp. on Discrete Algorithms (SODA’13), pp. 1074–1086.
SIAM, 2013. ACM DL. 2
[17] D ON C OPPERSMITH AND S HMUEL W INOGRAD: Matrix multiplication via arithmetic progressions.
J. Symbolic Comput., 9(3):251–280, 1990. [doi:10.1016/S0747-7171(08)80013-2] 2, 4, 21, 22, 23
[18] W OLFGANG D ÜR , G UIVRE V IDAL , AND J UAN I GNACIO C IRAC: Three qubits can
be entangled in two inequivalent ways. Phys. Rev. A (3), 62(6):062314, 12, 2000.
[doi:10.1103/PhysRevA.62.062314] 5
[19] J ORDAN S. E LLENBERG AND D ION G IJSWIJT: On large subsets of Fnq with no three-term arithmetic
progression. Ann. Math., 185(1):339–343, 2017. [doi:10.4007/annals.2017.185.1.8] 12
T HEORY OF C OMPUTING, Volume 17 (2), 2021, pp. 1–32 29
M ATTHIAS C HRISTANDL , P ÉTER V RANA , AND J EROEN Z UIDDAM
[20] RYSZARD H ORODECKI , PAWEŁ H ORODECKI , M ICHAŁ H ORODECKI , AND K AROL
H ORODECKI: Quantum entanglement. Rev. Modern Physics, 81(2):865–942, 2009.
[doi:10.1103/RevModPhys.81.865] 5
[21] S WASTIK KOPPARTY, G UY M OSHKOVITZ , AND J EROEN Z UIDDAM: Geometric rank of tensors
and subrank of matrix multiplication. In Proc. 35th Comput. Complexity Conf. (CCC’20), pp. 35:1–
19. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2020. [doi:10.4230/LIPIcs.CCC.2020.35,
arXiv:2002.09472] 8
[22] J OSEPH M. L ANDSBERG AND M ATEUSZ M ICHAŁEK: Abelian tensors. J. Math. Pures Appliquées,
108(3):333–371, 2017. [doi:10.1016/j.matpur.2016.11.004, arXiv:1504.03732] 13
[23] F RANÇOIS L E G ALL: Powers of tensors and fast matrix multiplication. In Proc. 39th Inter-
nat. Symp. Symbolic and Algebraic Computation (ISSAC’14), pp. 296–303. ACM Press, 2014.
[doi:10.1145/2608628.2608664] 2
[24] G EORGE P ÓLYA AND G ABOR S ZEG Ő: Problems and Theorems in Analysis I. Classics in Math.
Springer, 1924/1972/1998. [doi:10.1007/978-3-642-61983-0] 6
[25] R APHAËL S ALEM AND D ONALD C LAYTON S PENCER: On sets of integers which contain no
three terms in arithmetical progression. Proc. Nat. Acad. Sci. USA, 28(12):561–563, 1942.
[doi:10.1073/pnas.28.12.561] 8
[26] W ILL S AWIN: Bounds for matchings in nonabelian groups. Electr. J. Combinat., 25(4), 2018.
[doi:10.37236/7520, arXiv:1702.00905] 25
[27] A NDREW JAMES S TOTHERS: On the complexity of matrix multiplication. Ph. D. thesis, Univ.
Edinburgh, 2010. era-handle. 2
[28] VOLKER S TRASSEN: Gaussian elimination is not optimal. Numerische Mathematik, 13(4):354–356,
1969. [doi:10.1007/BF02165411] 2
[29] VOLKER S TRASSEN: Relative bilinear complexity and matrix multiplication. J. reine angew. Math.,
375/376:406–443, 1987. [doi:10.1515/crll.1987.375-376.406] 3, 10, 11
[30] VOLKER S TRASSEN: The asymptotic spectrum of tensors. J. reine angew. Math., 384:102–152,
1988. [doi:10.1515/crll.1988.384.102] 3, 7, 8, 12, 13, 15, 18
[31] VOLKER S TRASSEN: Degeneration and complexity of bilinear maps: Some asymptotic spectra. J.
reine angew. Math., 413:127–180, 1991. [doi:10.1515/crll.1991.413.127] 3, 4, 10, 12, 19, 20, 21,
24, 27
[32] VOLKER S TRASSEN: Algebra and complexity. In First Eur. Congr. Math., Vol. II, volume 120 of
Progress Math., pp. 429–446. Birkhäuser, 1994. [doi:10.1007/978-3-0348-9112-7_18] 13
[33] T ERENCE TAO: A symmetric formulation of the Croot–Lev–Pach–Ellenberg–Gijswijt capset bound,
2016. LINK at terrytao.wordpress.com. 12, 26
T HEORY OF C OMPUTING, Volume 17 (2), 2021, pp. 1–32 30
BARRIERS FOR FAST M ATRIX M ULTIPLICATION FROM I RREVERSIBILITY
[34] T ERENCE TAO AND W ILL S AWIN: Notes on the “slice rank” of tensors, 2016. LINK at terry-
tao.wordpress.com. 25, 27
[35] V IRGINIA VASSILEVSKA W ILLIAMS: Multiplying matrices faster than Coppersmith–
Winograd. Extended abstract. In Proc. 44th STOC, pp. 887–898. ACM Press, 2012.
[doi:10.1145/2213977.2214056] 2
[36] F RANK V ERSTRAETE , J EROEN D EHAENE , BART L. R. D E M OOR , AND H ENRI V ERSCHELDE:
Four qubits can be entangled in nine different ways. Phys. Rev. A (3), 65(5):052112, 5, 2002.
[doi:10.1103/PhysRevA.65.052112] 5
[37] P ÉTER V RANA AND M ATTHIAS C HRISTANDL: Asymptotic entanglement transformation between
W and GHZ states. J. Math. Phys., 56(2):022204, 12, 2015. [doi:10.1063/1.4908106] 9
[38] N ENGKUN Y U , C HENG G UO , AND RUNYAO D UAN: Obtaining a W state from a Greenberger–
Horne–Zeilinger state via stochastic local operations and classical communication with a rate
approaching unity. Phys. Rev. Lett., 112(16):160401, 2014. [doi:10.1103/PhysRevLett.112.160401]
9
[39] J EROEN Z UIDDAM: Algebraic complexity, asymptotic spectra and entanglement polytopes. Ph. D.
thesis, Univ. Amsterdam, 2018. UvA-DARE. 27
AUTHORS
Matthias Christandl
Professor
Department of Mathematical Sciences
University of Copenhagen
Copenhagen, Denmark
christandl math ku dk
Péter Vrana
Associate professor
Department of Geometry
Budapest University of Technology and Economics
Budapest, Hungary
MTA-BME Lendület Quantum Information Theory Research Group
vranap math bme hu
http://math.bme.hu/~vranap/
T HEORY OF C OMPUTING, Volume 17 (2), 2021, pp. 1–32 31
M ATTHIAS C HRISTANDL , P ÉTER V RANA , AND J EROEN Z UIDDAM
Jeroen Zuiddam
Assistant professor
Korteweg–de Vries Institute for Mathematics
University of Amsterdam
Amsterdam, Netherlands
j.zuiddam uva nl
https://staff.fnwi.uva.nl/j.zuiddam/
ABOUT THE AUTHORS
M ATTHIAS C HRISTANDL is a professor at the Department of Mathematical Sciences at the
University of Copenhagen in Denmark. He received his Ph. D. from the University of
Cambridge in 2006. Prior to joining Copenhagen in 2014 he was an assistant professor
at ETH Zurich. His research interests are in quantum information theory, quantum
computation and algebraic complexity theory.
P ÉTER V RANA received his Ph. D. in 2011 from the Doctoral School of Physical Sciences,
Budapest University of Technology and Economics, under the supervision of Péter Lévay.
His main research interest is in quantum information theory. Péter lives in Budapest,
Hungary, where he has been a faculty member of the BUTE Institute of Mathematics
since 2014.
J EROEN Z UIDDAM received his Ph. D. from the University of Amsterdam in 2018, under
the supervision of Harry Buhrman and Matthias Christandl. During that time he was a
member of the Centrum Wiskunde & Informatica and the Institute for Logic, Language
and Computation. From 2018 to 2020, Jeroen was a member of the Institute for Advanced
Study in Princeton, where he worked with Avi Wigderson. From 2020 to 2021, Jeroen
was a Simons Junior Fellow at the Courant Institute of Mathematical Sciences of New
York University, hosted by Oded Regev. He is currently an assistant professor at the
Korteweg–de Vries Institute for Mathematics at the University of Amsterdam. His
research ranges over several areas of computer science and mathematics, including
algebraic complexity theory, quantum information theory and discrete mathematics.
T HEORY OF C OMPUTING, Volume 17 (2), 2021, pp. 1–32 32