TENSOR NETWORK COMPLEXITY OF MULTILINEAR MAPS

PER AUSTRIN

arXiv:1712.09630v1 [cs.CC] 27 Dec 2017

School of Computer Science and Communication
KTH Royal Institute of Technology

PETTERI KASKI
Department of Computer Science
Aalto University

KAIE KUBJAS
Laboratory for Information & Decision Systems
Massachusetts Institute of Technology
and
Laboratoire d’Informatique
Université Pierre et Marie Curie
Abstract. We study tensor networks as a model of arithmetic computation for evaluating multilinear maps. This model turns out to be strong enough to capture the current best algorithms for
a variety of problems, e.g., O(nω+ ) time matrix multiplication, O(n log n) time discrete Fourier
transform, O(n(ω+)t+j ) time (3t+j)-clique counting and O∗ (2n ) time for computing the permanent
of a matrix.
While powerful, the model still has limitations, and we are able to show a number of unconditional
lower bounds for various linear maps, including:
(a) an Ω(nd2v/3e ) time lower bound for v-clique, matching the upper bound if ω = 2.
(b) an Ω(20.918n ) time lower bound for the permanent of an n
P× n matrix.
(c) an Ω(n4 ) time lower bound for the trilinear map Dijk = l Aijl Bikl Cjkl generalizing matrix
multiplication, taking three n × n × n tensors A, B, C and producing an n × n × n tensor D,
ruling out tensor networks as an approach to obtaining non-trivial algorithms for hyperclique
counting and the Max-3-CSP problem.

1

1. Introduction
One of the cornerstones of the theory of computation is the study of efficient algorithms:
For a function f , how much time is required to evaluate f on given inputs?
Answering this question for almost any specific f is well beyond reach of contemporary tools.
For example, it is theoretically possible that canonical NP-complete problems, such as the Circuit
Satisfiability problem, can be solved in linear time whereas they are widely believed to require
super-polynomial (or somewhat less widely, exponential) time [41, 45, 46]. The main reason for
this barrier to quantitative understanding is that it is very hard to prove lower bounds for explicit
functions in general models of computation such as circuits or Turing machines.
This situation withstanding, a more modest program to advance our understanding of computation is to study restricted models of computation that for many f of interest are simultaneously
(i) general enough to capture the fastest-known algorithms for f , and
(ii) restricted enough to admit proofs of strong unconditional time lower bounds for f .
There is a substantial body of existing work that fits under this program, ranging from the study
of low-depth or otherwise restricted circuits (see e.g. [7], Ch. 14) to models of algorithm-design
principles such as greedy algorithms, backtracking, or dynamic programming [3, 37], to linear or
semidefinite programming relaxations for hard combinatorial optimization problems [64].
1.1. Multilinear maps. One class of functions f that are of substantial importance is the family of `-linear maps (multilinear maps) from ` input vector spaces to an output vector space.1
Examples range from maps of known near-linear-time complexity in the input size, such as the
discrete Fourier transform [32, 85], to maps without known polynomial-time-complexity algorithms,
such as the permanent of a matrix [77, 83]. Beyond motivation in numerical multilinear algebra
and its applications, recent advances in the study of fine-grained algorithm design and complexity
have highlighted the fundamental role of algebraic methods in the fastest-known algorithm designs
across a broad range of tasks from graph problems, such as all-pairs shortest paths and k-clique,
to parsing and constraint satisfaction problems, such as maximum satisfiability and graph coloring [2, 15, 17, 38, 47, 65, 89, 90].
In this paper, we study the arithmetic complexity of evaluating a multilinear map, that is, the
number of operations (scalar additions, subtractions, and multiplications) needed to evaluate the
map. To set up a baseline, a generic `-linear map from ` vector spaces of dimension n to a scalar
requires Ω(n` ) scalars to represent the map directly using combinations of basis vectors. Given
this complexity of a direct explicit representation, it is a fundamental problem to seek less costly
representations, along with associated efficient algorithms that work on the chosen representation.
We propose the systematic study of tensor networks as a framework for fast evaluation of multilinear maps, and show a number of upper and lower bounds on the computational power of tensor
networks in the spirit of (i) and (ii) above.
1.2. Tensor networks. Tensor networks have a long and rich history which can be traced as far
back as 19th -century studies in invariant theory due to Cayley [24, 25], Clebsch [28], Clifford [29],
Sylvester [82], and Kempe [50, 51]. Tensor networks are extensively deployed in applications from
pure mathematics and theoretical physics [49, 57, 59, 60, 69, 70, 74, 78] to computational physics and
chemistry [67, 72, 80]. In theoretical computer science, they appear in various guises including, for
example, in the Holant framework [84, 22, 21], in the study of probabilistic graphical models [55, 75],
in the study of parallel programming [79], in the study of quantum computing [6], and in the study
of arithmetic complexity [9, 23, 36]. (See §1.5 for a detailed discussion.) As the precise definitions
are rather technical, let us start with a few simple motivating examples and then state our results,
with the understanding that precise definitions appear in §4.
1Multilinear maps with ` = 1 are called linear, ` = 2 bilinear, ` = 3 trilinear, and so forth.

2

As a simple warm-up, consider the operation of multiplying
P an n × n matrix A by an n × 1
vector x, that is, computing for each i = 1, 2, . . . , n the scalar nj=1 Aij xj . We may represent this
computation with the network on the left in (1), where A and x form the vertices (or tensors) in
the network. We execute this network by contracting a subset of vertices in the network. The edges
(or modes) contained entirely inside the contracted set are summed over, leading to a new network
with a single node containing the product Ax. This contraction takes O(n2 ) operations because for
all n values of the boundary mode i we perform an inner product of two vectors of length n.
i

(1)

A

j

i

x

Ax

O(n2 ) operations

[contract]

Suppose now that A has low rank so that it can be written as A = P Q where P is an n × r matrix
and Q is an r × n matrix with r  n. We may represent this as the network to the left in (2), which
may be executed by a sequence of two contractions, each taking time O(nr).
i

(2)

k

P

Q

j

i

x

[contract]

O(nr) operations

P

i P Qx

k Qx

[contract]

O(nr) operations

Beyond simple low-rank compositions, many maps of substantial importance have a layered structure
that decomposes the map to a sequence of elementary maps. A canonical example is the discrete
Fourier transform (DFT), which for a smooth composite order such as 2k , can be decomposed into
a fast Fourier transform (FFT) that consists of a sequence of k transforms of order 2 interleaved
with diagonal-matrix multiplications of twiddle factors [32, 85]. Below in (3) we draw the network
topology for an FFT with k = 5. In our drawings of tensor networks,
(a) each tensor is drawn as a (white) box, and
(b) each mode is drawn as a tree that branches with solid black vertices.2
(3)

(butterfly)

(twiddle)

(butterfly)

(twiddle)

(butterfly)

(twiddle)

(butterfly)

(twiddle)

(4)

(butterfly)

When (3) is joined with an input tensor on the right, the execution of the network by consecutive
contractions captures exactly the standard circuit structure of the FFT in O(2k k) operations:

Rather than presenting an execution as a detailed sequence of diagrams with highlighted contractions
such as (4), without losing optimality we may present an execution as a rooted binary tree whose
leaves are the tensors in a diagram. For example, the red tree overlayed on top of the diagram
2Such a tree simply represents modes that are incident with more than two tensors.

3

below represents precisely the execution (4), where each internal node in the tree corresponds to a
contraction in (4).

(5)

These examples of linear maps together with their networks and executions merely constitute a
warm-up to the expressive power of tensor networks. In § 5, we give a number of more intricate
networks towards our main results collected in Theorem
1.1; see, for example, (46) on page 23 for

an illustration of a network for evaluating an 82 -linear map for counting 8-cliques in a graph.
1.3. Our results. Starting with motivation (i) and seeking to express existing fastest-known algorithms as executions of tensor networks by a sequence of contractions, we show upper bounds
for a number of natural problems. Beyond standard linear settings such as the FFT, not only do
tensor networks realize classical bilinear settings such as Abelian group algebra products and fast
matrix multiplication algorithms based on low tensor rank, they are a powerful enough to capture
a substantial number of higher-linearity applications, including Ryser’s algorithm for matrix permanent [77], the currently fastest known algorithms for the k-clique problem for k ≥ 4 [38, 65],
which cannot be captured with tools based on tensor rank alone (cf. § 1.4), and the Kruskal operator [53, 56] (cf. § 3.5), which underlies realization of rank-decompositions for tensor rank [54]
and current fastest algorithms for detecting outlier correlations [48]. Further applications captured
by tensor networks are the set covering and set partitioning frameworks via fast zeta and Möbius
transforms that underlie the current fastest algorithms for graph coloring [17] and its generalizations
such as computing the Tutte polynomial [14, 15].
To state a compendium theorem for our upper bound results, let us write ω = ω(F) for the
infimum over all e such that the arithmetic complexity of multiplying two n × n matrices is O(ne ).
While the value of ω may depend on the underlying field F, we tacitly ignore this, since the field
is fixed throughout the paper. For all fields it is known that 2 ≤ ω < 2.3728639 [62, 86]. For the
detailed definitions of the relevant multilinear maps, cf. §3 and §5.
Theorem 1.1. We have the following upper bounds on arithmetic complexity via tensor networks:
(1) O(2k k) for the discrete Fourier transforms for the Abelian groups Z2k and Zk2 .
(2) O(nω+ ) for the matrix multiplication map of two n × n matrices.
(3) O(max(nd`/2e(ω+−1) r, n2d`/2e rω+−2 )) for the Kruskal operator of ` matrices of shape n × r.
(4) O(n(ω+)bv/3c+(v mod 3) ) for counting v-cliques in an n-vertex graph.
(5) O(2k k) for group algebra products on F[Z2k ] and F[Zk2 ] when 2 is unit in F.
(6) O(2k k) for the semigroup algebra product on F[({0, 1}k , ⊆, ∩, ∪)].
(7) O(2n n) for the permanent of an n × n matrix.
Above  > 0 is an arbitrary constant.
Perhaps the most interesting application above is the v-clique problem, which suggests that one
v
should seek to pursue generalizations, in particular to v-vertex
 hypercliques of k hyperedges with
v
v > k ≥ 3, a task that can be algebrized via the study of a k -linear form (cf. §3.6). Indeed, subgraph
counting is a problem that has received substantial interest over the years (e.g. [47, 65, 5, 4, 38,
16, 18, 91, 87, 40, 39, 66, 52, 33]), but progress in the particular case of v-clique has been stuck
to the extent that the problem has attracted notoriety as a hardness assumption in fine-grained
complexity [1, 2]. Beyond the study of cliques, hypercliques, and subgraph counting, nontrivial
algorithms for such forms would have immediate applicability, for example, in the study of maximum

4

constraint satisfaction problems (Max-CSP) for constraints of width k ≥ 3; cf. Williams [89] for the
case k = 2. One of the main goals of our subsequent lower bounds is to rule out tensor networks as
a candidate to yield improved algorithms in this setting.
Turning from upper bounds to lower bounds and motivation (ii), tensor networks are restricted
enough to enable nontrivial lower bounds for many multilinear maps. To begin with, an immediate
and well-known limitation of tensor networks is that all the intermediate results during the execution
of a network are multilinear, and the execution of a network can be simulated by a multilinear circuit.
Raz [73] shows that multilinear formulas cannot compute the determinant of an n × n matrix in a
polynomial number of operations in n, even though polynomial-size general circuits are known for
the determinant (cf. [11, 19, 76]).
It turns out that considerably stronger lower bounds can be shown for tensor networks. In particular, we establish essentially tight lower bounds (subject
 to the assumption ω = 2) for arithmetic
complexity via tensor networks in cases such as the v2 -linear form for v-cliques, and the Kruskal
operator. Furthermore, we rule out the possibility of any nontrivial algorithm designs via tensor
networks for the higher kv -linear forms with v > k ≥ 3. The following theorem collects our main
lower-bound results, and should be contrasted with the upper bounds in Theorem 1.1.
Theorem 1.2. We have the following lower bounds on arithmetic complexity via tensor networks:

(1) Ω(nv ) for the kv -linear form when v > k ≥ 3.

(2) Ω(nd2v/3e ) for the v-clique-counting v2 -linear form.
` dl/2e r)) for the Kruskal operator of ` matrices of shape n × r.
(3) Ω(max(n
 ,n
n
(4) Ω( n/3 ) for the determinant or permanent of an n × n matrix.

n
One may wonder about the gap between the bounds of Ω( n/3
) and O(2n n) for the permanent.
As we
 explain below, our lower bound methods are inherently rank-based and can not go beyond
n
n/3 . Turning this on its head, given the apparent power of tensor networks, the prospect of a
(2 − Ω(1))n -time tensor-network algorithm for the permanent is tantalizing.
1.4. Overview of proof ideas. As a running example in this overview, we consider the 6-linear
form A : F[n]×[n] × F[n]×[n] × . . . × F[n]×[n] → F taking as input 6 matrices of size n × n, defined by
X
(1) (2) (3) (4) (5) (6)
(6)
A(X (1) , X (2) , X (3) , X (4) , X (5) , X (6) ) =
Xij Xik Xi` Xjk Xj` Xk` .
i,j,k,`∈[n]

If χ is the adjacency matrix of a loopless graph G, then A(χ, χ, χ, χ, χ, χ) counts the number of
4-cliques in the graph. Associated with A is the 6-tensor T (A) of size n2 × n2 × · · · × n2 , where
each of the 6 modes is indexed by a pair (i, j) ∈ [n] × [n], and the value at a given position is the
coefficient of the corresponding term in A. Concretely,
(
1 if i1 = i2 = i3 , j1 = j4 = j5 , k2 = k4 = k6 and `3 = `5 = `6 ;
T (A)i1 j1 ,i2 k2 ,i3 `3 ,j4 k4 ,j5 `5 ,k6 `6 =
0 otherwise.
Upper bounds. Most, but not all, of the families of multilinear maps we consider are closed under
taking Kronecker products. For instance, consider the 4-clique counting form (6) for an n-vertex
graph and its associated tensor T (A). Then for any k ≥ 1, the tensor associated with the 4-clique
counting form in nk -vertex graphs is T (A)⊗k , the k-fold Kronecker product of T (A) with itself. We
write A⊗k for the associated map. With this in mind, it is natural to seek general constructions
that, given an efficient evaluation of some map A, yields an efficient evaluation of A⊗k .
We give such a construction, and show that the cost of the best tensor network execution for A⊗k
is essentially submultiplicative in a quantity that we call the amortized cost of an execution. For
tensors of order at most 3, the notion of amortized cost essentially captures the rank of T (A), but
for higher-order tensors, the amortized cost may be significantly smaller than the rank. Roughly

5

speaking, the amortized cost of a step in an execution of a map A is: (i) equal to the normal cost
if the operation involves the contraction of two tensors that both depend on some input variables
of A, but (ii) equal to the size of the result if only one of the tensors involved in the contraction
depends on the input variables of A. A precise definition appears in §5.2. Our general upper bound
for the cost of A⊗k can, somewhat informally, be stated as follows.
Theorem 1.3 (Submultiplicativity of cost, informal statement). If a multilinear map A has a tensor
network execution consisting of s steps, each with cost at most c and amortized cost at most a, then
A⊗k has a tensor network execution consisting of at most k · s steps, each with cost at most ak−1 · c.

An immediate corollary of this is that we can capture any algorithm for A⊗k based on a low-rank
decomposition of T (A) (Corollary 5.5). For example, this implies that tensor networks can multiply
n × n matrices in O(nω+ ) time (§5.4).
However, returning to our running example form (6), as we explain below the tensor T (A) has
rank n4 , meaning that Corollary 5.5 only yields a trivial upper bound. This is where the full
generality of Theorem 1.3 comes in. Consider the form (6) for graphs on some constant number
n0 of vertices. As it turns out, we can design a network and an associated execution for this form,
depicted in (7) and explained in more detail in the proof of Lemma 5.9, with an execution of cost
e
and amortized cost ne+1
n2e+3
0 , where n0 is the rank of the tensor associated with n0 × n0 matrix
0
multiplication. Picking n0 to be a large enough constant so that e is approximately ω, and letting
k be such that n is approximately nk0 , we obtain via Theorem 1.3 an O(nω++1 ) time upper bound
for (6).
ij

il

ik

kl

jk

jl

ij

il

ik

kl

jk

jl

X (1)

X (2)

X (3)

X (4)

X (5)

X (6)

X (1)

X (2)

X (3)

X (4)

X (5)

X (6)

(7)

Lower bounds. Just like many other arithmetic complexity lower bounds, our lower bounds boil
down to establishing lower bounds on the rank of certain matrices.
In order to establish a lower bound on the rank of T (A), we flatten it to a matrix and analyze the
rank of that matrix. There are 25 possible bipartitions of the 6 modes of T (A) into two non-empty
subsets, and the lower bound on the rank of T (A) that we obtain is the maximum of the ranks of
the resulting matrices. Using this method it is easy to establish that for our example form (6), the
rank of T (A) = n4 . That this is an upper bound follows from (6), and that it is a lower bound
follows by considering the bipartition taking variables X (1) and X (6) as row indices, and the other
4 variables as column indices. The resulting n4 × n8 matrix has full rank.
Tensor networks are more versatile and can be more efficient than low-rank decompositions of
T (A). Nevertheless, we show limitations on this versatility. In particular we show that every tensor
network execution for A induces a tree in which the leaves are the inputs of A and all internal nodes
have degree 3. We call this a socket tree. Each edge in a socket tree induces a bipartition of the
variables and our key technical lemma is to show that for each such bipartition, the rank of the
corresponding flattening of T (A) is a lower bound on the cost of the execution that gave rise to the
tree. Thus, to obtain a lower bound for the cost of a specific execution, we consider the maximum
rank obtained over all edges of the corresponding socket tree, and to lower bound the cost of every

6

tensor network execution, we minimize this quantity over all possible socket trees. We refer to the
resulting quantity as the socket width of A, denoted w(A) (formal definition appears in §6). Our
general lower bound can thus be phrased as follows, where c(A) denotes the minimum cost of a
tensor network for evaluating A (formal definition appears in §4.5).
Theorem 1.4. For every multilinear map A, it holds that c(A) ≥ w(A).

Indeed, for our running example (6), there are low-width socket trees establishing that w(A) ≤ n3 ,
see (8). However, that bound is tight: our Ω(nd2·4/3e ) = Ω(n3 ) lower bound for the 42 -linear form
(Theorem 1.2) is obtained by proving that w(A) ≥ n3 (Lemma 7.7) and appealing to Theorem 1.4.
ij

il

ik

kl

jk

jl

(8)
1.5. Earlier and related work. We now proceed to a more detailed discussion of earlier work.
Tensor networks. The history of tensor networks (or, alternatively, tensor diagrams or diagrams) as
an analytical and computational tool goes back to the 19th -century to the works by Cayley [24, 25],
Clebsch [28], Clifford [29], Sylvester [82], and Kempe [50, 51]. The diagrammatic form used here can
be traced back to Penrose [70]. Some early appearances of tensor diagrams are by Cvitanovic̀ [34],
Cvitanovic̀ and Kennedy [35], Kuperberg [57], and many others. Surveys of tensor diagrams can be
found in Penrose and Rindler [71] and Landsberg [59]. Schrijver [78] gives a brief historical account.
A principal deviation from Penrose’s notation that we make in this paper is to work subject to
a basis and a corresponding dual basis in each relevant vector space to avoid distinction between
primal and dual spaces. This in particular enables a concise treatment of hyperedges and saves us
from considering orientation of edges, or the planar layout of edges in a drawing. That is, we will
view a tensor network combinatorially as a hypergraph with tensors associated at the vertices, and
with a subset of the edges3 designated to form the boundary of the network (cf. §4 for the precise
definitions). A yet further conceptual difference is that we view the execution of a tensor network as
a sequence of contractions of sets of vertices (tensors) rather than as contractions of edges (modes).
This choice enables us to reduce the size of hyperedges gradually before eliminating them during an
execution, thus enabling better granularity. For simplicity, we will restrict to a purely multilinear
framework and will not consider sums of networks although such a study would be possible, and is
pursued e.g. in Penrose’s work [70].
A large body of existing work in applications (cf. §1.2) studies how to efficiently execute a given
tensor network D. Our quest in this paper differs from such studies in that we study a multilinear
map A, and seek to design the most efficient network D that realizes A, or to establish lower bounds
for best-possible designs. In particular, our upper and lower bounds in Theorem 1.1 and Theorem 1.2
are over all tensor networks that realize a particular map A of interest.
Computational problems on tensors and tensor networks. Problems on given tensors and tensor
networks are known to be mostly computationally hard as soon as the setting changes from matrices
to higher-order tensors. Håstad [42] showed that computing the rank of an explicitly given `-tensor is
NP-complete over finite fields and NP-hard over rationals whenever ` ≥ 3. Hillar and Lim extended
the latter result to any field containing Q [43]. They also showed that many other tensor problems
such as the eigenvalue, singular value and spectral norm decision and approximation problems as
well as rank-1 approximation problem for 3-tensors (over R and in some cases over C) are NP-hard.
The task of finding the value of a given scalar-valued tensor network is known to be #P-complete
(see e.g. [8, 12]). Similarly, it is NP-hard to find the most efficient sequence of contractions for a
given network [58, 72].
3We find it convenient to talk about edges (modes) with the understanding that hyperedges are tacitly meant.

7

Tensor networks in applications. Beyond our present use of tensor networks as a model of computation to efficiently evaluate multilinear maps, tensor networks are used across a broad range
of applications. Accordingly, the following should be viewed as mere pointers to further literature
on tensor networks, not as an exhaustive listing of all applications of tensor networks. Orus [67]
gives an introduction to tensor networks in the context of computational physics. Itai and Landau [6] study quantum computation and quantum algorithms for evaluating tensor networks [6].
Solomonik and Hoefler study sparse tensor algebra as a model for parallel programming [79]. The
Holant framework introduced by Valiant [84] and studied further by Cai et al. [22, 21] involves
the study of multilinear sum–product expressions that can be viewed as tensor networks. Tensor
networks appear naturally in the study of probabilistic graphical models [55, 75, 88], and in the
study of various machine-learning problems [26, 27].
Bilinear and multilinear complexity. As was concisely outlined in §1.4, for bilinear maps our present
work reduces to the study of tensor rank of 3-tensors and an extensive body of work on bilinear
complexity, with the arithmetic complexity of the matrix multiplication map as the primary driver.
For two starting points to this literature, we refer to the monograph by Bürgisser, Clausen, and
Shokrollahi [20] and to the survey by Pan [68]. Our present work can be seen as generalizing
this bilinear theory to higher orders of linearity via tensor networks and their executions. The
current state of the art for fast matrix multiplication can be found in Le Gall [61, 62], Le Gall
and Urrutia [63], Vassilevska Williams [86], Cohn and Umans [31], Cohn, Kleinberg, Szegedy, and
Umans [30], Benson and Ballard [10], and Huang, Rice, Matthews, and van de Geijn [44].
1.6. Organization of this paper. Section 2 recalls preliminaries on tensors and multilinear maps.
Section 3 reviews the specific multilinear maps that we study in this work and describes for each
map its associated tensor. In Section 4, tensor networks, execution and cost of a tensor network,
and cost of a multilinear map are defined. Section 5 presents tensor-network algorithms for the
multilinear maps introduced in Section 3. All the algorithms in this section have appeared in earlier
work but not necessarily in the tensor-network form. In Section 6, a general lower bound on the
cost of evaluating a multilinear map using tensor network is obtained. The lower bound is expressed
in terms of the socket-width of a multilinear map. In Section 7, lower bounds on socket-width for
concrete multilinear maps studied in Sections 3 and 5 are derived. Finally, Appendix A gives some
background results on minimum-cost executions.
2. Preliminaries
Throughout the paper [n] denotes {1, 2, . . . , n} and F denotes an arbitrary fixed field.
2.1. Tensors. This section sets up our notation for tensors and multilinear maps. We work with
tensors and multilinear maps relative to fixed bases for the respective vector spaces over F.
Modes, indexing, and positions. We will work with the following convention of positioning individual
entries inside a tensor. Let E be a finite set of modes. Associate with each mode e ∈ E a finite
nonempty index
Q set J(e). In this case we sayQthat E is a set of indexed modes. A position is an
element j ∈ e∈E J(e). Let us write J(E) = e∈E J(e) for the set of all positions with respect to
the indexed modes E. In the special case that the set of modes E is empty we define the set of
positions J(E) to consist of a single element.
Tensors, matrices, vectors, and scalars. Let E be a set of indexed modes. A tensor with respect to
E is a mapping T : J(E) → F. Equivalently, we write T ∈ FJ(E) to indicate that T is a tensor with
respect to the indexed modes E. We view the set FJ(E) of all tensors over E as a vector space over
F with addition and scalar multiplication of tensors defined entrywise. We say that |E| is the order
of the tensor. A tensor of order zero is called a scalar, a tensor of order one is called a vector, and a
tensor of order two is called a matrix. The volume of the tensor is |J(E)|. The tuple (|J(e)| : e ∈ E)

8

is the shape of the tensor. It is convenient to use the “×”-symbol to punctuate the shape of a tensor;
that is, instead of writing, say (2, 3, 4) for the shape, we write 2 × 3 × 4. For a position j ∈ J(E)
and a tensor T ∈ FJ(E) , we say that Tj ∈ F is the entry of T at j.
A flattening of T induced by a bipartition E1 ∪ E2 = E of the modes of T is a |J(E1 )| × |J(E2 )|
matrix M where, for j1 ∈ J(E1 ) and j2 ∈ J(E2 ) we have Mj1 ,j2 = Tj1 j2 . Given two order ` tensors
S ∈ F[n1 ]×[n2 ]×···×[n` ] and T ∈ F[m1 ]×[m2 ]×···×[m` ] , their Kronecker product S ⊗ T is a tensor in
F[n1 m1 ]×[n2 m2 ]×···×[n` m` ] defined by
(S ⊗ T )m1 (i1 −1)+j1 ,m2 (i2 −1)+j2 ,...,m` (i` −1)+j` = Si1 ,i2 ,...,i` Tj1 ,j2 ,...,j` .
2.2. Multilinear maps. Let E1 , E2 , . . . , E` , E 0 be pairwise disjoint sets of indexed modes such
0
that E1 , E2 , . . . , E` are nonempty. We say that a map A : FJ(E1 ) × FJ(E2 ) × · · · × FJ(E` ) → FJ(E ) is
an `-linear map if A is linear with respect to each of its ` inputs individually when the other inputs
remain fixed. In particular, a 1-linear map is a linear map. A multilinear map that gives a scalar
output is a multilinear form. In particular, A is a form if and only if E 0 is empty.
0

The tensors of a multilinear map. For an `-linear map A : FJ(E1 ) ×FJ(E2 ) ×· · ·×FJ(E` ) → FJ(E ) , we
define two slightly different tensors T (A) and T̂ (A). Both are indexed by J(E1 ∪ E2 ∪ . . . ∪ E` ∪ E 0 )
and at position j1 j2 . . . j` j 0 take the value

T (A)j1 j2 ...j` j 0 = T̂ (A)j1 j2 ...j` j 0 = A e(j1 ) , e(j2 ) , . . . , e(j` ) j 0 ,
where e(ji ) ∈ FJ(Ei ) denotes the tensor with a 1 in position ji and 0s in all other position. The
difference between T (A) and T̂ (A) is their shape. The shape of T (A) is |J(E1 )| × |J(E2 )| × · · · ×
|J(E` )| × |J(E 0 )|, except if A is a form in which case the |J(E 0 )| part is omitted. Thus T (A) is of
order ` + 1 (or ` if A is a form). The shape of T̂ (A) is (|J(e)| : e ∈ Ei , i ∈ [` + 1]), thus its order is
|E1 | + |E2 | + · · · + |E` | + |E 0 |.
In other words, each mode of T (A) corresponds to one of the inputs of A, or the output. These
inputs are in turn sets of indexed modes so may contain more “fine-grained” structure, but this
information is lost at the level of granularity of T (A). When working with tensor networks for
evaluating A, we need to keep track of the fine-grained mode structure because this is in many
cases what allows us to construct efficient algorithms, hence in most parts of the paper we are more
interested in the tensor T̂ (A) which contains this fine-grained structure.
On the other hand, T̂ (A) does not contain information about which modes are grouped together
to form the inputs and output of A, and this information is also important. This leads us to the
notion of sockets, defined next.
Sockets. Let us study the tensor T̂ (A) with respect to the map A. We say that the modes in
E1 ∪ E2 ∪ · · · ∪ E` are the input modes of T̂ (A), and the modes in E 0 are the output modes of
T̂ (A) with respect to A. Let us say that E1 , . . . , E` are the input sockets of T̂ (A) with respect to
A. Similarly, E 0 is the output socket in T̂ (A) with respect to A. In particular, the output socket is
empty if and only if A is a form. To describe a socketing of the modes of a tensor, it is convenient
to use parentheses to group a “×”-punctuated shape of a tensor into sockets, see also §2.1.
Let T̂ be a tensor over a set of indexed modes E. Any tuple E = (E1 , E2 , . . . , E` , E 0 ) of subsets of
E that partitions E with E1 , E2 , . . . , E` nonempty defines an `-linear map AE (T̂ ) : FJ(E1 ) × FJ(E2 ) ×
0
· · · × FJ(E` ) → FJ(E ) with T̂ (AE (T̂ )) = T̂ . In this case the tuple (E1 , E2 , . . . , E` ) gives the input
sockets of T and E 0 is the output socket of T̂ with respect to AE (T̂ ).
We thus conclude that two multilinear maps A1 , A2 may have the same base tensor T̂ (A1 ) =
T̂ (A2 ), and from a tensor T̂ one may obtain different multilinear maps by varying how the modes
of T̂ are assigned to input and output sockets.

9

The form of a multilinear map. Let A be a multilinear map with a nonempty output socket. We
can turn A into a multilinear form F (A) by turning its output socket into an input socket. Let us
say that F (A) is the multilinear form of A. We also set F (A) = A when A is a multilinear form.
3. Examples of multilinear maps
This section reviews the specific multilinear maps that we study in this work. Together with each
map we describe its associated tensor and a socketing of the tensor that realizes the map.
3.1. Discrete Fourier transform. Let n ≥ 2 be an integer and let ρ ∈ F be a primitive nth root
of unity in the field F.4 Define the n × n symmetric matrix Φ with entries Φi,j = ρ(i−1)(j−1) for all
i, j ∈ [n]. The discrete Fourier transform (DFT) of order n at ρ is the linear map L : F[n] → F[n]
defined for all x ∈ F[n] by the matrix-vector multiplication L(x) = Φx. In particular, the matrix Φ
is the tensor associated with L. The matrix Φ has two modes, namely its rows and columns. To
realize L, take the columns of Φ as the input socket, and the rows as the output socket.
3.2. Determinant and permanent. Let us write Sn for the symmetric group of all permutations
σ : [n] → [n]. Let c(σ) be the number of cycles in the cycle decomposition of σ, where each fixed
point of σ is counted as a cycle. Further standard examples of multilinear operators include the
determinant and permanent
Y
X Y
X
(9)
ai,σ(i) ,
(−1)n−c(σ)
ai,σ(i)
per A =
det A =
σ∈Sn

σ∈Sn i∈[n]

i∈[n]

both of which are n-linear in the n columns (or the n rows) of the matrix A = (aij )i,j∈[n] . The
determinant and permanent are associated with order n tensors T̂ (det) , T̂ (per) ∈ F[n]×[n]×···×[n] defined
for all j = (i1 , i2 , . . . , in ) ∈ [n] × [n] × · · · × [n] by
(10)

(det)
T̂j

(
(−1)n−c(j)
=
0

if j ∈ Sn
otherwise

(per)
T̂j

(
1 if j ∈ Sn
=
0 otherwise.

To realize the determinant and permanent using (10), we socket T̂ (det) and T̂ (per) with the rows
of A. The determinant and permanent tensors are not closed under taking Kronecker products,
because the Kronecker product of two tensors has the same order as its input tensors, but for each
n there is exactly one determinant (permanent) tensor of order n.
3.3. Matrix multiplication. Let n, r, and m be positive integers. Perhaps the most fundamental
example of a bilinear map is the map that multiplies an n × r matrix A = (Aij )i∈[n], j∈[r] with an
r × m matrix B = (Bij )i∈[r], j∈[m] to obtain the n × m product matrix C = (Cij )i∈[n] ,j∈[m] defined
for all i ∈ [n] and j ∈ [m] by
X
(11)
Cij =
Aik Bkj .
k∈[r]

It is natural to view the input A ∈ F[n]×[r] as a 2-tensor, and similarly so for the input B ∈
F[r]×[m] , and the output C ∈ F[n]×[m] . Thus, (11) is naturally associated with the 6-tensor T̂ ∈
F[n]×[r]×[r]×[m]×[n]×[m] with entries defined for all i1 , i2 ∈ [n], j1 , j2 ∈ [m], and k1 , k2 ∈ [r] by
(
1 if i1 = i2 and j1 = j2 and k1 = k2 ;
(12)
T̂i1k1k2 j1i2 j2 =
0 otherwise.
4That is, ρ satisfies ρn = 1 and ρn/k 6= 1 for all integer divisors k ≥ 2 of n.

10

To realize (11) using (12), we can use the socketing grouped by parentheses in ([n] × [r]) × ([r] ×
[m]) × ([n] × [m]), where the first two groups are the two input sockets corresponding to A and B,
and the last group is the output socket corresponding to C.
Let us write hn, r, mi as a shorthand for the tensor (12). From (12) and the definition of the
Kronecker product it is immediate that matrix-multiplication tensors satisfy
(13)

hn1 , r1 , m1 i ⊗ hn2 , r2 , m2 i = hn1 n2 , r1 r1 , m1 m2 i .

That is, matrix multiplication tensors are closed under taking Kronecker products.
3.4. Group algebra product. Let (A, +) be an Abelian group of order n. Another fundamental
example of a bilinear map is to convolve two vectors f ∈ FA and g ∈ FA according to the group
operation of A to obtain the vector h = f ∗ g ∈ FA , defined for all k ∈ A by
X
(14)
hk =
f(k−j) gj .
j∈A

The map (14) is associated with the 3-tensor T̂ ∈ FA×A×A defined for all i, j, k ∈ A by
(
1 i + j = k;
(15)
T̂ijk =
0 otherwise.
A socketing of the three modes of (15) that realizes (14) is to take the first two modes as two input
sockets corresponding to f and g, respectively, and to take the last mode as the output socket
corresponding to h. The vector space FA equipped with the convolution product ∗ is the group
algebra F[A].
3.5. Kruskal operator. Let n1 , n2 , . . . , n` and r be positive integers. Matrix multiplication generalizes naturally to the `-linear task of multiplying ` matrices A(1) ∈ F[n1 ]×[r] , A(2) ∈ F[n2 ]×[r] , . . .,
A(`) ∈ F[n` ]×[r] to obtain the order-` tensor Y ∈ F[n1 ]×[n2 ]×···×[n` ] defined for all (i1 , i2 , . . . , i` ) ∈
[n1 ] × [n2 ] × · · · × [n` ] by
X (1) (2)
(`)
(16)
Yi1 i2 ···i` =
Ai1 j Ai2 j · · · Ai` j .
j∈[r]

This operator is known as the Kruskal operator [56, 53]5 of the matrices A(1) , A(2) , . . . , A(`) .
The map (16) is associated with the 3`-tensor
T̂ ∈ F[n1 ]×[r]×[n2 ]×[r]×···×[n` ]×[r]×···×[n1 ]×[n2 ]×···×[n` ]

defined for all i1 , i01 ∈ [n1 ], i2 , i02 ∈ [n2 ], . . . i` , i0` ∈ [n` ] and j1 , j2 , . . . , j` ∈ [r] by
(
1 if i1 = i01 , i2 = i02 , . . ., i` = i0` and j1 = j2 = . . . = j` ;
(17)
T̂i1 j1 i2 j2 ···i` j` i01 i02 ···i0` =
0 otherwise.
A socketing of (17) that realizes (16) is to take each of the ` pairs of modes [n1 ] × [r], [n2 ] × [r], . . .,
[n` ] × [r] as an input socket and the final ` modes [n1 ] × [n2 ] × · · · × [n` ] as the output socket.
Let us write hn1 , n2 , . . . , n` |ri for the tensor (17). Analogously to the closure property (13) for
matrix multiplication tensors, we observe that
(18)

hn1 , n2 , . . . , n` |ri ⊗ hn01 , n02 , . . . , n0` |r0 i = hn1 n01 , n2 n02 , . . . , n` n0` |rr0 i .

That is, Kruskal operator tensors are closed under taking Kronecker products. Furthermore, we
observe that hn, r, mi = hn, m|ri. That is, the matrix multiplication tensor (12) is the special case
of the Kruskal operator tensor (17) when ` = 2.
5Kolda [53] calls this operator the Kruskal operator. Kruskal [56] studied the case ` = 3 in particular.

11

3.6. Binomial-linear forms. Further multilinear operators arise naturally by algebraization of
combinatorial problems. For example, the linear form of the matrix multiplication map
X
(19)
Aij Bjk Cki
i,j,k∈[n]

can be used to count the number of triangles in graph, and the form
X
Aij Bik Ci` Djk Ej` Fk`
(20)
i,j,k,`∈[n]

can be used to count the number of occurrences of any 4-vertex subgraph in a graph by varying
the six n × n matrices A, B, C, D, E, F ∈ F[n]×[n] . A more complicated variant takes as input four
3-tensors A, B, C, D ∈ F[n]×[n]×[n] of shape n × n × n and considers the linear form
X
Aijk Bik` Cij` Djk` .
(21)
i,j,k,`∈[n]

An n4−Ω(1) time algorithms for the associated trilinear map (A, B, C) 7→ D would imply an algorithm for the Max 3-Sat problem with running time (2 − Ω(1))n [89].
The forms (19), (20), and (21) are all special cases of what we call binomial-linear forms. Let

v ≥ k be positive integers and write [v]
k for the set of k-element subsets of [v]. Fix positive integers
(S) be an input tensor of shape [n ]×[n ]×· · ·×[n ].
n1 , . . . ,nv . For S = {i1 , i2 , . . . , ik } ∈ [v]
i1
i2
ik
k , let X
v
The k -linear form with index set sizes n1 , . . . , nv is the form
X
Y
(S)
Xσ|S ,
(22)
σ∈[n1 ]×[n2 ]×···×[nv ] S∈([v])
k

where
σ|S is the restriction of σ to the k indices in S. The matrix
multiplication form (19) is the


3
4
4
2 -linear form, (20) is the 2 -linear form, and (21) is the 3 -linear form.
The map (22) is associated with a tensor T̂ of order k · kv whose modes are E = { (S, i) | S ∈
[v]
k , i ∈ S } with index sets J((S, i)) = [ni ]. The entries of T̂ are defined by
(
1 if ∃σ ∈ [n1 ] × [n2 ] × · · · × [nv ] such that j(S,i) = σi for every (S, i) ∈ E;
(23)
T̂j =
0 otherwise.

A socketing of (23) that realizes (22) is given by one input socket for each S ∈ [v]
k such that the
socket contains the k modes (S, i) for i ∈ S.
Note that the tensors of the forms (20) and (21) are actually the same – they are both of order
12, have volume n12 , and are in fact equal to the outer product of the n × n × n identity tensor
with itself 4 times after renaming of modes. However, due to the difference in socketing, the forms
are computationally very different. We show in §7 that while there are non-trivial tensor network
algorithms for evaluating (20),
no such algorithms exist for (21).

Let us write n1 , n2k, ..., nv for the tensor T̂ as defined above. Analogously to the closure properties
(13) and (18), we observe that

  0 0
 

n1 , n2 , . . . , nv
n1 , n2 , . . . , n0v
n1 n01 , n2 n02 , . . . , nv n0v
(24)
⊗
=
.
k
k
k
4. Tensor networks
4.1. Networks. A network (or diagram) consists of a finite set V of vertices, a finite set E of edges,
an incidence relation I ⊆ V × E, and a boundary B ⊆ E. A network is nondegenerate if every edge
is incident to at least one vertex. In what follows we assume that all networks are nondegenerate.
An edge e ∈ E is a loop if e ∈
/ B and e is incident to exactly one vertex.

12

For a vertex v ∈ V , let us write I(v) = {e ∈ E : (v, e) ∈ I} for the set of edges incident to v.
Dually, for an edge e ∈ E, let us write I(e) = {v ∈ V : (v, e) ∈ I} for the set of vertices incident to
e. For a network D, we write V (D), E(D), I(D), and B(D) to refer to the vertices of D, the edges
of D, the incidence relation of D, and the boundary of D, respectively.
Induced networks. For a network D and a nonempty subset W ⊆ V (D), the induced network D[W ]
consists of the vertices in W together with the edges of D that are incident to at least one vertex
in W ; the boundary of D[W ] consists of all edges that are at the boundary of D or incident to a
vertex outside W . Formally,
V (D[W ]) = W ,
(25)

E(D[W ]) = {e ∈ E(D) : (w, e) ∈ I(D) for some w ∈ W } ,
I(D[W ]) = I(D) ∩ (V (D[W ]) × E(D[W ])) ,

B(D[W ]) = (B(D) ∩ E(D[W ])) ∪ {e ∈ E(D[W ]) : (v, e) ∈ I(D) for some v ∈ V (D) \ W } .

For a vertex v ∈ V , we abbreviate D[v] = D[{v}]. Note that the boundary of D[v] consists of all
non-loop edges incident to v in D.
4.2. Tensor networks. Let D be a network. We index D by associating with each edge e ∈ E an
index set J(e) of size `(e). Induced networks inherit indexing by restriction. Next we associate with
each vertex v ∈ V a tensor T (v) ∈ FJ(I(v)) . We say that D equipped with the tensors (T (v))v∈V is
a tensor network.
The value of a tensor network D, or the tensor represented by D, is a tensor T (D) ∈ FJ(B) ,
defined for all i ∈ J(B) by
X
Y
(26)
T (D)i =
T (v)ij .
j∈J(E(D)\B) v∈V

Observe that in (26) the positions i and j together identify a unique entry of T (v) by projection to
J(I(v)). We also observe that the value of a tensor network with an empty boundary is a scalar.
4.3. Contracting tensors. Let D be a tensor network and let W ⊆ V (D) be a nonempty set of
vertices. Let w be a new element not in V . We may contract W in D to obtain a tensor network
D/W by replacing the sub-network D[W ] in D with the single vertex w whose associated tensor
T (w) is the tensor represented by D[W ]. Formally,
V (D/W ) = (V (D) \ W ) ∪ {w} ,
(27)

E(D/W ) = E(D) \ (E(D[W ]) \ B(D[W ])) ,

I(D/W ) = (I(D) \ I(D[W ])) ∪ {(w, e) : e ∈ B(D[W ])} ,

B(D/W ) = B(D) ,

T (w) = T (D[W ]) .
Q
The cost of contracting W in D is c(D, W ) = e∈E(D[W ]) |J(e)|. The value of a tensor network is
invariant under contraction, i.e., for all nonempty W ⊆ V (D) it holds that T (D) = T (D/W ) (see
Lemma A.1 for a proof).
4.4. Execution and cost of a tensor network. To compute the tensor T (D) from a given tensor
network D, we may proceed by a sequence of contractions on D. Such a process is called executing
D, and the cost of D is the cost of a minimum-cost execution of D. We proceed with the details.
Let D = D0 be a tensor network with at least one tensor. For k = 1, 2, . . . , t, select a nonempty
subset Wk−1 ⊆ V (Dk−1 ) such that Wk−1 has at least two tensors or consists of a single tensor with
a loop. Set Dk = Dk−1 /Wk−1 and observe that the number of tensors and/or modes decreases by
at least one in the contraction. Suppose that Dt is loopless and consists of a single tensor. We say

13

that such a sequence of contractions is an execution of D in t steps. The cost of the execution is
maxk=1,2,...,t c(Dk−1 , Wk−1 ). The cost of an execution in zero steps is defined to be 0.
It is immediate that D has at least one execution and every execution consists of at most 2|V (D)|−
1 steps. By invariance under contractions, we have T (Dt ) = T (D). The cost c(D) of D is the cost
of a minimum-cost execution of D.
An execution of D of cost c(D) immediately translates into an algorithm that computes T (D)
using O(c(D)|V (D)|) arithmetic operations in F, since the contraction step Dk = Dk−1 /Wk−1 takes
O(c(Dk−1 , Wk−1 )) ≤ c(D) time to evaluate, and there are O(V (D)) steps.
Lemma 4.1. Let D be a tensor network. There exists a minimum-cost execution of D such that
each contracted set has size at most two. Furthermore, if D is loopless, we can assume that each
contracted set has size exactly two.
In what follows we restrict to consider loopless D only. Thus while a general execution may
contract arbitrary vertex sets in D in each step, we may assume without loss of generality that the
minimum-cost execution has the structure of a rooted binary tree, whose leaves are the vertices of
the tensor network, and each internal vertex is the tensor obtained by contracting its two children.
4.5. Cost of a multilinear map. Let us now define the cost of a multilinear map via the minimumcost tensor networks (and socketing) for evaluating the map. That is, the cost of a multilinear map
is defined in terms of the best tensor network that implements the map. In more precise terms, let
0

A : FJ(E1 ) × FJ(E2 ) × · · · × FJ(E` ) → FJ(E )
be an `-linear map. Consider the tensor T̂ (A) of A and the associated input sockets E1 , E2 , . . . , E`
and the output socket E 0 . Let D∗ be an arbitrary tensor network such that T (D∗ ) = T̂ (A) and
the boundary satisfies B(D∗ ) = E1 ∪ E2 ∪ · · · ∪ E` ∪ E 0 . Modify the network D∗ as follows. For
each k = 1, 2, . . . , `, introduce a new vertex to D∗ , make the new vertex incident to each of the
modes in the input socket Ek , and associate the new vertex with a tensor X (k) ∈ FJ(Ek ) . Remove
the modes E1 ∪ E2 ∪ · · · ∪ E` from the boundary of D∗ . Let us denote the resulting network by
D and call the introduced ` new vertices the socket vertices of D. We observe that B(D) = E 0
and A(X (1) , X (2) , . . . , X (`) ) = T (D). Furthermore, the cost c(D) is independent of the value of
X (k) ∈ FJ(Ek ) for k = 1, 2, . . . , `. We say that D is a realization of A if it can be obtained from A
by this process, and write D(A) for the set of all tensor network realizations D of A.
The cost of the map A is c(A) = minD∈D(A) c(D). In particular, we observe that the minimum
exists since the cost of a tensor network is a nonnegative integer and the family D(A) is nonempty.
5. Upper bounds on cost
This section presents tensor-network algorithms for the maps introduced in §3. All the algorithms
have appeared in earlier work but not necessarily in tensor-network form; that is, our objective here
is to show that these essentially fastest known algorithms can all be represented in the present
tensor-network formalism.
5.1. Fast Fourier transforms and fast convolution. As a warm-up, let us consider how to
express fast Fourier transforms as tensor networks and their executions. We start by observing that
the Cooley–Tukey [32] fast Fourier transform on Z2k can be implemented as a tensor network. We
assume ρ is a primitive (2k )th root of unity in the field F.
Lemma 5.1. The discrete Fourier transform for the Abelian group Z2k can be computed by executing
a tensor network in O(2k k) operations.

14

Proof. The case k = 0 is immediate so let us assume that k ≥ 1. We construct a tensor network
k
whose execution multiplies a vector x ∈ F[2 ] with the DFT matrix Φ in §3.1 for n = 2k to yield
k
the result Φx ∈ F[2 ] . Toward this end, let us write Im for an m × m identity matrix,


1
1
(28)
H2 =
1 −1
k]

for the 2 × 2 Hadamard-Walsh matrix, and R(k,j) ∈ F[2
2j copies of the vector
j ·0

[1, 1, . . . , 1, ρ2
| {z } |

j ·1

, ρ2

2k−1−j

for the vector obtained by concatenating
j ·(2k−1−j −1)

, . . . , ρ2
{z

]
}

2k−1−j

for j = 0, 1, . . . , k − 2. We can (e.g. [85]) decompose Φ into a sequence of 2k × 2k matrices
Φ = P (k) B (k,k−1) T (k,k−2) B (k,k−2) · · · T (k,1) B (k,1) T (k,0) B (k,0)

(29)

consisting of alternating butterfly matrices
B (k,j) = I2 ⊗ I2 ⊗ · · · ⊗ I2 ⊗H2 ⊗ I2 ⊗ I2 ⊗ · · · ⊗ I2
{z
}
|
{z
}
|
j

k−j−1

and diagonal twiddle matrices
T (k,j) = diag(R(k,j) )
followed by a permutation matrix P (k) that permutes the indices in [2k ] viewed as k-bit strings
by reversing the bit-order. Since only the (j + 1)th Kronecker component in the butterfly matrix
B (k,j) is a nonidentity matrix, and multiplication of a vector with the diagonal twiddle matrix
T (k,j) corresponds to pointwise (Hadamard) multiplication with the vector R(k,j) on the diagonal,
we observe that the sequence (29) can be represented as a tensor network D∗ as depicted below (for
k = 5) so that all the modes have length 2.
R5,3

R5,2

R5,1

R5,0

H2
H2

(30)

H2
H2
H2
Φ = P (5)

B (5,4)

T (5,3)

B (5,3)

T (5,2)

B (5,2)

T (5,1)

We can now connect the network (30) to a data vector x ∈ F[2

k]

B (5,1)

T (5,0)

B (5,0)

to obtain the network D below:

(31)

Below we depict in red an execution tree TD with cost 2k+1 for the network (31). Observe that
the mode permutation (multiplication with the matrix P (5) ) is not part of the execution since the

15

permutation amounts to merely rearranging the modes.

(32)

Since the network has O(k) tensors, the execution (32) can be carried out in O(2k k) operations in
F.

Lemma 5.2. The discrete Fourier transform for the elementary Abelian group Zk2 can be computed
by executing a tensor network in O(2k k) operations.
Proof. This proof is analogous to the proof of Lemma 5.1 but omits the twiddle matrices T (k,j) and
the final permutation matrix P (k) from the decomposition of the tensor network.

The following corollary is immediate from Lemma 5.1.
Lemma 5.3. The group algebra products on F[Z2k ] and F[Zk2 ] can be computed by executing a tensor
network in O(2k k) operations whenever 2 is a unit in F.
k

Proof. We start with F[Z2k ]. Let f, g ∈ F[2 ] be two vectors given as input. Our task is to compute
k
the Z2k -convolution f ∗ g ∈ F[2 ] . The case k = 0 is immediate so suppose that k ≥ 1. Recalling
that f ∗ g = Φ−1 ((Φf ) · (Φg)), where “·” denotes an elementwise (Hadamard) product of two vectors
of length 2k , let us construct a tensor network as follows. First take the FFT of f and g using
Lemma 5.1, then multiply the resulting vectors elementwise, and finally take the inverse FFT by
replacing ρ with ρ−1 in Lemma 5.1 and multiplying with the diagonal matrix 21k I2k . Below we
display (for k = 5) the resulting network D that executes to f ∗ g.

(33)

The execution of the network proceeds from right to left analogously to (32).

(34)

The cost of this execution is 2k+1 . Since the network has O(k) tensors, the execution (34) can be
carried out in O(2k k) operations in F.
The case of F[Zk2 ] is analogous but replacing Lemma 5.1 with Lemma 5.2 and modifying the
diagrams accordingly.


16

5.2. Submultiplicativity of cost. Let E1 , E2 , . . . , E` , E 0 be pairwise disjoint sets of indexed
modes such that E1 , E2 , . . . , E` are nonempty. Let
0

A : FJ(E1 ) × FJ(E2 ) × · · · × FJ(E` ) → FJ(E )

be an `-linear map. For a positive integer k, we define the `-linear map A⊗k such that its tensor
satisfies T (A⊗k ) = T (A)⊗k . Then
k

k

k

0 k

A⊗k : FJ(E1 ) × FJ(E2 ) × · · · × FJ(E` ) → FJ(E ) .

Note that T (A⊗k ) = T (A)⊗k is the k-fold Kronecker product of T (A) with itself – that is, it has
the same order, but the index sets are larger – whereas T̂ (A⊗k ) is the k-fold outer product of T̂ (A)
with itself – that is, its index sets have the same sizes, but its order is k times larger.
Let D be a diagram that realizes A and let TD be an execution tree for D. For each internal node
x in TD (that is, a vertex obtained by contraction), define the amortized cost of x by splitting into
the following three cases:
(i) if neither of the two subtrees of x contains a socket vertex, the amortized cost of x is 1;
(ii) if exactly one of the subtrees of x, say, the subtree rooted at y (where x and y are adjacent
in TD ), contains at least one socket vertex, the amortized cost of x is the maximum of the
volume of the tensor at x and the volume of the tensor at y;6
(iii) if both of the subtrees of x contain at least one socket vertex, the amortized cost of x is the
cost of the contraction to obtain x.
The amortized cost a(TD ) of TD is the maximum of the amortized costs of the internal nodes of
TD . Since the amortized cost of each internal node of TD is at most its cost, we have a(TD ) ≤ c(TD ).
Furthermore, we observe that the amortized cost of x in case (ii) above may be strictly less than
the cost of the contraction to obtain x. In particular, in (ii) the amortized cost is defined not by
the cost of the contraction but rather by volume. This is because in a k th Kronecker power we can
amortize the cost of the aggregate transformation in case (ii) not with a single contraction but with
a sequence of k contractions. This observation will form the heart of the proof of Theorem 1.3.
Before proceeding with the proof, let us illustrate the key ideas in visual terms. Let us start with
the three illustrations in (35).

(35)

Suppose the leftmost network in (35) is socketed so that the two modes at the top form the output
socket, and the four modes at the bottom form two input sockets so that modes in the same socket
are incident to the same vertex. In the middle in (35), we have adjoined two socket vertices to the
input sockets to obtain a realization D. On the right in (35), we display an execution tree TD for
D. Observe that the bottom-most internal nodes of TD , and the top-most internal node of TD , have
type (ii). The internal node in the center has type (iii). (There are no internal nodes of type (i).)
Supposing that all the modes have length at least 2, we also observe that the nodes of type (ii) have
amortized cost strictly less than their contraction cost.
6Here, it is crucial to note that the volume of the other subtree rooted at x, only containing non-socket vertices,

does not contribute directly to the amortized cost of x.

17

Let us now consider the k th power of (35) visually, for k = 4:

(36)

The leftmost network in (36) depicts the k-fold outer product of the network on the left in (35)
with itself. Observe that we simply take k copies of the network, but that for the purposes of the
visualization we have taken care to draw the k copies of each mode together for the socketing. In
the middle in (36), we have adjoined two socket vertices to the input sockets to obtain a realization
D⊗k of A⊗k . On the right in (36), we display an execution tree TD⊗k for D⊗k . Observe how each of
the internal nodes of type (ii) in TD gets expanded to a sequence of k internal nodes in TD⊗k . This
transformation from TD to TD⊗k is the gist of the following theorem.
Theorem 5.4 (Formal statement of Theorem 1.3). Let D be an arbitrary realization of A and let
TD be an arbitrary execution tree for D. For all positive integers k, we have
(37)

c(A⊗k ) ≤ a(TD )k−1 c(TD ) .

Furthermore, this realization of A⊗k consists of at most k · |V (D)| vertices.
Proof. Let D∗ be the subnetwork of D with T (D∗ ) = T̂ (A). That is, D∗ is the network induced by
all the non-socket vertices of D. Taking k disjoint copies of D∗ , we obtain a network whose tensor
is T̂ (A⊗k ). Attaching the resulting network to tensors at sockets gives a realization of A⊗k . Let us
write D⊗k for this realization.
To establish (37), it suffices to construct an execution tree TD⊗k for D⊗k whose cost satisfies
c(TD⊗k ) ≤ a(TD )k−1 c(TD ). We construct TD⊗k by rewriting TD from leaves towards the root to
consider the k copies of each vertex in D∗ . We start with leaf nodes which are the vertices of D⊗k .
We split the process into cases (i), (ii), and (iii) as in the definition of amortized cost. Let x be the
internal node of TD that we are currently considering.
In case (i), we perform the contraction indicated by x in each of the k copies of D∗ in D⊗k
individually. This creates k new internal nodes in TD⊗k that are all copies of x. We set these k
nodes as the nodes that correspond to x in the subsequent steps. Each of these contractions in TD⊗k
has the same cost as the contraction indicated by x in TD . This cost is less or equal than c(TD ).
In case (ii), let y be the child of x in TD such that the subtree rooted at y contains a socket
vertex, and let z be the other child of x in TD . There is a single vertex in TD⊗k corresponding to y
and k identical vertices in TD⊗k corresponding to z. We contract these k vertices individually each
with the vertex that corresponds to y. This creates k new internal nodes in TD⊗k , where we set the
topmost node as the node that corresponds to x in the subsequent steps. After the ith step, the
corresponding tensor has i copies of modes of x and k − i copies of modes of y. The cost of the
contraction in the ith step is the cost of contracting y and z in TD multiplied by the the volume of
y to the power k − i and the volume of x to the power i − 1. Since the volumes of x and y are less
than or equal to a(TD ), this cost is less than or equal to a(TD )k−1 c(TD ).
In case (iii), let y and z be the two child nodes of x in TD . By the structure of the earlier steps,
we have that a single vertex in D⊗k corresponds to y, and similarly for z. We contract these two
vertices. This creates one new internal node in TD⊗k , which we set as the node that corresponds
to x in the subsequent steps. This tensor has k copies of modes of x. The cost of this contraction
in TD⊗k is the cost of the corresponding contraction in TD to the k th power, because both tensors
have k copies of all modes compared to y and z. By definition, in case (iii) the amortized cost of

18

contracting y and z is the same as the cost of contracting y and z. Hence the cost of this contraction
in TD⊗k is less or equal than a(TD )k ≤ a(TD )k−1 c(TD ).
This rewriting process produces an execution tree TD⊗k for D⊗k with c(TD⊗k ) ≤ a(TD )k−1 c(TD ).

An immediate corollary is that tensor networks can use low rank decompositions of T (A) to
efficiently evaluate A⊗k .
Corollary 5.5 (Submultiplicativity of low-rank executions). Let A : FJ(E1 ) × FJ(E2 ) × · · · ×
0
FJ(E` ) → FJ(E ) be a multilinear map. Define m = max{|J(E1 )|, |J(E2 )|, . . . , |J(E` )|, |J(E 0 )|} and
r = rk T (A). Then c(A⊗k ) ≤ max(r, m)k min(r, m)
Proof. By taking a star-like network topology (as in (35)) we get an execution with a(TD ) =
max(r, m) and cost c(TD ) = m · r.

5.3. Yates’ algorithm as a special case of submultiplicativity. To witness the initial usefulness of Theorem 5.4, a simple special case occurs when A : F[s] → F[t] is a linear map. It is
immediate that we can realize A with a two-vertex network and an execution tree that has amortized cost max(s, t) and cost st.
k
Then, Theorem 5.4 immediately implies that we can evaluate A⊗k : F[s] → F[t] using a tensor
network with cost max(sk+2 , tk+2 ) and O(k) vertices. In particular, the network can be executed
in O(max(sk+2 , tk+2 )k) operations in F. This network in essence realizes Yates’ algorithm [92] for
multiplying an sk -length vector with the k th Kronecker power of an s × t matrix to obtain tk -length
vector.
Applying the previous observation to A = H2 in (28) with s = t = 2, we obtain Lemma 5.2 as an
immediate corollary. Similarly, other choices of 2 × 2 matrices yield the algebraic core of currently
the fastest known algorithms for problems such as graph coloring and its generalizations such as
computing the Tutte polynomial of a graph [14, 15, 17]. In particular, the pair of mutually inverse
2 × 2 matrices




1 1
1 −1
,
M2 =
Z2 =
0 1
0
1
yield, as Z2⊗k and M2⊗k , the zeta and Möbius tranforms for the lattice ({0, 1}k , ⊆, ∩, ∪) of all
subsets of a k-element set, partially ordered by subset inclusion. Theorem 5.4 yields immediately
the standard algorithms (normally developed via Yates’s algorithm) for the fast zeta and the fast
Möbius transforms via tensor networks. These networks can then be combined as in the proof of
Lemma 5.3 to yield the associated bilinear convolution maps (multiplication maps in the semigroup
algebra F[({0, 1}k , ⊆, ∩, ∪)]) to realize these maps in O(2k k) operations. We omit the details due
to similarity with Lemma 5.3.
5.4. Fast matrix multiplication. Let us now turn to matrix multiplication. We start by considering square matrix multiplication and then proceed to rectangular matrix multiplication.
We recall that the matrix multiplication exponent ω (cf. §1.3) satisfies [20, Proposition 15.1]


log rk hn, n, ni3
(38)
ω = inf
: n≥2 .
log n
Above in (38) we write hn, n, ni3 for the 3-tensor obtained from the 6-tensor hn, n, ni by flattening
the two modes corresponding the rows and columns of each of the three matrices. That is, hn, n, ni3
has shape n2 × n2 × n2 .
Lemma 5.6. For all  > 0 it holds that two n × n matrices may be multiplied in O(nω+ ) operations
by executing a tensor network.

19

Proof. Fix an  > 0. By (38) we can let α, β, γ be three 3-tensors of shape (c × c) × d for positive
integer constants c ≥ 2 and d with c2 ≤ d ≤ cω+/2 such that α, β, γ decompose the matrix
multiplication tensor hc, c, ci defined by (12) as depicted below; the indices i1 , k1 , k2 , j1 , i2 , j2 refer
to the tensor (12). The mode shared by α, β, γ in (39) has length d, all the other modes have length
c.
i2 j2
0

γ

1

2

hc, c, ci

(39)

2

2

α

0

i1 k1

β

1

0

1

k2 j1

For example, Strassen’s decomposition [81] as depicted in (40) below realizes (39) with c = 2 and
d = 7. We use the numbering in magenta to indicate correspondence between modes in (39) and
(40).

(40)

1
0
α=
0
1

0
0
1
1

1
0
0
0

0
0
0
1
2

1
1
0
0

-1 0 1
0 1
0
1 01
0 -1

1
0
β=
0
1

1
0
0
0

0 -1
1 0
0 1
-1 0
2

0
0
0
1

1
1
0
0

0
0
1
1

1
0
1

1
γ= 0
0
1

0
0
1
-1

0
1
0
1

1
0
1
0

-1
1
0
0

0
0
0
1

1
0
0
0

1
0
1

2

Let us next set up an application of Theorem 5.4. Let A : F[c]×[c] × F[c]×[c] → F[c]×[c] be the
bilinear multiplication map for two c × c matrices. Observe that the tensor of A is T̂ (A) = hc, c, ci.
To realize A, define two input sockets in (39), namely {i1 , k1 } and {k2 , j1 } to obtain a realization
D and an execution tree TD as follows:

(41)

Since c2 ≤ d, the amortized cost of TD satisfies a(TD ) = d. The cost is c(TD ) = c2 d.
Let the matrices X, Y ∈ F[n]×[n] be given. We construct a tensor network that multiplies X and
Y . We may assume that n ≥ c. Let k be the unique integer with ck−1 < n ≤ ck . Extend the
k
k
matrices X, Y to X, Y ∈ F[c ]×[c ] by inserting rows and columns with zero-entries.
Since hc, c, ci⊗k = hck , ck , ck i by (13), we have that A⊗k is the multiplication map for two ck × ck
matrices. Using Theorem 5.4 with D and TD , we obtain c(A⊗k ) ≤ a(TD )k−1 c(TD ) = dk c2 . Moreover,
the realization D⊗k of A⊗k given by Theorem 5.4 consists of |V (D⊗k )| = O(k) vertices. We can
now associate X and Y with the two socket vertices of D⊗k , taking care to associate X with the
left socket (originating from {i1 , k1 } and α) and Y with the right socket (originating from {k1 , j1 }
and β). (Cf. (36) for an illustration how D and TD in (41) yield D⊗k and TD⊗k .) Executing D⊗k
then results in the product matrix A⊗k (X, Y ) = XY in dk c2 |V (D⊗k )| ≤ ck(ω+/2)+2 |V (D⊗k )| ≤
ck(ω+) = O(nω+ ) operations for all large enough n.


20

Let us next proceed to rectangular matrix multiplication. Our strategy is to reduce to square
matrix multiplication. Also observe that in the case ω = 2 the upper bounds in the following
theorem are optimal up to the choice of  > 0 because of the size of the input/output.
Lemma 5.7. For all  > 0 it holds that we may multiply an n × r matrix with an r × n matrix by
executing a tensor network in
(i) O(nω+−1 r) operations when r ≥ n, and
(ii) O(n2 rω+−2 ) operations when r ≤ n.
Proof. Fix an  > 0 and let α, β, γ be three 3-tensors of shape (c × c) × d for constants c and d as
in the proof of Lemma 5.6. Let the matrices X ∈ F[n]×[r] and Y ∈ F[r]×[n] be given. We construct
tensor networks that compute the product XY .
To establish (i), first pad X and Y using rows and columns of zero-entries so that both n and
r become positive integer powers of c and n divides r. This increases n and r by at most a
multiplicative factor c. We now have n = ck and r = ct for positive integers t ≥ k.
Observe that we can compute the n × n product matrix XY by taking the sum of nr = ct−k
matrix products of size n × n.
Let us implement this computation with a tensor network. Reshape X to a (k + t)-tensor whose
all modes have length c. The first k modes index the rows, the last t modes index the columns.
Reshape Y to a (t + k)-tensor whose all modes have length c. The first t modes index the rows, the
last k modes index the columns.
Connect X and Y into a network as displayed in (42) on the right.

{

k modes,
each of length c

hck , ck , ck i

hn, r, ni

(42)

X

Y

X

Y
Ic

Ic

} t − k modes,

each of length c

That is, we join t − k column modes of X with the matching t − k row modes of Y using t − k
identity matrices Ic (to avoid degeneracy of the network if X and Y are removed). Then we connect
the remaining modes of X and Y to the left and right sockets of a matrix multiplication network
for ck × ck matrices as depicted by hck , ck , ck i in (42); this matrix multiplication network is obtained
as in the proof of Lemma 5.6. The result is a multiplication network hn, r, ni as depicted in (42)
on the left. We execute this network using the structure on the right in (42) by first contracting
(with zero cost) the identity matrices Ic with Y . We then execute the remaining network as in the
proof of Lemma 5.6. For large enough n, the cost of the execution is at most ck(ω+/2)+2 ct−k+1 ,
which translates to O(nω+ r) operations since the network has O(k) vertices whose contractions
have nonzero cost.
To establish (ii), first pad X and Y using rows and columns of zero-entries so that both n
and r become positive integer powers of c and r divides n. This increases r and n by at most a
multiplicative factor c. We now have r = ck and n = ct for positive integers t ≥ k.
Observe that we can compute the n × n product matrix XY by taking ( nr )2 = c2(t−k) matrix
products of size r × r.

21

Let us implement this computation with a tensor network. Reshape X to a (t + k)-tensor whose
all modes have length c. The first t modes index the rows, the last k modes index the columns.
Reshape Y to a (k + t)-tensor whose all modes have length c. The first k modes index the rows, the
last t modes index the columns. Connect X and Y into a network as displayed in (42) on the right.

Ic

hn, r, ni

(43)

X

Ic

Y

k modes,
each of length c

{

{

t − k modes,
each of length c

hck , ck , ck i

X

Ic
Ic

Y

That is, we join t − k row modes of X each to an identity matrix Ic whose other mode is at the
boundary. Similarly, we join matching t − k column modes of Y each to an identity matrix Ic
whose other mode is at the boundary. (This is to avoid degeneracy of the network if X and Y
are removed.) Then connect the remaining modes of X and Y to the left and right sockets of a
matrix multiplication network for ck × ck matrices as depicted by hck , ck , ck i in (43); this matrix
multiplication network is obtained as in the proof of Lemma 5.6. The result is a multiplication
network hn, r, ni as depicted in (43) on the left. We execute this network using the structure on the
right in (43) by first contracting (with zero cost) the identity matrices Ic with X and Y , respectively.
We then execute the remaining network as in the proof of Lemma 5.6. For large enough r, the cost
of the execution is at most ck(ω+/2)+2 c2(t−k)+1 , which translates to O(n2 rω−1+ ) operations since
the network has O(k) vertices whose contractions have nonzero cost.

5.5. Kruskal operator. We proceed to implement the Kruskal operator by Kroneckering and
reduction to fast rectangular matrix multiplication.
Lemma 5.8. For all constants  > 0 and ` = 1, 2, . . . it holds that we may evaluate the Kruskal
operator of ` matrices of shape n × r by executing a tensor network in
(i) O(nd`/2e(ω+−1) r) operations when r ≥ nd`/2e , and
(ii) O(n2d`/2e rω+−2 ) operations when r ≤ nd`/2e .

Proof. Fix an  > 0 and let α, β, γ be three 3-tensors of shape (c × c) × d for constants c and d as in
the proof of Lemma 5.6. Let A(1) , A(2) , . . . , A(`) ∈ F[n]×[r] be given as input. We construct a tensor
network that computes the output Y of the Kruskal operator (16).
Without loss of generality we may assume that ` is even by introducing a matrix A(`+1) ∈ F[n]×[r]
filled with 1-entries and setting ` ← ` + 1. By inserting rows and columns with zero-entries as
necessary, we can assume that both n and r are positive integer powers of c. The key idea is
now to Kronecker the matrices A(1) , A(2) , . . . , A(`/2) and A(`/2+1) , A(`/2+2) , . . . , A(`) in the vertical
`/2
`/2
dimension only to obtain two matrices B ∈ F[n ]×[r] and C ∈ F[n ]×[r] , respectively. We then
multiply B and the transpose of C using fast rectangular matrix multiplication from Lemma 5.7 to
`/2
`/2
obtain Y ∈ F[n ]×[n ] . It is immediate from Lemma 5.7 that this results in the operation counts
claimed in (i) and (ii) as long as we can realize the idea using tensor networks. Kroneckering in
the vertical dimension only can be realized by joining all the horizontal dimensions to a common
mode, which becomes the inner mode for matrix multiplication. The resulting network is depicted
below (for ` = 6), where either (42) or (43) is used for the subnetwork indicated with hn`/2 , r, n`/2 i

22

depending on whether (i) or (ii) holds.
hnl/2 , r, nl/2 i
(44)
A(1) A(2) A(3) A(4) A(5) A(6)
In drawing (44) we have made two abstractions. First, each drawn mode in fact is a bundle of
modes, each of length c. Second, each mode in a bundle that is incident to one of the input matrices
A(1) , A(2) , . . . , A(`) is in fact subdivided by inserting an identity matrix Ic just before the incidence to
the input matrix. The network (44) is executed first by contracting the (zero-cost) identity matrices
Ic , then contracting A(1) , A(2) , . . . , A(`/2) and A(`/2+1) , A(`/2+2) , . . . , A(`) , and finally proceeding to
execute the subnetwork hn`/2 , r, n`/2 i as in Lemma 5.7.


5.6. The binomial-linear forms. We now proceed to the v2 -linear forms.

Lemma 5.9. For all constants  > 0 and v = 3, 4, . . . it holds that we may evaluate the v2 -linear

form on given v2 matrices of shape n × n by executing a tensor network in O(n(ω+)bv/3c+(v mod 3) )
operations.
Proof. Fix an  > 0 and let α, β, γ be three 3-tensors of shape (c × c) × d with constants c and d as
in the proof of Lemma 5.6.
Let u = v mod 3 and s = (v − u)/3. That is, s and u are positive integers that satisfy v = 3s + u.
Let us write [a, b] = [b] \ [a − 1] and set
P1 = [1, 2s] ∪ [3s + 1, 3s + u] ,

P2 = [1, s] ∪ [2s + 1, 3s] ∪ [3s + 1, 3s + u] ,

P3 = [s + 1, 3s] .


Now partition the subsets in [v]
into three groups G1 , G2 , G3 ⊆ [v]
such that (a) G1 consists of
2
2


[v]
\ G1 with
all subsets {x, y} ∈ 2 with {x, y} ⊆ P1 , (b) G2 consists of all subsets {x, y} ∈ [v]
2

[v]
{x, y} ⊆ P2 , and (c) G3 consists of all subsets {x, y} ∈ 2 \ (G1 ∪ G2 ). In particular, we observe
that for all {x, y} ∈ G3 we have {x, y} ⊆ P3 . Also observe that |P1 | = |P2 | = 2s + u and |P3 | = 2s.


Let the v2 matrices A{x,y} ∈ F[n]×[n] for {x, y} ∈ [v]
2 be given as input. By inserting rows and
columns with zero-entries as appropriate, we may assume that n = ck for a positive integer k. The
key idea is to start with a base construction for an input of size c and then scale the construction
up to an input of size n using Theorem 5.4.
Let us now describe the base construction. First, we introduce a subnetwork that forces consistency of modes for the inputs indexed by G1 , G2 , and G3 , respectively. In essence, for each mode
z ∈ P1 , introduce a mode for each occurrence of z in G1 . Similarly, for each z ∈ P2 , introduce a
mode for each occurrence of z in G2 . Finally, for each z ∈ P3 , introduce a mode for each occurrence
of z in G3 . Below we show an illustration for v = 8 and thus s = 2, u = 2.
12

13

14

17

18

23

24

27

28

34

37

38

47

48

78

15

16

25

26

56

57

58

67

68

35

36

45

4

5

46

(45)
1

2

3

4

7

8

1

2

5

6

7

8

3

6

In the drawing (45) all modes have length c, and each occurrence of z ∈ [v] at the top is tacitly
assumed to be subdivided by an identity matrix Ic . (Otherwise the network would be degenerate.)
Next we introduce s copies of α, β, γ to force consistency for the modes in [1, 3s] between G1 , G2 , G3 .

23

We also join individually each of the u modes in [3s + 1, 3s + u] between G1 and G2 . Below we show
an illustration for v = 8. Observe from (39) and the numbering in magenta that each introduced
copy i = 1, 2, . . . , s of α, β, γ forces consistency between the modes i, s + i, 2s + i.
1 2 1 3 1 4 1 7 1 8 2 3 2 4 2 7 2 8 3 4 3 7 3 8 4 7 4 8 7 8

1 5 1 6 2 5 2 6 5 6 5 7 5 8 6 7 6 8

3 5 3 6 4 5 4 6

(46)
1 0

1 0

0 1

0 1

0 1

0 1

2

2

2

2

2

2

α

α

β

β

γ

γ


The base network D realizing the c-uniform v2 -linear form is now as depicted in (46). We execute
the network D using
 the following execution tree TD , where the identity matrices Ic immediately
v
incident to the 2 socket vertices are contracted tacitly and not drawn in (47).

(47)

The amortized cost of the execution in (47) is a(TD ) = ds cu and the cost is c(TD ) ≤ ds+1 cu+2 .
By Theorem 5.4, this translates to cost at most a(TD )k−1 c(TD ) = dsk+1 cuk+2 for the n-uniform
v
ω+/2 , we
2 -linear form. Since the network given by Theorem 5.4 has O(sk) tensors and d ≤ c
(ω+)s+u
conclude that the number of operations is O(n
). The lemma follows.

5.7. The permanent. The following lemma observes that essentially the fastest known algorithm
for the permanent, namely Ryser’s algorithm [77], can be realized as a tensor network. Here by
essentially fastest known we mean the base of the exponential running time. Sub-exponential speedups to Ryser’s algorithm are known, see e.g. Björklund [13].
Lemma 5.10. The permanent of an n × n matrix can be computed by executing a tensor network
in O(2n n) operations.
Proof. We observe that Ryser’s algorithm [77] for the permanent (9), namely the inclusion–exclusion
expression
X
YX
per A =
(−1)n−|S|
aij
S⊆[n]

i∈[n] j∈S

is implementable with a star-shaped tensor network consisting of n matrices of shape 2n × n joined
together by a common mode (of length 2n ), with the n modes of length n being the boundary
of the network. Each of the n matrices consists of the {0, 1}-valued incidence vectors of the 2n
subsets S ⊆ [n], with one of the matrices arbitrarily selected to contain signed rows determined by
(−1)n−|S| . The input to the network consists of n vectors of length n, namely the rows of the n × n
input matrix A. The network is executed by first executing the n matrix-vector multiplications,
and then contracting the resulting n vectors of length 2n until the scalar per A remains.


24

6. A lower bound for the cost of a multilinear map
In this section, we prove a general lower bound on the cost of evaluating a multilinear map using
tensor networks, as defined in Section 4.5. The lower bound is expressed in terms of the socket-width
of a multilinear map, which we now proceed to define.
0
Let A : FJ(E1 ) × FJ(E2 ) × · · · × FJ(E` ) → FJ(E ) be an `-linear map. A socket-tree of A is a tree
TS whose ` + 1 leaf nodes are the sockets E1 , E2 , . . . , E` , E 0 of A and whose internal nodes all have
degree exactly 3. Associate with each edge e = {xR , xC } of TS the two subtrees TS (xR , e) and
TS (xC , e) obtained by removing e, where TS (xR , e) is the subtree containing xR and TS (xC , e) is
the subtree containing xC . Let L(xR , e) be the set of leaves in TS (xR , e) and let L(xC , e) be the set
of leaves in TS (xC , e).
The sets L(xR , e) and L(xC , e) are both nonempty and together partition the set of sockets.
Consider the flattening M (TS , e) of the tensor T (A) such that the modes in L(xR , e) index the rows
and the modes in L(xC , e) index the columns of M (TS , e). The width of TS at e is the rank of
M (TS , e), and the width of TS is w(TS ) = maxe∈E(TS ) rk(M (TS , e)).
Let us write S (A) for the set of all socket-trees of the multilinear form A. We define the socketwidth of A to be w(A) = minTS ∈S (A) w(TS ).
The rest of this section is devoted to proving Theorem 1.4:
Theorem 1.4. For every multilinear map A, it holds that c(A) ≥ w(A).
First, we prove that without loss of generality, we may restrict attention to forms rather than
general maps.
Claim 6.1. For any multilinear map A, it holds that c(A) ≥ c(F (A)).
Proof. We observe that A and F (A) satisfy T̂ (A) = T̂ (F (A)). Any network D ∈ D(A) can be
0
modified to a network D0 ∈ D(F (A)) by attaching a tensor X 0 ∈ FJ(E ) to the boundary of D. Let
D ∈ D(A) be such that c(D) = c(A). The minimum-cost execution of D, followed by contracting
0
T (D)
of D0 . Its cost is c(A), since the cost of contracting of T (D) and X 0
Q and X , is an execution
Q
is e∈B(D) |J(e)| and e∈B(D) |J(e)| ≤ c(A), because the last step of the minimum-cost execution
of D contracted a set W with all modes e ∈ B(D) incident to W . Thus, c(A) ≥ c(F (A)).

Furthermore, w(A) = w(F (A)) for every multilinear map A, since w(A) only depends on the
tensor T̂ (A) and the grouping of modes into sockets, but not on which socket (if any) is the output
socket. Thus it suffices to prove Theorem 1.4 for multilinear forms, which we now proceed to do.
Lemma 6.2. For any multilinear form F , it holds that c(F ) ≥ w(F ).

Proof. Let D ∈ D(F ) be such that c(D) = c(F ). It is a tensor network with empty boundary
and a socket vertex Si ∈ V (D) for each input socket Ei , where i = 1, 2, . . . , `. Its tensor is
T (D) = F (X (1) , X (2) , . . . , X (`) ) where X (i) = T (Si ) for i = 1, 2, . . . , `.
By Lemma 4.1, a minimum-cost execution of D can be represented by a rooted binary tree TD ,
where the set of leaves of TD are V (D) and each inner node represents the vertex obtained by
contracting its two children. Let TS be the unique socket-tree of F that is obtained as a topological
minor of TD . Slightly abusing the notation, we assume that the leaves of TS are the socket vertices
S1 , S2 , . . . , S` instead of the sockets E1 , E2 , . . . , E` . To establish the lemma, it suffices to show that
TD has cost at least w(TS ), since w(TS ) ≥ w(F ).
Let e = {xR , xC } ∈ E(TS ) be an edge of the socket tree TS with rk(M (TS , e)) = w(TS ), and let ee
be an edge of the execution tree TD in the subdivision of e appearing in TD . Define SR = L(xR , e)
and SC = L(xC , e). Let WR ⊆ V (D) be the set of non-socket vertices of D that appear on the
same side of ee in TD with socket vertices SR and let WC be the set of remaining non-socket vertices
of D. Finally, let D0 = D/SR /SC /WR /WC be the result of contracting each of these four sets of

25

vertices of D. For notational convenience, we identify the four nodes of the new network with the
four subsets SR , SC , WR , WC .
The tensor P = T (D0 [WR ∪ SR ]) appears as an intermediate result in the execution TD , hence
the volume ofSP is a lower bound on the cost of TD .
S
Let ER = Ei ∈I(SR ) Ei be the union of all modes at the boundary of D0 [SR ], EC = Ei ∈I(SC ) Ei
be the union of all modes at the boundary of D0 [SC ] and ERC ⊆ E(D0 ) be the set of all modes e in
D0 such that I(e) 6⊆ WR ∪ SR and I(e) 6⊆ WC ∪ SC . Note that |J(ERC )| is precisely the volume of
P and that ERC may intersect ER and EC .
0 ∪ E 00 and E
0
00
0
0
Let ER = ER
RC = ERC ∪ ERC , where ER and ERC consist of modes that are
R
00 and E 00
00 = E 00 .
incident to WR , and ER
consist of modes not incident to WR . We have ER
RC Q
RC
Q
0
J(e)
J(e)
Define Te(D [WR ]) ∈ e∈ER F
× e∈ERC F
as follows:
(
T (D0 [WR ])i,k if j = l,
Te(D0 [WR ])i,j,k,l =
0
otherwise,
0 ), j ∈ J(E 00 ), k ∈ J(E 0 ), and l ∈ J(E 00 ). If all edges in E
where i ∈ J(ER
are incident to
R
RC
RC Q
Q RC J(e)
0
0
0
J(e)
e
WR , then T (D [WR ]) = T (D [WR ]). Recall that T (D [SR ]) ∈ e∈E 0 F
× e∈E 00 F
. Then for
R
R
every k, l, we have
X
X
Te(D0 [WR ])i,j,k,l T (D0 [SR ])i,j =
Te(D0 [WR ])i,l,k,l T (D0 [SR ])i,l
i,j

i

=

X

T (D0 [WR ])i,k T (D0 [SR ])i,l = Pk,l .

i

Giving these two tensors appropriate flattened shapes Te(D0 [WR ]) ∈ FJ(ER ) ×FJ(ERC ) and T (D0 [SR ]) ∈
FJ(ER ) , we observe that P is simply the vector-matrix product P = T (D0 [SR ]) · Te(D0 [WR ]) ∈
FJ(ERC ) . Similarly, for the other half of D0 , we can write Q = T (D0 [WC ∪ SC ]) as a matrixvector product Q = Te(D0 [WC ]) · T (D0 [SC ]) ∈ FJ(ERC ) where Te(D0 [WC ]) ∈ FJ(ERC )×J(EC ) and
T (D0 [SC ]) ∈ FJ(EC ) .
Thus we have T (D) = T (D0 [SR ]) · Te(D0 [WR ]) · Te(D0 [WC ]) · T (D0 [SC ]). Recall that for each
socket vertex Si in the original network D, we have T (Si ) = X (i) . Denoting XR = T (D0 [SR ]) and
N
N
XC = T (D0 [SC ]), we get XR = Si ∈SR X (i) and XC = Si ∈SC X (i) .7 Hence
F (X (1) , X (2) , . . . , X (`) ) = XR · (Te(D0 [WR ]) · Te(D0 [WC ])) · XC .
It follows that Te(D0 [WR ]) · Te(D0 [WC ]) is the flattening of T (F ) to a matrix with rows indexed by
the sockets in SR and columns indexed by the sockets in SC . But this flattening is precisely the
matrix M (TS , e), implying that |J(ERC) | ≥ rk(M (TS , e)) = w(TS ), as desired.

7. Lower bounds for socket-width
In this section we establish lower bounds on socket-width for concrete maps.
7.1. Determinant and permanent. We now prove lower bounds for the socket width of the
determinant and permanent. Let us start with the following trivial observation.
Claim 7.1. For any socket tree TS with n ≥ 2 leaves, there is an edge e = {xR , xC } such that
n/3 ≤ |L(xR , e)| < 2n/3.
7These identities use the fact that D is derived from a non-degenerate network D ∗ for T̂ (F ). In particular, every

mode in the network D is incident upon at least one non-socket vertex, hence all modes incident upon SR are boundary
modes in D0 [SR ], and similarly for SC .

26

Proof. Consider all edges e = {xR , xC } such that |L(xR , e)| ≥ n/3. At least one such edge certainly
exists since n ≥ 2. Indeed, an edge e = {xR , xC } incident to a leaf xC has |L(xR , e)| = n − 1 leaves.
Among these, choose an edge such that TS (xR , e) is of minimal size. Assume for contradiction that
|L(xR , e)| ≥ 2n/3. But then one of the two subtrees of xR in TS (xR , e) must have at least n/3
leaves, and since they are smaller than TS (xR , e), this contradicts the minimality of TS (xR , e). 
Lemma 7.2. For every positive integer n ≥ 2,
 the socket-width of both the determinant and the
n
.
permanent of an n × n matrix is at least dn/3e

Proof. Let TS be a socket tree for the permanent, let e = {xR , xC } be an arbitrary edge in TS, and
let k = |L(xR , e)| be the number of leaves in TS (xR , e). We now show that rk(M (TS , e)) ≥ nk .
Recall that the sockets of TS are the n rows of the input matrix. Without loss of generality,
number the rows so that the leaves of TS (xR , e) are rows 1 to k, and the leaves of TS (xC , e) are rows
k + 1 to n. The rows of M (TS , e) are indexed by a tuple jR = (i1 , . . . , ik ) ∈ [n]k , and the columns
are indexed by a tuple jC = (ik+1 , . . . , in ) ∈ [n]n−k . The entry of M (TS , e) at position (jR , jC ) is 1

if (i1 , i2 , . . . , in ) is a permutation. For any set U ∈ [n]
k , let u1 < u2 < . . . < uk be the elements of
U in ascending order and define jR (U ) = (u1 , . . . , uk ); let uk+1 < uk+2 < . . . < un be the elements
of [n] \ U in ascending order and define jC (U ) = (uk+1 , uk+2 , . . . , un ).

For U1 , U2 ∈ [n]
k , the entry
 of nM
 (TS , e) at position (jR (U1 ), jC (U2 )) equals 1 if U1 = U2 , and
0
n
n
otherwise. This induces a k × k identity submatrix of M (TS , e), implying rk(M (TS , e)) ≥ k .
By Claim 7.1, TS has an edge e with n/3 ≤ k < 2n/3. For that edge, rk(M (TS , e)) ≥ nk ≥
n
dn/3e , which completes the proof for the permanent.
For the determinant, the only change is that some entries of M (TS , e) become −1 instead of 1,
but this only changes the identified submatrix from an identity matrix to a diagonal matrix and in
particular does not change its rank.

7.2. Binomial-linear forms. Let us start by considering lower bounds for the binomial-linear
forms. We establish two results, one for
 the case v > k ≥ 3 and one for the case v > k = 2.
Suppose TS is a socket tree for a kv -linear form. Recall that the sockets of this form correspond

to the elements of [v]
k . Given an edge e ∈ E(TS ) and a vertex x ∈ V (TS ), we write
[
U (x, e) =
S ⊆ [v].
S∈L(x,e)


Claim 7.3. For any v ≥ k ≥ 2, any socket tree TS of a kv -linear form, and any edge e = {xR , xC }
of TS , it holds that either U (xR , e) = [v] or U (xC , e) = [v].

Proof. Suppose for contradiction that there is an edge e = {xR , xC } with i1 6∈ U (xR , e) and i2 6∈
U (xC , e) for some not necessarily distinct i1 , i2 ∈ [v]. But since k ≥ 2, there exists a socket S ⊇
{i1 , i2 }, and that socket must appear in either TS (xR , e) or TS (xC , e). This leads to a contradiction.


Claim 7.4. Let TS be a socket tree for a kv -linear form with index set sizes n1 , n2 , . . . , nv and
v > k ≥ 2. Let eQ
= {xR , xC } ∈ E(TS ) and suppose U (xC , e) = [v]. Then the socket width of TS is
at least w(TS ) ≥ i∈U (xR ,e) ni .
Q
Proof. Let m = i∈U (xR ,e) ni . We show that rk(M (TS , e)) ≥ m by identifying an m × m identity
submatrix of M (TS , e).
Define ER = { (S, i) | S ∈ L(xR , e), i ∈ S } to be the modes contained in the sockets on the xR
side of e, and analogously EC = { (S, i) | S ∈ L(xC , e), i ∈ S }.
The rows of M (TS , e) are indexed by J(ER ) and the columns are indexed by J(EC ). We will
consider
Q an m × m submatrix of M (TS , e) whose rows and columns are indexed by the elements
σ ∈ i∈U (xR ,e) [ni ]. More specifically, each row of the submatrix is indexed by jR where jR |(S,i) = σ|i

27

for i ∈ U (xR , e). Each column is indexed by jC where jC |(S,i) = σ|i for i ∈ U (xR , e) and jC |(S,i) = 1
for i 6∈ U (xR , e).
Q
The value of the submatrix at position (jR , jC ) is 1 if there exists σ ∈ i∈U (xR ,e) [ni ] such that
jR |(S,i) = σ|i and jC |(S,i) = σ|i for all i ∈ U (x, e) and 0 otherwise. Because all elements of U (xR , e)
appear also in U (xC , e), we yield an m × m identity matrix as desired.

With these claims in hand we are ready to prove our lower bounds.
Lemma 7.5. Let v and k be positive integers with v > k ≥ 3. Then, the socket-width of a
form with index sets of sizes n1 , n2 , . . . , nv is at least n1 n2 · · · nv .

v
k



-linear

Proof. Let TS be an arbitrary socket tree for the form. By Claim 7.4, it suffices to show that TS
must have an edge e = {xR , xC } of TS such that U (xR , e) = U (xC , e) = [v].
Suppose for contradiction that TS has no such edge. By Claim 7.3, each edge e = {xR , xC } has
either U (xR , e) = [v] or U (xC , e) = [v]. Direct each edge towards the subtree which covers [v]. For
example, if U (xR , e) = [v] and U (xC , e) 6= [v] then e is directed towards xR .
Since a tree is acyclic, there must be some vertex x∗ such that all edges incident to x∗ are directed
towards x∗ . The vertex x∗ cannot be a leaf, because the subtree consisting of a leaf contains a single
socket, which covers k < v elements. Thus x∗ has degree 3. Let the three edges incident to x∗ be
e1 = {x∗ , y1 }, e2 = {x∗ , y2 } and e3 = {x∗ , y3 }. Since all the edges are directed towards x∗ there are
i1 , i2 , i3 ∈ [v] such that i1 6∈ S(y1 , e1 ), i2 6∈ S(y2 , e2 ) and i3 6∈ S(y3 , e3 ). Since k ≥ 3 there exists a
socket S ⊇ {i1 , i2 , i3 }. But now the socket S cannot appear in any of the subtrees rooted at y1 , y2 ,
or y3 . Since these three subtrees together cover all leaves, this yields the desired contradiction and
we conclude that there must exist an edge e such that U (xR , e) = U (xC , e) = [v].

Next we proceed with the case k = 2, which is a bit more subtle. Let us write Km for the
complete graph on m vertices. We say that a set of subgraphs covers Km if every edge of Km occurs
in at least one of the subgraphs. We start by establishing the following claim.
Claim 7.6. For all positive integers t it holds that
(i) K3t cannot be covered by three copies of K2t−1 ,
(ii) K3t+1 cannot be covered by three copies of K2t , and
(iii) K3t+2 cannot be covered by three copies of K2t+1 .
Proof. To verify (i), consider any two K2t−1 in K3t . The vertex sets of these two K2t−1 must cover
the 3t vertices or otherwise the third K2t−1 will be insufficient to cover all the 3t − 1 edges leaving
from any uncovered vertex. It follows that the two K2t−1 must have c = t − 2 vertices in common
and u = t + 1 vertices unique to each K2t−1 . Indeed, we obtain c and u as solutions of the system
with c + u = 2t − 1 and c + 2u = 3t. A third K2t−1 is insufficient to cover the u2 edges on 2u
vertices joining the two sets of size u, because 2t − 1 < 2u. To verify (ii), consider any two K2t in
K3t+1 . As above, we observe that the two K2t must have u = t + 1 and 2t < 2u, a contradiction.
To verify (iii), consider any two K2t+1 in K3t+2 . As above, we observe that the two K2t+1 must
have u = t + 1 and 2t < 2u, a contradiction. This completes the proof of the claim.


We say that a kv -linear form is n-uniform if the index sets satisfy n = n1 = n2 = · · · = nv .
Lemma
7.7. Let v and n be positive integers with v ≥ 3. Then, the socket-width of an n-uniform

v
d2v/3e .
2 -linear form is at least n
Proof. Write v = 3t + r for integers t ≥ 1 and r ∈ {0, 1, 2}, and let L be the desired exponent for
the lower bound. That is, for r = 0 we need L = 2t, for r = 1 we need L = 2t + 1, and for r = 2
we need L = 2t + 2. Note that by Claim 7.6, the complete graph Kv cannot be covered by three
copies of KL−1 .

28

Our goal is to show that S contains an edge e = {xR , xC } with |U (xR , e)| ≥ L and U (xC , e) = [v],
which by Claim 7.4 yields the desired lower bound. Assume for contradiction that no such edge
exists.
By Claim 7.3 every edge e = {xR , xC } has either U (xR , e) = [v] or U (xC , e) = [v]. Just like
in the proof of Lemma 7.5, orient each edge towards the vertex which covers [v], and let x∗ be a
vertex with no outgoing edges. Then x∗ must have degree 3. Let the three edges be e1 = {x∗ , y1 },
e2 = {x∗ , y2 }, and e3 = {x∗ , y3 }. Then |S(y1 , e1 )|, |S(y2 , e2 )|, |S(y3 , e3 )| ≤ L − 1. Considering for
every socket all the edges in Kv that correspond to a pair of elements in the socket, we have that
the set of sockets in the subtree rooted at each yi gives a subgraph of Kv on at most L − 1 vertices,
and in particular is contained in a complete graph on L − 1 vertices. Since the parameters v and L
are chosen so that Kv can not be covered by three copies of KL−1 , we get a contradiction. Thus TS
must contain an edge with |U (xR , e)| ≥ L and U (xC , e) = [v].

7.3. Kruskal operator. We say that an `-linear Kruskal operator is n-uniform if the lengths of
the modes satisfy n = n1 = n2 = · · · = n` .
Lemma 7.8. For positive integers n and r, the socket-width of an n-uniform `-linear Kruskal
operator is at least max n` , nd`/2e r .
Proof. Let TS be an arbitrary socket tree for the operator. One of the leaves is the output socket
representing the tensor B of shape n × n × · · · × n (` times) that is obtained by applying the Kruskal
operator to the input matrices A(i) of shape n × r, where 1 ≤ i ≤ `.
Consider the neighbor x of the output socket. It has three neighbors: the output socket leaf,
and two other vertices xR and xC . Either the subtree rooted at xR or the one rooted at xC must
contain u ≥ d`/2e input sockets (since together they contain all ` input sockets). Let e be the edge
leading to that subtree.
We claim that rk(M (TS , e)) ≥ nu r. Suppose without loss of generality that the input sockets
(1)
A , . . . , A(u) are in the subtree rooted at xR , and that the input sockets A(u+1) , . . . , A(`) are in the
subtree rooted at x together with the output socket.
Each row of M (TS , e) is indexed by sequences of 2u indices (i1 , j1 , . . . , iu , ju ) where each i ∈
[n] and each j ∈ [r]. Each column is indexed by a sequence of ` + 2(n − u) indices (i01 , . . . , i0` ;
iu+1 , ju+1 , . . . , i` , j` ) where each i, i0 ∈ [n] and each j ∈ [r]. An entry of M (TS , e) is 1 if and only if
i01 = i1 , i02 = i2 , . . . , i0` = i` , and j1 = j2 = . . . = j` .
For any i1 , . . . , iu ∈ [n] and j ∈ [r], consider the row index (i1 , j, i2 , j, . . . , iu , j) and the column
index (i1 , i2 , . . . , iu , 1, 1, . . . , 1; 1, j, 1, j, . . . , 1, j). The nu r × nu r submatrix of M (TS , e) induced by
these sets of row and column indices is the identity matrix, thus rk(M (TS , e)) ≥ nu r as desired.
For the n` lower bound, we instead consider the edge e0 joining x with the output socket. Now
the rows are indexed by (i1 , j1 , i2 , j2 , . . . , i` , j` ) and the columns by (i01 , . . . , i0` ). The n` × n` identity
submatrix is obtained by taking for every i1 , . . . , i` ∈ [n], the row (i1 , 1, i2 , 1, . . . , i` , 1) and the
column (i1 , . . . , i` ).


Acknowledgments
Per Austrin was funded by the Swedish Research Council, Grant 621-2012-4546. The research of
Petteri Kaski leading to these results has received funding from the European Research Council under the European Union’s Seventh Framework Programme (FP/2007-2013) / ERC Grant Agreement
338077 “Theory and Practice of Advanced Search and Enumeration.” The first part of this research
was done while Kaie Kubjas was at Aalto University. The last part of this research was done while
Kaie Kubjas was at MIT and UPMC, and was supported by the European Union’s Horizon 2020
research and innovation programme / Marie Skłodowska-Curie Grant Agreement 748354.

29

References
[1] A. Abboud, A. Backurs, K. Bringmann, and M. Künnemann. Fine-grained complexity of analyzing compressed
data: Quantifying improvements over decompress-and-solve. In C. Umans, editor, 58th IEEE Annual Symposium
on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 192–203.
IEEE Computer Society, 2017.
[2] A. Abboud, A. Backurs, and V. V. Williams. If the current clique algorithms are optimal, so is Valiant’s parser.
In V. Guruswami, editor, IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015,
Berkeley, CA, USA, 17-20 October, 2015, pages 98–117. IEEE Computer Society, 2015.
[3] M. Alekhnovich, A. Borodin, J. Buresh-Oppenheim, R. Impagliazzo, A. Magen, and T. Pitassi. Toward a model
for backtracking and dynamic programming. Computational Complexity, 20(4):679–740, 2011.
[4] N. Alon and S. Gutner. Balanced families of perfect hash functions and their applications. ACM Trans. Algorithms, 6(3):54:1–54:12, 2010.
[5] N. Alon, R. Yuster, and U. Zwick. Finding and counting given length cycles. Algorithmica, 17(3):209–223, 1997.
[6] I. Arad and Z. Landau. Quantum computation and the evaluation of tensor networks. SIAM J. Comput.,
39(7):3089–3121, 2010.
[7] S. Arora and B. Barak. Computational Complexity: A Modern Approach. Cambridge University Press, New
York, NY, USA, 1st edition, 2009.
[8] F. Bacchus, S. Dalmao, and T. Pitassi. Algorithms and complexity results for #SAT and Bayesian inference.
In 44th Symposium on Foundations of Computer Science (FOCS 2003), 11-14 October 2003, Cambridge, MA,
USA, Proceedings, pages 340–351. IEEE Computer Society, 2003.
[9] M. Beaudry and M. Holzer. The complexity of tensor circuit evaluation. Computational Complexity, 16(1):60–111,
2007.
[10] A. R. Benson and G. Ballard. A framework for practical parallel fast matrix multiplication. In A. Cohen and
D. Grove, editors, Proceedings of the 20th ACM SIGPLAN Symposium on Principles and Practice of Parallel
Programming, PPoPP 2015, San Francisco, CA, USA, February 7-11, 2015, pages 42–53. ACM, 2015.
[11] S. J. Berkowitz. On computing the determinant in small parallel time using a small number of processors. Inf.
Process. Lett., 18(3):147–150, 1984.
[12] J. D. Biamonte, J. Morton, and J. Turner. Tensor network contractions for #SAT. Journal of Statistical Physics,
160(5):1389–1404, 2015.
[13] A. Björklund. Below all subsets for some permutational counting problems. In R. Pagh, editor, 15th Scandinavian
Symposium and Workshops on Algorithm Theory, SWAT 2016, June 22-24, 2016, Reykjavik, Iceland, volume 53
of LIPIcs, pages 17:1–17:11. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016.
[14] A. Björklund, T. Husfeldt, P. Kaski, and M. Koivisto. Fourier meets Möbius: fast subset convolution. In D. S.
Johnson and U. Feige, editors, Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San
Diego, California, USA, June 11-13, 2007, pages 67–74. ACM, 2007.
[15] A. Björklund, T. Husfeldt, P. Kaski, and M. Koivisto. Computing the Tutte polynomial in vertex-exponential
time. In 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, October 25-28, 2008,
Philadelphia, PA, USA, pages 677–686. IEEE Computer Society, 2008.
[16] A. Björklund, T. Husfeldt, P. Kaski, and M. Koivisto. Counting paths and packings in halves. In A. Fiat
and P. Sanders, editors, Algorithms - ESA 2009, 17th Annual European Symposium, Copenhagen, Denmark,
September 7-9, 2009. Proceedings, volume 5757 of Lecture Notes in Computer Science, pages 578–586. Springer,
2009.
[17] A. Björklund, T. Husfeldt, and M. Koivisto. Set partitioning via inclusion-exclusion. SIAM J. Comput.,
39(2):546–563, 2009.
[18] A. Björklund, P. Kaski, and Ł. Kowalik. Counting thin subgraphs via packings faster than meet-in-the-midd
le time. In C. Chekuri, editor, Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Di screte
Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 594–603. SIAM, 2014.
[19] J. R. Bunch and J. E. Hopcroft. Triangular factorization and inversion by fast matrix multiplication. Math.
Comp., 28:231–236, 1974.
[20] P. Bürgisser, M. Clausen, and M. A. Shokrollahi. Algebraic Complexity Theory, volume 315 of Grundlehren der
Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. Springer-Verlag, Berlin,
1997. With the collaboration of Thomas Lickteig.
[21] J. Cai, H. Guo, and T. Williams. A complete dichotomy rises from the capture of vanishing signatures. SIAM
J. Comput., 45(5):1671–1728, 2016.
[22] J. Cai, P. Lu, and M. Xia. Computational complexity of holant problems. SIAM J. Comput., 40(4):1101–1132,
2011.
[23] F. Capelli, A. Durand, and S. Mengel. The arithmetic complexity of tensor contraction. Theory Comput. Syst.,
58(4):506–527, 2016.

30

[24] A. Cayley. On the theory of the analytical forms called trees. Philos. Mag., 13:172–176, 1857.
[25] A. Cayley. On the analytical forms called trees, part II. Philos. Mag., 18:374–378, 1859.
[26] A. Cichocki, N. Lee, I. V. Oseledets, A. H. Phan, Q. Zhao, and D. P. Mandic. Tensor networks for dimensionality
reduction and large-scale optimization: Part 1 low-rank tensor decompositions. Foundations and Trends in
Machine Learning, 9(4-5):249–429, 2016.
[27] A. Cichocki, A. H. Phan, Q. Zhao, N. Lee, I. V. Oseledets, M. Sugiyama, and D. P. Mandic. Tensor networks for
dimensionality reduction and large-scale optimization: Part 2 applications and future perspectives. Foundations
and Trends in Machine Learning, 9(6):431–673, 2017.
[28] A. Clebsch. Ueber symbolische Darstellung algebraischer Formen. J. Reine Angew. Math., 59:1–62, 1861.
[29] W. Clifford. Extract of a letter to Mr. Sylvester from Prof. Clifford of University College, London. Amer. J.
Math., 1(2):126–128, 1878.
[30] H. Cohn, R. D. Kleinberg, B. Szegedy, and C. Umans. Group-theoretic algorithms for matrix multiplication.
In 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 23-25 October 2005,
Pittsburgh, PA, USA, Proceedings, pages 379–388. IEEE Computer Society, 2005.
[31] H. Cohn and C. Umans. Fast matrix multiplication using coherent configurations. In S. Khanna, editor, Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans,
Louisiana, USA, January 6-8, 2013, pages 1074–1087. SIAM, 2013.
[32] J. W. Cooley and J. W. Tukey. An algorithm for the machine calculation of complex Fourier series. Math. Comp.,
19:297–301, 1965.
[33] R. Curticapean, H. Dell, and D. Marx. Homomorphisms are a good basis for counting small subgraphs. In
H. Hatami, P. McKenzie, and V. King, editors, Proceedings of the 49th Annual ACM SIGACT Symposium on
Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 210–223. ACM, 2017.
[34] P. Cvitanović. Group theory for feynman diagrams in non-abelian gauge theories. Physical Review D, 14:1536–
1553, 09 1976.
[35] P. Cvitanović and A. D. Kennedy. Spinors in negative dimensions. Phys. Scr., 26(1):5–14, 1982.
[36] C. Damm, M. Holzer, and P. McKenzie. The complexity of tensor calculus. Computational Complexity, 11(12):54–89, 2002.
[37] S. Davis and R. Impagliazzo. Models of greedy algorithms for graph problems. Algorithmica, 54(3):269–317, 2009.
[38] F. Eisenbrand and F. Grandoni. On the complexity of fixed parameter clique and dominating set. Theoret.
Comput. Sci., 326(1-3):57–67, 2004.
[39] P. Floderus, M. Kowaluk, A. Lingas, and E. Lundell. Detecting and counting small pattern graphs. SIAM J.
Discrete Math., 29(3):1322–1339, 2015.
[40] F. V. Fomin, D. Lokshtanov, V. Raman, S. Saurabh, and B. V. R. Rao. Faster algorithms for finding and counting
subgraphs. J. Comput. Syst. Sci., 78(3):698–706, 2012.
[41] W. I. Gasarch. The Second P =? NP Poll. SIGACT News Complexity Theory Column, 74, 2012.
[42] J. Håstad. Tensor rank is NP-complete. J. Algorithms, 11(4):644–654, 1990.
[43] C. J. Hillar and L. Lim. Most tensor problems are NP-hard. J. ACM, 60(6):45:1–45:39, 2013.
[44] J. Huang, L. Rice, D. A. Matthews, and R. A. van de Geijn. Generating families of practical fast matrix
multiplication algorithms. In 2017 IEEE International Parallel and Distributed Processing Symposium, IPDPS
2017, Orlando, FL, USA, May 29 - June 2, 2017, pages 656–667. IEEE Computer Society, 2017.
[45] R. Impagliazzo and R. Paturi. On the complexity of k-SAT. J. Comput. Syst. Sci., 62(2):367–375, 2001.
[46] R. Impagliazzo, R. Paturi, and F. Zane. Which problems have strongly exponential complexity? J. Comput.
Syst. Sci., 63(4):512–530, 2001.
[47] A. Itai and M. Rodeh. Finding a minimum circuit in a graph. SIAM J. Comput., 7(4):413–423, 1978.
[48] M. Karppa, P. Kaski, and J. Kohonen. A faster subquadratic algorithm for finding outlier correlations. In
R. Krauthgamer, editor, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 1288–1305. SIAM, 2016.
[49] L. H. Kauffman. Knots, abstract tensors and the Yang-Baxter equation. In Knots, topology and quantum field
theories (Florence, 1989), pages 179–334. World Sci. Publ., River Edge, NJ, 1989.
[50] A. B. Kempe. On the application of Clifford’s graphs to ordinary binary quantics. Proc. London Math. Soc. (2),
17:107–121, 1885/86.
[51] A. B. Kempe. On the application of the Sylvester-Clifford graphs to ordinary binary quantics. (Second part.).
Proc. London Math. Soc. (2), 24:97–118, 1892/93.
[52] T. Kloks, D. Kratsch, and H. Müller. Finding and counting small induced subgraphs efficiently. Inf. Process.
Lett., 74(3-4):115–121, 2000.
[53] T. G. Kolda. Multilinear operators for higher-order decompositions. Technical Report Technical Report
SAND2006-2081, Sandia National Laboratories, Albuquerque, NM, Livermore, CA, 2006.
[54] T. G. Kolda and B. W. Bader. Tensor decompositions and applications. SIAM Rev., 51(3):455–500, 2009.

31

[55] D. Koller and N. Friedman. Probabilistic Graphical Models. Adaptive Computation and Machine Learning. MIT
Press, Cambridge, MA, 2009.
[56] J. B. Kruskal. Three-way arrays: rank and uniqueness of trilinear decompositions, with application to arithmetic
complexity and statistics. Linear Algebra and Appl., 18(2):95–138, 1977.
[57] G. Kuperberg. Involutory Hopf algebras and 3-manifold invariants. Internat. J. Math., 2(1):41–66, 1991.
[58] C.-C. Lam, P. Sadayappan, and R. Wenger. On optimizing a class of multi-dimensional loops with reduction for
parallel execution. Parallel Process. Lett., 7(2):157–168, 1997.
[59] J. M. Landsberg. Tensors: Geometry and Applications, volume 128 of Graduate Studies in Mathematics. American Mathematical Society, Providence, RI, 2012.
[60] J. M. Landsberg, Y. Qi, and K. Ye. On the geometry of tensor network states. Quantum Inf. Comput., 12(34):346–354, 2012.
[61] F. Le Gall. Faster algorithms for rectangular matrix multiplication. In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pages 514–523,
2012.
[62] F. Le Gall. Powers of tensors and fast matrix multiplication. In International Symposium on Symbolic and
Algebraic Computation, ISSAC ’14, Kobe, Japan, July 23-25, 2014, pages 296–303, 2014.
[63] F. Le Gall and F. Urrutia. Improved rectangular matrix multiplication using powers of the CoppersmithWinograd tensor. CoRR, abs/1708.05622, 2017.
[64] J. R. Lee, P. Raghavendra, and D. Steurer. Lower bounds on the size of semidefinite programming relaxations. In
Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland,
OR, USA, June 14-17, 2015, pages 567–576, 2015.
[65] J. Nešetřil and S. Poljak. On the complexity of the subgraph problem. Comment. Math. Univ. Carolin., 26(2):415–
419, 1985.
[66] S. Olariu. Paw-free graphs. Inf. Process. Lett., 28(1):53–54, 1988.
[67] R. Orús. A practical introduction to tensor networks: Matrix product states and projected entangled pair states.
Annals of Physics, 349:117–158, 2014.
[68] V. Y. Pan. Matrix multiplication, trilinear decompositions, APA algorithms, and summation. CoRR,
abs/1412.1145, 2014.
[69] R. Penrose. Tensor Methods in Algebraic Geometry. PhD thesis, St. John’s College, 1956.
[70] R. Penrose. Applications of negative dimensional tensors. In Combinatorial Mathematics and its Applications
(Proc. Conf., Oxford, 1969), pages 221–244. Academic Press, London, 1971.
[71] R. Penrose and W. Rindler. Spinors and space-time. Vol. 1. Cambridge Monographs on Mathematical Physics.
Cambridge University Press, Cambridge, 1984. Two-spinor calculus and relativistic fields.
[72] R. N. C. Pfeifer, J. Haegeman, and F. Verstraete. Faster identification of optimal contraction sequences for tensor
networks. Physical Review E, 90:033315, 2014.
[73] R. Raz. Tensor-rank and lower bounds for arithmetic formulas. J. ACM, 60(6):40:1–40:15, 2013.
[74] J. Richter-Gebert and P. Lebmeir. Diagrams, tensors and geometric reasoning. Discrete Comput. Geom.,
42(2):305–334, 2009.
[75] E. Robeva and A. Seigal. Duality of graphical models and tensor networks. CoRR, abs/1710.01437, 2017.
[76] G. Rote. Division-free algorithms for the determinant and the Pfaffian: Algebraic and combinatorial approaches.
In H. Alt, editor, Computational Discrete Mathematics, Advanced Lectures, volume 2122 of Lecture Notes in
Computer Science, pages 119–135. Springer, 2001.
[77] H. J. Ryser. Combinatorial Mathematics. The Carus Mathematical Monographs, No. 14. Published by The
Mathematical Association of America; distributed by John Wiley and Sons, Inc., New York, 1963.
[78] A. Schrijver. On traces of tensor representations of diagrams. Linear Algebra Appl., 476:28–41, 2015.
[79] E. Solomonik and T. Hoefler. Sparse tensor algebra as a parallel programming model. CoRR, abs/1512.00066,
2015.
[80] E. Solomonik, D. Matthews, J. R. Hammond, J. F. Stanton, and J. Demmel. A massively parallel tensor contraction framework for coupled-cluster computations. J. Parallel Distrib. Comput., 74(12):3176–3190, 2014.
[81] V. Strassen. Gaussian elimination is not optimal. Numer. Math., 13:354–356, 1969.
[82] J. J. Sylvester. On an application of the new atomic theory to the graphical representation of the invariants and
covariants of binary quantics, with three appendices. Amer. J. Math., 1(1 and 2):64–125, 1878.
[83] L. G. Valiant. The complexity of computing the permanent. Theor. Comput. Sci., 8:189–201, 1979.
[84] L. G. Valiant. Holographic algorithms. SIAM J. Comput., 37(5):1565–1594, 2008.
[85] C. Van Loan. Computational Frameworks for the Fast Fourier Transform. SIAM, 1992.
[86] V. Vassilevska Williams. Multiplying matrices faster than Coppersmith-Winograd. In H. J. Karloff and T. Pitassi,
editors, Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY,
USA, May 19 - 22, 2012, pages 887–898. ACM, 2012.

32

[87] V. Vassilevska Williams and R. Williams. Finding, minimizing, and counting weighted subgraphs. SIAM J.
Comput., 42(3):831–854, 2013.
[88] M. J. Wainwright, M. I. Jordan, et al. Graphical models, exponential families, and variational inference. Foundations and Trends R in Machine Learning, 1(1–2):1–305, 2008.
[89] R. Williams. A new algorithm for optimal 2-constraint satisfaction and its implications. Theor. Comput. Sci.,
348(2-3):357–365, 2005.
[90] R. Williams. Faster all-pairs shortest paths via circuit complexity. In D. B. Shmoys, editor, Symposium on Theory
of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 664–673. ACM, 2014.
[91] V. V. Williams, J. R. Wang, R. R. Williams, and H. Yu. Finding four-node subgraphs in triangle time. In P. Indyk,
editor, Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015,
San Diego, CA, USA, January 4-6, 2015, pages 1671–1680. SIAM, 2015.
[92] F. Yates. The Design and Analysis of Factorial Experiments. Imperial Bureau of Soil Science, 1937.

33

APPENDIX
Appendix A. Minimum-cost execution
This appendix summarizes some results on tensor network contractions and minimum-cost executions. These results are not original work, but for the sake of completeness we present them
here.
A.1. Invariance property. In the following lemma, we will show that the tensor of a network is
equal to the tensor of any network that is obtained by a contraction from the original network. In
particular, this implies that any execution gives the same tensor.
Lemma A.1 (Invariance). Let D be a tensor network. For all nonempty W ⊆ V (D) it holds that
T (D) = T (D/W ).
Proof. Let W ⊆ V (D) be nonempty and let i ∈ J(B(D/W )) = J(B(D)). From (25), (26), and
(27), it follows that
X
Y
T (D/W )i =
T (v)ij
j∈J(E(D/W )\B(D/W )) v∈(V (D)\W )∪{w}

X

=

j∈J(E(D/W )\B(D/W ))

=

X

T (v)ij

v∈V (D)\W

Y

T (D[W ])ij

j∈J(E(D/W )\B(D))

=

Y

T (w)ij

T (v)ij

v∈V (D)\W

X

X

Y

j∈J(E(D/W )\B(D)) j 0 ∈J(E(D[W ])\B(D[W ])) w∈W

=

X

X

Y

T (w)ijj 0

Y

T (v)ij

v∈V (D)\W

T (v)ijj 0

j∈J(E(D/W )\B(D)) j 0 ∈J(E(D[W ])\B(D[W ])) v∈V (D)

=

X

Y

j 00 ∈J(E(D)\B(D))

v∈V (D)

T (v)ij 00

= T (D)i .

A.2. The structure of a minimum-cost execution. In this section, we analyze the structure of
a minimum-cost execution. In particular, we will prove Lemma 4.1 that states that each contracted
set has size at most two and also show that one can always contract adjacent vertices in a network.
Lemma 4.1. Let D be a tensor network. There exists a minimum-cost execution of D such that
each contracted set has size at most two. Furthermore, if D is loopless, we can assume that each
contracted set has size exactly two.
Proof. If D contains loops, we may assume that a minimum-cost execution first removes all the
loops by contracting singleton vertices incident to loops. Indeed, the cost of contracting a singleton
vertex is the volume of the tensor associated to it. Since the result of an execution is a single tensor,
then every vertex has to be contained in a contracted set of an execution and none of the edges
incident to a vertex cannot be removed before the vertex is contained in a contracted set. Hence,
the volume of any tensor in the tensor network is a lower bound for the cost of any execution of D
and we may contract singleton vertices.
So let us assume that D is loopless. Suppose that a minimum-cost execution of D contains a
contraction by a set W = {w1 , w2 , . . . , ws } of size at least s ≥ 3, and let w be the new vertex
after this contraction. Then we can replace the contraction by W with two contractions by W 0 =

34

{w1 , w2 , . . . , ws−1 } and W 00 = {w, ws } without increasing the cost of the execution. The cost of
contracting W 0 is less or equal than the cost of contracting W , because every edge incident to W 0
is also incident to W . The cost of contracting W 00 is less or equal than the cost of contracting W ,
because the set of edges incident to w is contained in the set of edges incident to W 0 . We repeat
this procedure until all contracted sets in the execution have size at most two.

Two tensors in a tensor network are called adjacent if they are incident to a common mode.
Lemma A.2 (Execution by contracting adjacent tensors). Let D be a loopless tensor network that
is connected as a hypergraph. Then, there exists a minimum-cost execution of D such that each
contracted set has size two and consists of adjacent vertices.
Proof. Consider a minimum-cost execution of D such that each contracted set has size two; such an
execution exists by Lemma 4.1. If all contracted sets in the execution consist of adjacent vertices,
we are done. Otherwise, consider a contraction of two vertices, u and v, such that u and v are
not adjacent when they are contracted to yield the vertex uv. Consider the steps of the execution
after this contraction step. Let us call such a step a relevant step if it involves a descendant of the
vertex uv. Let us modify the execution as follows. First, delete the contraction of u and v from
the execution. Then, for each relevant step in execution order, replace the descendant of the vertex
uv with the current descendant of either u or v so that the contraction becomes a contraction of
adjacent vertices whenever possible. If the descendants of u and v become adjacent after a relevant
step, contract the descendants of u and v, and then continue the execution without further changes.
Since D is connected, the descendants of u and v must eventually become adjacent.
We will show that this modification of the execution gives again an execution and that it has
cost no larger than the original minimum-cost execution. In the modification of the execution, let
the contraction sets containing u or a descendant of u and not containing a descendant of v be
{u, w1 }, {uw1 , w2 }, . . ., {uw1 . . . ws−1 , ws }; similarly, let the contraction sets containing v or a descendant of v and not containing a descendant of u be {v, z1 }, {vz1 , z2 }, . . ., {vz1 . . . zt−1 , zt }. Here
w1 , . . . , ws , z1 , . . . , zt can be vertices of D or vertices obtained after contraction steps. Contracting
{uw1 . . . ws , vz1 . . . zt } gives the vertex uw1 . . . ws vz1 . . . zt , which appears also in the original execution. Hence, after certain steps the tensor networks in the original execution and in the modification
are the same (after making necessary non-relevant contractions) and the modification of the original
execution is also an execution.
First we consider the cost of contracting {uw1 . . . wi−1 , wi } in the modified execution where
1 ≤ i ≤ s. There exists a j satisfying 1 ≤ j ≤ t such that in the original execution we contract
{uw1 . . . wi−1 vz1 . . . zj , wi }. Then the cost of contracting {uw1 . . . wi−1 , wi } is less or equal that the
cost of contracting {uw1 . . . wi−1 vz1 . . . zj , wi }, because every edge incident to the vertex uw1 . . . wi−1
in the modified execution has to be incident to uw1 . . . wi−1 vz1 . . . zj in the original execution. Otherwise, there would be an edge in D that is incident only to vertices in {u, w1 , . . . , wi−1 , v, z1 , . . . , zj },
and in particular both to vertices in {u, w1 , . . . , wi−1 } and in {v, z1 , . . . , zj }. This is impossible, because then uw1 . . . wi−1 and vz1 . . . zj would be adjacent vertices in the modified execution, but by
assumption uw1 . . . ws and vz1 . . . zt are the first adjacent descendants of u and v in the modified
execution. Similarly, we can show that the cost of contracting {vz1 . . . zj−1 , zj } in the modified
execution for 1 ≤ j ≤ t is less than the cost of contracting a set in the original execution.
Second we consider the cost of contracting {uw1 . . . ws , vz1 . . . zt } in the modified execution. Without loss of generality, we can assume that in the original execution the vertex uw1 . . . ws vz1 . . . zt
is obtained from contracting {uw1 . . . ws vz1 . . . zt−1 , zt }. We will show that the cost of contracting {uw1 . . . ws , vz1 . . . zt } in the modified execution is less or equal than the cost of contracting
{uw1 . . . ws vz1 . . . zt−1 , zt } in the original execution. Indeed, every edge incident to uw1 . . . ws in
the modified execution is incident to uw1 . . . ws vz1 . . . zt−1 in the original execution, because otherwise there would be an edge in D that is incident only to vertices in {u, w1 , . . . , ws , v, z1 , . . . , zt−1 },
and in particular both to vertices in {u, w1 , . . . , ws } and {v, z1 , . . . , zt−1 }. However, by assumption

35

uw1 . . . ws and vz1 . . . zt are the first adjacent descendants of u and v in the modified execution. Similarly, every edge incident to vz1 . . . zt in the modified execution is incident to uw1 . . . ws vz1 . . . zt−1
or zt in the original execution, because otherwise there would be an edge in D that is incident only
to vertices in {u, w1 , . . . , ws , v, z1 , . . . , zt−1 }, and in particular both to vertices in {u, w1 , . . . , ws } and
{v, z1 , . . . , zt−1 }. This contradicts that uw1 . . . ws and vz1 . . . zt are the first adjacent descendants
of u and v in the modified execution.
The modified execution consists of at least one less contraction of nonadjacent vertices. Repeating
this procedure until there are no contractions of nonadjacent vertices completes the lemma.

A.3. Finding a minimum-cost execution. In this section, we will show a recurrence relation for
the cost of a tensor network. To this end, let D be a loopless connected tensor network D with at
least two tensors. Let us write C (D) for the set of all W ⊆ V (D) such that D[W ] is connected.
Lemma A.3. Let D be a loopless connected tensor network D with at least two tensors. The cost
of D satisfies the recurrence

(48)
c(D) =
min max c(D[W ]), c(D[V (D) \ W ]), c(D/W/(V (D) \ W )) .
W ∈C (D)
V (D)\W ∈C (D)

Proof. We recall that the cost c(D) of D is the cost of minimum-cost execution of D. We can
view a minimum-cost execution of D as a rooted tree such that the root has degree two, all nonroot internal nodes have degree three, and each leaf node is a tensor of D. By Lemma A.2, the
two subtrees rooted at the neighbours of the root define two disjoint sets U, W ⊆ V (D) such that
U ∪ W = V (D) and both D[U ] and D[W ] are connected. The cost of the contraction at the root
is c(D/W/U ), and the subtrees rooted at U and W cost c(D[U ]) and c(D[W ]), respectively. The
recurrence considers all the partitions to connected sets, including the optimum.


