%% Theory of Computing
%% File: v018a016.tex
%% Publication date: June 22, 2022
%% Authors: Per Austrin, Petteri Kaski, and Kaie Kubjas

%

%
%
%
%

%

%

%
%

%

%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%

%

\documentclass{toc}

%
%
%
\tocdetails{%
  title = {Tensor Network Complexity of Multilinear Maps},
%
%
%
%
%
  number_of_pages = {54},
  number_of_bibitems = {104},
  number_of_figures = {2},
  conference_version = {ITCS19}, %
    %
    %
%
%
%
  author = {Per Austrin, Petteri Kaski, and Kaie Kubjas},
    %
    %
    %
  authorlist = {Per Austrin, Petteri Kaski, Kaie Kubjas},
    %
    %
    %
    %
    %
    %
    %
%
%
  %
  %
  %
  %
%
  acmclassification = {F.1.1, F.2.2, G.2.1, G.2.2},
    %
    %
    %
    %
    %
    %
    %
    %
    %
    %
  amsclassification = {15A69, 68Q17, 68Q25, 68W05, 05C85, 14Q20},
    %
    %
    %
    %
    %
    %
    %
    %
    %
    %
keywords = {arithmetic complexity, lower bound, multilinear map, tensor network},
    %
    %
    %
    %
    %
}   %

    %
    %
    %
    %
    %
    %
    %
    %
    %
    %
    %
    %
    %
    %
    %
    %
    %
    %
    %
    %
    %
    %
    %
    %
    %
    %
    %
    %
    %

%
%
\tocdetails{%
volume = 18,
number = 16,
year = 2022,
%
%
%
%
%
%
%
received = {November 28, 2018},
revised = {December 20, 2020},
published = {June 22, 2022},
%
%
doi = {10.4086/toc.2022.v018a016},
%
}   %

%
%
%
%
\usepackage{caption,subcaption}
\usepackage{microtype}
\usepackage[super]{nth}
\usepackage{mathrsfs}
\usepackage{thm-restate}
\usepackage{todonotes}
\usepackage{mathtools}

%
%
%

%

\DeclareMathOperator{\bw}{bw}
\DeclareMathOperator{\tw}{tw}

\newcommand{\g}{\ensuremath{\chi}}
\newcommand{\bra}{\ensuremath{\langle}}
\newcommand{\ket}{\ensuremath{\rangle}}
\newcommand{\sgn}{\ensuremath{\operatorname{sgn}}}
\newcommand{\per}{\ensuremath{\operatorname{per}}}
\newcommand{\tr}{\ensuremath{\operatorname{tr}}}
\newcommand{\rk}{\ensuremath{\operatorname{rk}}}
\newcommand{\Sym}{\ensuremath{\operatorname{Sym}}}
\newcommand{\F}{\ensuremath{\mathbb{F}}}

\newcommand{\ts}{\ensuremath{\mathcal{T}_S}}
\newcommand{\td}{\ensuremath{\mathcal{T}_D}}
\newcommand{\tdk}{\ensuremath{\mathcal{T}_{D^{\otimes k}}}}

\makeatletter
\newcommand{\slimfigure}[3]{%
	\@fleqnfalse
    \begin{equation}
    \begin{aligned}
      \label{fig:#3}
      \includegraphics[scale=#1]{#2}
    \end{aligned}
  \end{equation}
}
\makeatother


\begin{document}

\begin{frontmatter} %

%
%

%
%

%
\title{Tensor Network Complexity of Multilinear Maps
    \titlefootnote{An extended abstract of this paper appeared in
      the \href{https://drops.dagstuhl.de/opus/portals/lipics/index.php?semnr=16098}{Proceedings of the 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)} \cite{conf-version}.}}

%
%
%
%
%
%
%
%
%
%
%
%


%
%
%
%

%

\author[austrin]{Per Austrin\thanks{Supported by the Swedish Research Council, Grant 621-2012-4546 and the Approximability and Proof Complexity project funded by the Knut and Alice Wallenberg Foundation.}}
\author[kaski]{Petteri Kaski\thanks{Supported by the European Research Council, Grant 338077.}}
\author[kubjas]{Kaie Kubjas\thanks{Supported by the European Union's Horizon 2020 research and innovation programme: Marie Sk\l{}odowska-Curie Grant 748354, research carried out at LIDS, MIT and Team PolSys, LIP6, Sorbonne Universit\'e.}}

%
%
%
%

%
%
%
%
%
%
\begin{abstract}
  We study \emph{tensor networks} as a model of arithmetic computation for
  evaluating multilinear maps.
  These capture any algorithm based on low-rank tensor decompositions, such as $O(n^{\omega+\epsilon})$ time matrix multiplication, and in addition many other algorithms such as $O(n \log n)$ time discrete Fourier transform and $O^*(2^n)$ time for computing the permanent of a matrix.
  However,  %
  tensor networks sometimes yield faster algorithms than those
  that follow from low-rank decompositions.  For instance the
  fastest known $O(n^{(\omega +\epsilon)t})$ time algorithms for
  counting $3t$-cliques can be implemented with tensor networks, even
  though the underlying tensor has rank $n^{3t}$ for all $t \ge 2$.
  For counting homomorphisms of a general pattern graph $P$ into a host graph on $n$ vertices we obtain an upper bound of $O(n^{(\omega+\epsilon)\bw(P)/2})$ where $\bw(P)$ is the branchwidth of $P$. This essentially matches the bound for counting cliques, and yields small improvements over previous algorithms for many choices of $P$.

  While powerful, the model still has limitations, and we are able to
  show a number of unconditional lower bounds for various multilinear maps,
  %
  including the following.  %
  \begin{enumerate}
  \item[(a)] %
  An  %
$\Omega(n^{\bw(P)})$ time lower bound for counting homomorphisms from $P$ to an $n$-vertex graph, matching the upper bound if $\omega = 2$.
    In particular for $P$ a $v$-clique this yields an $\Omega(n^{\lceil 2v/3 \rceil})$ time lower bound for counting $v$-cliques, and for $P$ a $k$-uniform $v$-hyperclique we obtain an $\Omega(n^v)$ time lower bound for $k \ge 3$, ruling out tensor networks as an approach to obtaining non-trivial algorithms for hyperclique counting and the Max-$3$-CSP problem.

  \item[(b)] %
   An  %
$\Omega(2^{0.918n})$ time lower bound for the
    determinant and the %
    permanent of an $n \times n$ matrix.

  \end{enumerate}
\end{abstract}

\iffalse %
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%

\tocarxivcategory{cs.CC,cs.DS}

\fi %

\end{frontmatter}

%
%
%

\section{Introduction}

\noindent
One of the cornerstones of the theory of computation is the study of efficient
algorithms:
\begin{quote}
For a function $f$, how much time is required to evaluate $f$ on given inputs?
\end{quote}
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 \cite{Gasarch2012,Impagliazzo2001,Impagliazzo2001b}.
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
\begin{enumerate}%
\item
general enough to capture the fastest-known algorithms for
$f$, and
\item
restricted enough to admit proofs of strong \emph{unconditional} time
lower bounds for $f$.
\end{enumerate}
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, \eg, \cite[Ch. 14]{AroraB2009})  %
to models of algorithm-design principles such as greedy algorithms,
backtracking, or dynamic programming
\cite{AlekhnovichBBIMP2011,DavisI2009}, to linear or semidefinite
programming relaxations for hard combinatorial optimization problems
\cite{LeeRS2015}.

\subsection{Multilinear maps}

One class of functions $f$ that are of substantial importance is the family of \emph{$\ell$-linear maps} (\emph{multilinear maps}) from $\ell$ input vector spaces to an output vector space.%
\footnote{Multilinear maps with $\ell=1$ are called \emph{linear}, $\ell=2$ \emph{bilinear}, $\ell=3$ \emph{trilinear}, and so forth.}{}
Examples range from maps of known near-linear-time complexity in the input size, such as the discrete Fourier transform~\cite{CooleyT1965,VanLoan1992}, to maps without known polynomial-time-complexity algorithms, such as the permanent of a matrix~\cite{Ryser1963,Valiant1979}. 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~\cite{AbboudBW15a,BjorklundHKK2008,BjorklundHK2009,EisenbrandG2004,ItaiR1978,Nesetril1985,Williams2005,Williams14apsp}.

In this paper, we study the \emph{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 $\ell$-linear map from $\ell$ vector spaces
of dimension $n$ to a scalar requires $\Omega(n^\ell)$ 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 \emph{tensor networks} on hypergraphs 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.


\subsection{Tensor networks}

\label{sect:nets}

Tensor networks have a long and rich history which can be traced as
far back as \nth{19}-century studies in invariant theory due
to Cayley~\cite{Cayley1875,Cayley1879}, Clebsch~\cite{Clebsch1861},
Clifford~\cite{Clifford1878}, Sylvester~\cite{Sylvester1878},
and Kempe~\cite{Kempe1885,Kempe1892}.
Tensor networks are extensively deployed in applications from pure mathematics
and theoretical physics~\cite{Kauffman1989,Kuperberg1991,Landsberg2012,LandsbergQY2012,Penrose1956,Penrose1971,RichterGebertL2009,Schrijver2015a} to computational physics and chemistry~\cite{Orus2014,PfeiferHV2014,SolomonikMHSD2014}.
In theoretical computer science,
they appear in various guises,  %
including, for example,
in the Holant framework \cite{Valiant2008,CaiLX2011,CaiGW2016a},
in the study of probabilistic graphical models~\cite{KollerF2009,RobevaS2017},
in the study of parallel programming~\cite{SolomonikH2015},
in the study of quantum computing~\cite{ItaiL2010},
and in the study of arithmetic
complexity~\cite{BeaudryH2007,CapelliDM2016,DammHM2002}.
Tensor contraction is also emerging as a basic
computational primitive in computer
hardware~\cite{JouppiYPPABBBBB17,MarkidisCLPV18}.
(See \expref{Section}{sec:related work} for a detailed discussion.)
As the precise definitions are somewhat technical, let us start with
a few simple motivating examples and then state our results,
with the understanding that precise definitions appear
in \expref{Section}{sec:tensor network defs}.

In our setting, a tensor network is a hypergraph in which the vertices are
tensors and the hyperedges are called \emph{modes}.
Each mode that is incident to a tensor defines a ``dimension''
for indexing the entries of the tensor---for example, a matrix is a tensor
that is incident to two modes, one mode for the rows of the matrix, and
the other mode for the columns of the matrix. A network may be simplified
by a sequence of \emph{contractions}, where each contraction takes a subset
of tensors and replaces it with a single tensor whose entries are obtained
as generalized inner products of the entries of the tensors being contracted.

As a concrete first example of these concepts, let us consider the task of
multiplying two matrices, $A$ and $B$. More specifically, let
$A$ be a matrix with rows indexed by mode $i$ and
columns indexed by mode $k$, and let $B$ be a matrix
with rows indexed by mode $k$ and columns indexed by mode $j$.
We may represent the multiplication task as
the tensor network depicted on the left in \eqref{fig:intro matrix mul 1}.
The result of contracting $A$ and $B$ is a new
matrix with rows indexed by $i$ and columns indexed by $j$, where the
entry at each position $(i,j)$ is $\sum_k A_{ik} B_{kj}$.  If the three
index sets all have size $n$, then computing $A \cdot B$ by contracting
them in such a direct manner uses $\Theta(n^3)$ operations.  To obtain
faster matrix multiplication, we can rewrite the bare-bones network
on the left in \eqref{fig:intro matrix mul 1} using a low-rank
decomposition of the matrix multiplication tensor.
For example, Strassen's decomposition~\cite{Strassen1969}
of $2 \times 2$ matrix multiplication
can be represented using the second network in \eqref{fig:intro matrix mul 1}.
Note that the index $i$ used by $A$ and the result has been separated into
two distinct indices $i$ and $i'$, and similarly for $j$ and $k$.
\slimfigure{0.9}{figures/intro_matrixmul1}{intro matrix mul 1}

We can \emph{execute} the network by successively contracting
groups of vertices.  In \eqref{fig:intro matrix mul 2} we see the
process of successively contracting pairs of tensors in a carefully
chosen order, until only a single tensor---the result of the
computation---remains.  Such an execution can be naturally
represented by a rooted binary tree, as shown on the right in
\eqref{fig:intro matrix mul 2}, where the tensors of the network form
the leaves, and each internal node represents the result of
contracting its two children.  To summarize, a tensor-network
algorithm is specified by providing (a) a tensor network that when
contracted yields the desired result, \emph{and} (b) an execution tree
indicating the order in which to contract tensors in the network.

\slimfigure{0.74}{figures/intro_matrixmul2}{intro matrix mul 2}

The \emph{cost} of performing one of the contractions in an execution
is the product of the lengths of the modes used by any tensor involved
in the contraction.  This simply measures (up to a constant factor)
the number of arithmetic operations (additions/multiplications) used
to compute the result by a direct, na\"\i{}ve computation that does not
depend on the values of the tensors.  For example, the contraction of
$\alpha$ and $A$ in the first step of \eqref{fig:intro matrix mul 2}
has cost $28$ because it involves the three modes $i'$ (length $2$),
$k$ (length $2$) and $\ell$ (length $7$).

We observe that cost is data-oblivious---the tensor $\alpha$ is fixed with many
zero-entries but these entries still contribute to the cost.  Indeed, in many cases there may be faster ways of evaluating a contraction than to evaluate it naively, and just like we saw above, this can often be dealt with by rewriting the network appropriately.
For instance, consider now the multiplication of two $2^k \times 2^k$
matrices.  Because the family of matrix multiplication tensors is closed under
Kronecker products, this operation may be computed by a tensor
network like the one shown in \eqref{fig:intro matrix mul 3}
(depicting the case $k=5$), where $\alpha$, $\beta$ and $\gamma$ are
as in \eqref{fig:intro matrix mul 2}.  The rows/columns of the
matrices are now indexed by $k$-tuples of bits.  A cost-efficient execution of this
network successively contracts tensors in the order shown to the right in \eqref{fig:intro matrix mul 3}.  In this execution, the first contraction of $A$
with the first $\alpha$ block has a cost of $2^k \cdot 2^k \cdot 7$,
and results in a tensor of size $2^{k-1} \times 2^{k-1} \times 7$.
Then the contraction with the next $\alpha$ block has a cost of $2^{k-1} \cdot 2^{k-1} \cdot
7^2$ and produces a result of size $2^{k-2} \times 2^{k-2} \times 7
\times 7$, and so on, until the contraction with the last $\alpha$
block which has a cost of $2 \cdot 2 \cdot 7^k = O(7^k)$.  The contractions with the $\beta$ and $\gamma$ blocks behave similarly.  Thus all the
$\Theta(k)$ contractions in the execution have cost bounded by $O(7^k)$, meaning that
we get a total running time of $O(k 7^k) = O(N^{\log_2 7} \log N)$ for
$N \times N$ matrices.%
\footnote{In fact, a more careful analysis gives running time $O(N^{\log_2 7})$.}{}
\slimfigure{0.65}{figures/intro_matrixmul3}{intro matrix mul 3}

This type of argument can capture any algorithm based on a low-rank
decomposition of the underlying tensor of the multilinear map, and
indeed, this enables $O(n^\omega)$-time\footnote{Throughout the paper,
we write  
%
%
  $\omega(h) = \omega_{\F(h)}$    %
for the infimum over all $t$
such that the arithmetic complexity of multiplying an
$n \times \lfloor n^h\rfloor$ matrix with an $\lfloor n^h\rfloor\times n$
matrix is $O(n^t)$ where $h>0$ is a constant.
While the value of $\omega(h)$ may depend on the underlying
field $\F$, we tacitly ignore this, since the field is fixed throughout
the paper. Also, we write simply $\omega=\omega(1)$ for the exponent
of square matrix multiplication. For all fields it is known that
$2\leq\omega<2.37286$~\cite{AlmanVW2021,LeGall2014,VassilevskaWilliams2012};
for the state of the art on $\omega(h)$,
%
see~\cite{LeGallU2017}.}{} %
 matrix multiplication
using tensor networks.
Beyond simple low-rank decompositions, which always give rise to
``star-like'' networks as in \eqref{fig:intro matrix mul 3}, there are
many interesting algorithms that can be captured using networks with a
more complicated topology.
For instance, 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 $2^k$, 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~\cite{CooleyT1965,VanLoan1992}.

\subsection{Our results}
\label{sect:our}

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 powerful enough to capture a substantial number of higher-linearity
applications, including Ryser's algorithm for matrix permanent \cite{Ryser1963},
and the \emph{Kruskal operator}~\cite{Kolda2006,Kruskal1977}
(see~\expref{Section}{sect:kruskal}), %
which underlies realization of rank-decompositions for tensor rank
\cite{Kolda2009} and current fastest algorithms for detecting outlier
correlations~\cite{KarppaKK2018}.

One problem for which tensor networks turn out to be particularly useful
is counting homomorphisms from a fixed pattern graph $P$ to
a large host graph $G$ on $n$ vertices.  The most well-studied such problem
is when $P$ is a $k$-clique.  For this problem, the currently fastest
algorithms run in time roughly $O(n^{\omega k/3})$
\cite{Nesetril1985,EisenbrandG2004}.  For general $P$, it is known
that the problem can be solved in $O(n^{\tw(P)+1})$ time
\cite{DiazST02}, where $\tw(P)$ is the treewidth of $P$.
We show that tensor networks can solve the problem in $O(n^{(\omega+\epsilon)
  \bw(P)/2})$ time, where $\bw(P)$ is the \emph{branchwidth} of $P$.
When $P$ is a $k$-clique, we have $\bw(P) = \lceil 2k/3\rceil$; if $\omega = 2$,
the running time coincides with that of the currently fastest algorithms.
On the other hand, if $\omega > 2$, we can slightly improve upon this to recover the
currently fastest known running time of
Eisenbrand and Grandoni \cite{EisenbrandG2004} relying on fast rectangular matrix multiplication.
In the case of general $P$, the bound $O(n^{(\omega+\epsilon) \bw(P)/2})$ improves
on the treewidth-based bound for graphs with $\bw(P) \le
2(\tw(P)+1)/\omega$ (and in particular if $\omega=2$ it is always as
fast as the treewidth-based bound, ignoring the $\epsilon$).  By
recent results of Curticapean, Dell, and Marx~\cite{CurticapeanDM2017},
fast algorithms for homomorphism-counting can be used to obtain fast
algorithms for counting subgraphs of $G$ isomorphic to $P$, and in
some cases our new branchwidth-based bound leads to an improvement;
for example, for counting paths %
of length $7$, $8$ or $9$,
we get a running time of $O(n^{3\omega/2+\epsilon}) < O(n^{3.56})$
compared to $O(n^{4})$ using the treewidth-based bound, whereas for very long
paths it is not clear whether we would need $\omega=2$ in order for
%
this bound %
to improve on the treewidth-based bound. Previous work
that combines branch decompositions and fast matrix
multiplication includes Dorn~\cite{Dorn2006} and
Bodlaender~\emph{et~al.}~\cite{BodlaenderLRV2010}.

Further applications
captured by tensor networks are the set covering and set partitioning
frameworks via fast zeta and M\"obius transforms that underlie the
current fastest algorithms for graph coloring~\cite{BjorklundHK2009}
and its generalizations such as computing the
Tutte polynomial~\cite{BjorklundHKK2007,BjorklundHKK2008}.
To summarize, we have the following compendium
%
of upper bound results.
For the detailed definitions of the relevant multilinear maps,
%
%
see \expref{Sections}{sect:examples} \expref{and}{sec:upper bounds}. %

\begin{theorem}
  \label{thm:upper bounds}
  We have the following upper bounds on arithmetic complexity via tensor
networks. %
  \begin{enumerate}
  \item $O(n^{\omega(h) + \epsilon})$ for the multiplication of matrices of shape $n \times \lfloor n^h \rfloor$ and $\lfloor n^h \rfloor \times n$
where $h > 0$ is a constant. %
%
  \item $O(n^{(\omega+\epsilon) \bw(P)/2})$ for counting homomorphisms of a fixed pattern hypergraph $P$ into a hypergraph on $n$ vertices.
  \item $O(n^{\beta + \epsilon})$ for counting $v$-cliques in an $n$-vertex graph, where $\beta$ is the exponent of the complexity of multiplying matrices of shape $n^{\lfloor v/3 \rfloor} \times n^{\lfloor (v+1)/3 \rfloor}$ and $n^{\lfloor (v+1)/3 \rfloor} \times n^{\lfloor (v+2)/3 \rfloor}$.
  \item $O(\max(n^{\lceil\ell/2\rceil(\omega+\epsilon-1)}r,\,n^{2\lceil\ell/2\rceil}r^{\omega+\epsilon-2}))$ for the Kruskal operator of $\ell$ matrices of shape $n\times r$.
  \item $O(2^k k)$ for the discrete Fourier transforms for the Abelian groups $\Z_{2^k}$ and $\Z_2^k$.
  \item $O(2^kk)$ for group algebra products on $\F[\Z_{2^k}]$ and $\F[\Z_2^k]$ when $2$ is unit in $\F$.
  \item $O(2^kk)$ for the semigroup algebra product on $\F[(\{0,1\}^k,\subseteq,\cap,\cup)]$.
  \item $O(2^n n)$ for the permanent of an $n \times n$ matrix.
  \end{enumerate}
Above $\epsilon>0$ is an arbitrary constant.
\end{theorem}


Perhaps the most interesting application above
is the $v$-clique problem, which suggests that one should seek to
pursue generalizations to $v$-vertex hypercliques of
$\binom{v}{k}$ hyperedges with $v>k\geq 3$.
Indeed, subgraph counting is a problem that has received substantial
interest over the years (\eg, \cite{%
ItaiR1978,%
Nesetril1985,%
AlonYZ1997,%
AlonG2010,%
EisenbrandG2004,%
BjorklundHKK2009,%
BjorklundKK2014,%
WilliamsWWY15,%
WilliamsW2013,%
FominLRSR2012,%
FloderusKLL2015,%
Olariu1988,%
KloksKM2000,%
CurticapeanDM2017}), 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~\cite{AbboudBBK2017,AbboudBW15a}.
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 constraint satisfaction problems (Max-CSP) for
constraints of width $k\geq 3$; 
see Williams~\cite{Williams2005} %
for
the case $k=2$. One of the main goals of our subsequent lower bounds is
to rule out tensor networks as %
candidates  %
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 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~\cite{Raz2013} shows that multilinear formulas cannot compute
the
determinant of an $n\times n$ matrix in a polynomial number of operations
in $n$, even though polynomial-size general circuits are known for
the determinant 
%
%
%
(see \cite{Berkowitz1984,BunchH1974,Csanky1976,Rote2001}). 
%

It turns out that considerably stronger lower bounds can be shown
for tensor networks. In particular, we establish
%
%
%
%
lower bounds for arithmetic complexity via tensor
networks of $P$-homomorphism counting and the Kruskal operator.
%
%
%
%
These lower bounds are tight 
%
under the assumption $\omega=2$. %
%
Furthermore, we rule out the possibility of any
nontrivial algorithm designs via tensor networks f
or counting cliques in hypergraphs.
The following theorem collects our main lower-bound results, 
and should be contrasted with the upper bounds
in \expref{Theorem}{thm:upper bounds}.

\begin{theorem}
  \label{thm:lower bounds}
  We have the following lower bounds on arithmetic complexity via tensor networks.  %
  \begin{enumerate}
  \item $\Omega(n^{\bw(P)})$ for the multilinear form corresponding to $P$-homomorphism counting.  In particular, this yields a lower bound of $\Omega(n^{\lceil 2v/3 \rceil})$ for counting cliques of size $v$, and a lower bound of $\Omega(n^v)$ for counting hypercliques of size $v$.
  \item $\Omega(\max(n^\ell, n^{\lceil \ell/2\rceil}r))$ for the Kruskal operator of $\ell$ matrices of shape $n\times r$.
  \item $\Omega(\binom{n}{n/3})$ for the determinant 
%
and the %
permanent of an $n \times n$ matrix.
  \end{enumerate}
\end{theorem}

We remark that \cite{LincolnWW18} independently showed that the rank of the $v$-hyperclique tensor is $\Omega(n^v)$; our $\Omega(n^v)$ lower bound for tensor networks strengthens that.
One may wonder about the gap between the bounds of
$\Omega(\binom{n}{n/3})$ and $O(2^n n)$ for the permanent.
As we explain below, our lower bound methods are inherently rank-based
and cannot go beyond $\binom{n}{n/3}$.  A curious point is that it is 
not immediately clear whether tensor networks can even achieve 
$O^*(2^n)$ time for the determinant, and we do not know whether
%
this is possible.


\subsection{Overview of proof ideas}

\label{sect:ideas}

As a running example in this overview, we consider the $6$-linear
%
%
form  %
$A: \F^{[n] \times [n]} \times \F^{[n] \times [n]} \times \ldots
\times \F^{[n] \times [n]} \rightarrow \F$
%
%
that takes as input $6$ matrices of size $n \times n$ and is
defined by the equation  %
\begin{equation}
\label{eq:overview form}
A(X^{(1)}, X^{(2)}, X^{(3)}, X^{(4)}, X^{(5)}, X^{(6)}) = \sum_{i, j, k, \ell \in[n]} X^{(1)}_{ij} X^{(2)}_{ik} X^{(3)}_{i\ell} X^{(4)}_{jk} X^{(5)}_{j\ell} X^{(6)}_{k\ell}\,.
\end{equation}
If $\chi$ is the adjacency matrix of a loopless graph $G$, then $A(\chi, \chi, \chi, \chi, \chi,
\chi)$ counts the %
$4$-cliques in the graph.  Associated with $A$ is the $6$-tensor $T(A)$ of size $n^2 \times n^2 \times \cdots \times n^2$, where each of the $6$ modes is indexed by a pair $(i, j) \in [n] \times [n]$, 
and the value at a given position is the coefficient of the corresponding
term in $A$.  Concretely,
\[
%
%
%
%
%
T(A)_{i_1j_1, i_2k_2, i_3\ell_3, j_4k_4, j_5\ell_5, k_6\ell_6} =
\begin{cases}
  1 & \!\!\! \text{if $i_1 = i_2 = i_3$ and $j_1 = j_4 = j_5$ and}\\
  & \!\!\! \text{$\,\,\,\,\,\,\,\, k_2 = k_4 = k_6$ and $\ell_3 = \ell_5 = \ell_6$},\\
  0 & \!\!\! \text{otherwise}.
\end{cases}
\]

\paragraph*{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 \eqref{eq:overview form} for an $n$-vertex
graph and its associated tensor $T(A)$.  Then for any
$k \ge 1$, the tensor associated with the $4$-clique counting form in
$n^k$-vertex graphs is $T(A)^{\otimes k}$, the $k$-fold Kronecker
product of $T(A)$ with itself.  We write $A^{\otimes 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^{\otimes k}$.

We give such a construction, and show that the cost of the best tensor
network execution for $A^{\otimes k}$ is essentially submultiplicative
in a quantity that we call the \emph{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 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 \expref{Section}{sec:submultiplicativity}.
Our general upper bound for the cost of $A^{\otimes k}$ can, somewhat
informally, be stated as follows.

\begin{restatable}[Submultiplicativity of cost, informal statement]{theorem}{GeneralUpperBoundTheorem}
  \label{thm:general upper bound}
  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^{\otimes k}$ has a tensor network
  execution consisting of at most $k \cdot s$ steps, each with cost at
  most $a^{k-1} \cdot c$.
\end{restatable}

An immediate corollary of this is that we can capture any algorithm
for $A^{\otimes k}$ based on a low-rank decomposition of $T(A)$
(\expref{Corollary}{cor:low rank execution}).  For example, this implies that
tensor networks can multiply $n \times n$ matrices in $O(n^{\omega +
  \epsilon})$ time (\expref{Section}{sec:matrix mul upper bound}).

However, returning to our running example form \eqref{eq:overview
  form}, as we explain below the tensor $T(A)$ has rank $n^4$, meaning
that \expref{Corollary}{cor:low rank execution} only yields a trivial upper bound.
This is where the full generality of \expref{Theorem}{thm:general upper bound}
comes in.  Consider the form \eqref{eq:overview form} for graphs on
some constant number $n_0$ of vertices.  As it turns out, we can design
a network and an associated execution for this form, depicted
in \eqref{fig:overview 4 choose 2 execution},
with an execution of cost $n_0^{2e+3}$ and amortized cost
$n_0^{e+1}$, where $n_0^e$ is the rank of the tensor associated with
$n_0 \times n_0$ matrix multiplication.  Picking $n_0$ to be a large
enough \emph{constant} so that
$e$ is approximately $\omega$, and letting $k$ be such that $n$ is
approximately $n_0^k$, we obtain via \expref{Theorem}{thm:general upper bound} an
$O(n^{\omega +\epsilon + 1})$ time upper bound for \eqref{eq:overview form}.\footnote{This bound is the running time of the algorithm of Ne{\v{s}}et{\v{r}}il
and Poljak \cite{Nesetril1985} for counting $4$-cliques, which if $\omega > 2$ is slightly worse than the running time of \expref{Theorem}{thm:upper bounds}.}
\slimfigure{0.75}{figures/intro_4choose2}{overview 4 choose 2 execution}

\paragraph*{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 \emph{rank} of $T(A)$,
we \emph{flatten} it to a matrix and analyze the rank of that
matrix.  There are $2^5$ 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 from \eqref{eq:overview form}, the rank of
$T(A) = n^4$.  That this is an upper bound follows from
\eqref{eq:overview form}, 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 four variables as column indices.
The resulting $n^4 \times n^8$ 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 vertices have degree $3$.  We call this a \emph{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 tensor network execution, we minimize this quantity over all
possible socket trees.  We refer to the resulting quantity as the
\emph{socket width} of $A$, denoted $w(A)$ (formal definition appears in \expref{Section}{sec:general lower bound}).  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 \expref{Section}{sec:map cost}).

\begin{restatable}{theorem}{GeneralLowerBoundTheorem}
  \label{thm:general lower bound}
  For every multilinear map $A$, it holds that $c(A) \ge w(A)$.
\end{restatable}

Indeed, for our running example \eqref{eq:overview form}, there are
low-width socket trees establishing $w(A) \le n^3$, see
\eqref{fig:overview socket tree}.  However, that bound is tight: our
$\Omega(n^{\lceil 2 \cdot 4 / 3 \rceil}) = \Omega(n^3)$ lower bound
for the $\binom{4}{2}$-linear form (\expref{Theorem}{thm:lower bounds})
is obtained by proving $w(A) \ge n^3$ (\expref{Lemma}{lem:lb-binom-2}) and
appealing to \expref{Theorem}{thm:general lower bound}.
\slimfigure{1.0}{figures/intro_4choose2_tree}{overview socket tree}

\vspace{-0.5cm}


\subsection{Earlier and related work}
\label{sec:related work}

We now proceed to a more detailed discussion of earlier work.

\paragraph*{Tensor networks}

The history of tensor networks
(or, alternatively, \emph{tensor diagrams} or \emph{diagrams}) as
an analytical and computational tool goes back to the \nth{19}-century to
%
%
the work of %
Cayley~\cite{Cayley1875,Cayley1879}, Clebsch~\cite{Clebsch1861},
Clifford~\cite{Clifford1878}, Sylvester~\cite{Sylvester1878},
and Kempe~\cite{Kempe1885,Kempe1892}. The diagrammatic form used here can be
traced back to Penrose~\cite{Penrose1971}. Some early appearances of tensor
diagrams are by Cvitanovi\`c~\cite{Cvitanovic1976},
Cvitanovi\`c and Kennedy~\cite{CvitanovicK1982},
Kuperberg~\cite{Kuperberg1991}, and many others. Surveys of tensor
diagrams are given by Penrose and Rindler~\cite{PenroseR1986a} and
by Landsberg~\cite{Landsberg2012}. Schrijver~\cite{Schrijver2015a} provides
a brief historical account.

Deviating from Penrose’s notation, we work 
%
relative to a fixed 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 hyperedges designated to form the
boundary of the network
(see~\expref{Section}{sec:tensor network defs} %
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 \emph{vertices} (tensors) rather than as contractions of
hyperedges (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, \eg, in
Penrose's %
paper~\cite{Penrose1971}.  %

A large body of existing work in applications
(see \expref{Section}{sect:nets}) %
studies
how to efficiently execute a \emph{given} tensor network $D$.
Our quest in this paper differs from such
%
investigations  %
in that
we %
take  %
a multilinear map $A$, and seek to
\emph{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~\expref{Theorem}{thm:upper bounds}
and~\expref{Theorem}{thm:lower bounds} are over all tensor networks that 
realize a particular map $A$ of interest.

\paragraph*{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\aa{}stad~\cite{Hastad1990} showed that computing the rank of
an explicitly given $\ell$-tensor is NP-complete over finite fields
and NP-hard over rationals whenever $\ell\geq 3$. Hillar and Lim extended the latter result to any field containing $\mathbb{Q}$~\cite{HillarL2013}. They also showed that many other tensor problems such as the eigenvalue, singular value and spectral norm decision and approximation problems as well as
the  %
rank-1 approximation problem for 3-tensors (over $\mathbb{R}$ and in some cases over $\mathbb{C}$) are NP-hard.

The task of finding the value of a given scalar-valued tensor network
is known to be $\#$P-complete (see, \eg, 
\cite{BacchusDP2003,BiamonteMT2015}).
Similarly, it is NP-hard to find the most efficient sequence of contractions
for a given network~\cite{LamSW1997,PfeiferHV2014}.

\paragraph*{Tensor networks in applications}

Beyond our present use of tensor networks as a model of computation to efficiently evaluate multilinear maps, tensor networks 
%
have been  %
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~\cite{Orus2014} gives an introduction to tensor networks in the context of computational physics. Itai and Landau~\cite{ItaiL2010} study quantum computation and quantum algorithms for evaluating tensor networks~\cite{ItaiL2010}. Solomonik and Hoefler study sparse tensor algebra as a model for parallel programming~\cite{SolomonikH2015}. The Holant framework
introduced by Valiant~\cite{Valiant2008} and studied further by
Cai \emph{et al.}~\cite{CaiLX2011,CaiGW2016a} involves the study of multilinear
sum--product expressions that can be viewed as tensor networks; for the reader familar with the Holant framework, the connection with tensor networks is explained in \expref{Appendix}{sec:Holant_theory}.
Tensor networks appear naturally in the study of probabilistic graphical
models~\cite{KollerF2009,MoitraW2018,RobevaS2017,WainwrightJ2008},
and in the study of various machine-learning
problems~\cite{CichockiLOPZM2016,CichockiPZLOSM2017}.

\paragraph*{Bilinear and multilinear complexity}

As was concisely outlined in \expref{Section}{sect:ideas}, for bilinear maps our present work %
%
%
is captured by
%
the study of
the  %
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\"urgisser, Clausen, and Shokrollahi~\cite{Buergisser1997} and to the survey by Pan~\cite{Pan2014}. 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 is due to Alman and Vassilevska Williams~\cite{AlmanVW2021}, Le Gall~\cite{LeGall2012,LeGall2014}, Le Gall and Urrutia~\cite{LeGallU2017}, Vassilevska Williams~\cite{VassilevskaWilliams2012}, Cohn and Umans~\cite{CohnU2013}, Cohn, Kleinberg, Szegedy, and Umans~\cite{Cohn2005}, Benson and Ballard~\cite{BensonB2015}, and Huang, Rice, Matthews, and van de Geijn~\cite{HuangRMG2017}.


\subsection{Organization of this paper}

\expref{Section}{sect:preliminaries} recalls preliminaries on tensors, multilinear maps, and branchwidth. \expref{Section}{sect:examples} reviews the specific multilinear maps that we study in this %
paper  %
and describes
the associated tensor for each map. In \expref{Section}{sec:tensor network defs}, tensor networks, execution and cost of a tensor network, and cost of a multilinear map are defined. \expref{Section}{sec:upper bounds} presents tensor-network algorithms for the multilinear maps introduced in \expref{Section}{sect:examples}. In \expref{Section}{sec:general lower bound}, a general lower bound on the cost of evaluating a multilinear map using
a  %
%
tensor network is obtained. The lower bound is expressed in terms of the socket-width of a multilinear map. In \expref{Section}{sec:socket-width lower bound}, lower bounds on socket-width for concrete multilinear maps studied in \expref{Sections}{sect:examples} \expref{and}{sec:upper bounds} are derived. Finally, \expref{Appendix}{sect:exec} gives some background results on minimum-cost executions.

\section{Preliminaries}
\label{sect:preliminaries}

Throughout the paper $[n]$ denotes $\{1,2,\ldots,n\}$ and $\F$ denotes
an arbitrary fixed field.

\subsection{Tensors}
\label{sect:tensors-maps}

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$.

\paragraph*{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 
\emph{modes}. Associate with each mode $e\in E$ a finite nonempty
\emph{index set} $J(e)$. In this case we say that $E$ is a set of
\emph{indexed} modes.  The \emph{length} of $e$ is $|J(e)|$. 
A \emph{position} is an element $j\in \prod_{e\in E}J(e)$. 
Let us write $J(E)=\prod_{e\in E}J(e)$ for the set of all
positions with respect to the indexed modes $E$.  In the special case
that the %
set $E$ of modes  %
is empty we define the
%
set $J(E)$ of positions  %
to consist of a single element.

For example, the $3$-tensor $\alpha$ shown on the right 
in \eqref{fig:intro matrix mul 1} (page \pageref{fig:intro matrix mul 1})
involves the %
set $E = \{i', k, \ell\}$ of modes  %
where $J(i') = [2]$,
$J(k) = [2]$, and $J(\ell) = [7]$ and a position in the tensor is an
element of $J(E) = [2] \times [2] \times [7]$.

\paragraph*{Tensors, matrices, vectors, and scalars}

\label{sect:tensor-def}

Let $E$ be a set of indexed modes. A \emph{tensor} with respect to $E$ is
a mapping $T:J(E)\rightarrow \F$. Equivalently, we write $T\in\F^{J(E)}$
to indicate that $T$ is a tensor with respect to the
%
indexed set $E$ of modes.  %
We view the set $\F^{J(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 \emph{order} of the tensor.  A tensor of order
zero is called a \emph{scalar}, a tensor of order one is called a 
\emph{vector}, and a tensor of order two is called a \emph{matrix}.
%
The \emph{volume} of the tensor is $|J(E)|$. The tuple $(|J(e)|:e\in E)$
is the \emph{shape} of the tensor. It is convenient to use the
%
``$\times$''~symbol  %
to %
%
highlight  %
the shape of a tensor; that is,
instead of writing, say $(2,3,4)$ for the shape, we write $2\times 3\times 4$.
For a position $j\in J(E)$ and a tensor $T\in\F^{J(E)}$,
we say that $T_j\in\F$ is the \emph{entry} of $T$ at $j$.


A \emph{flattening} of $T$ induced by a bipartition
%
%
%
$E_1 \cup E_2 = E$
%
of the modes of $T$ is a $|J(E_1)| \times |J(E_2)|$ matrix $M$ where, for $j_1 \in J(E_1)$ and $j_2 \in J(E_2)$ we have $M_{j_1,j_2} = T_{j_1j_2}$.
Given two %
order-$\ell$  %
tensors $S \in \F^{[n_1] \times [n_2] \times \cdots \times [n_\ell]}$ and $T \in \F^{[m_1] \times [m_2] \times \cdots \times [m_\ell]}$, their \emph{Kronecker product} $S \otimes T$ is a tensor in $\F^{[n_1 m_1] \times [n_2 m_2] \times \cdots \times [n_\ell m_\ell]}$ defined by
$$
(S \otimes T)_{m_1(i_1-1)+j_1,m_2(i_2-1)+j_2,\ldots,m_\ell(i_\ell-1)+j_\ell} = S_{i_1,i_2,\ldots,i_\ell} T_{j_1,j_2,\ldots,j_\ell}.
$$

For example, the tensor $\alpha$ shown on the right in \eqref{fig:intro matrix mul 1} has
order three, volume $28$, and shape $(2,2,7)$ or $2 \times 2 \times
7$.  The flattening of $\alpha$ induced by the bipartition $\{i', k\}
\cup \{\ell\}$ is the $4 \times 7$ matrix obtained by taking the four
rows of the two $2\times7$ matrices shown.  The Kronecker product
$\alpha \otimes \alpha$ of $\alpha$ with itself is an
%
order-3   %
tensor of shape $4 \times 4 \times 49$.


\subsection{Multilinear maps}

Let $E_1,E_2,\ldots,E_\ell,E'$ be pairwise disjoint sets of indexed modes
such that $E_1,E_2,\ldots,E_\ell$ are nonempty. We say that a map
$
A:\F^{J(E_1)}\times\F^{J(E_2)}\times\cdots \times\F^{J(E_\ell)}
      \rightarrow \F^{J(E')}
$
is an $\ell$-\emph{linear map} if
$A$ is linear with respect to each of its $\ell$ 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 \emph{form}.
In particular, $A$ is a form if and only if $E'$ is empty.

\paragraph*{The tensors of a multilinear map}

For an $\ell$-linear map
$
A:\F^{J(E_1)}\times\F^{J(E_2)}\times\cdots \times\F^{J(E_\ell)}\rightarrow \F^{J(E')}\,,
$
we define two slightly different tensors $T(A)$ and $\hat{T}(A)$. The tensor $T(A)$ is indexed by $J(E_1) \times J(E_2) \times \cdots \times J(E_\ell) \times J(E')$, and the tensor $\hat{T}(A)$ is indexed by $J(E_1 \cup E_2 \cup \ldots \cup E_\ell \cup E')$.  
At a position $(j_1, j_2, \ldots, j_\ell, j')$ of $T(A)$ and the corresponding position $j_1j_2\ldots j_\ell j'$ of $\hat{T}(A)$ these take the value
\[
T(A)_{(j_1, j_2, \ldots, j_\ell,j')} = \hat{T}(A)_{j_1j_2 \ldots j_\ell j'} =
A\bigl(e^{(j_1)},e^{(j_2)},\ldots,e^{(j_\ell)}\bigr)_{j'}\,,
\]
where $e^{(j_i)} \in \F^{J(E_i)}$ denotes the tensor with a $1$ in
position $j_i$ and $0$s in all other position.
The only difference between
$T(A)$ and $\hat{T}(A)$ is their shape.  The shape of $T(A)$ is
$|J(E_1)| \times |J(E_2)| \times \cdots \times |J(E_\ell)| \times
|J(E')|$,
except if $A$ is a form in which case the $|J(E')|$ part is omitted.
Thus $T(A)$ is of order $\ell+1$ (or $\ell$ if $A$ is a form).  The
shape of $\hat{T}(A)$ is $\bigtimes_{e \in E_i, i \in [\ell]} |J(e)| \times \bigtimes_{e' \in E'} |J(e')|$, thus
its order is $|E_1| + |E_2| + \cdots + |E_\ell| + |E'|$.

For example, consider the matrix multiplication map $A: \F^{[n] \times
  [n]} \times \F^{[n] \times[n]} \rightarrow \F^{[n] \times [n]}$,
\ie, for two $n\times n$ matrices $X$ and $Y$, $A(X, Y) = X \cdot Y$.
The tensor $\hat{T}(A)$ is a $6$-tensor where each position is a
$6$-tuple $(i_1, k_1, k_2, j_1, i_2, j2) \in [n]^6$, and $T(A)$ is a
$3$-tensor where each position is a triple $((i_1, k_1), (k_2, j_1),
(i_2, j_2)) \in ([n] \times [n])^3$.
The value of $\hat{T}(A)$ at position $(i_1, k_1, k_2, j_1, i_2,
j_2)$ (and of $T(A)$ at its corresponding position) is the value at position $(i_2,j_2)$ of
$A(e^{(i_1k_1)}, e^{(k_2j_1)}) = e^{(i_1k_1)}\cdot e^{(k_2j_1)}$, where $e^{(ab)}$ is the
$n\times n$ matrix with a $1$
in row $a$ column $b$ and zeroes elsewhere.  This is $1$ if $i_1 =
i_2$, $j_1=j_2$ and $k_1=k_2$, otherwise $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 $\hat{T}(A)$ which contains this
fine-grained structure.

On the other hand, $\hat{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.

\paragraph*{Sockets}

Let us study the tensor $\hat{T}(A)$ with respect to the map~$A$.
We say that the modes in
$E_1\cup E_2\cup\cdots\cup E_\ell$ %
are the \emph{input} modes of $\hat{T}(A)$,
and the modes in $E'$ are the \emph{output} modes of $\hat{T}(A)$ with respect to $A$.
Let us say that $E_1, \ldots, E_\ell$ are the
\emph{input sockets} of $\hat{T}(A)$ with respect to $A$. Similarly,
$E'$ is the \emph{output socket} in $\hat{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 
%
%
%
shape of a tensor
into sockets, see also~\expref{Section}{sect:tensor-def}.
%
Two multilinear maps, $A_1$ and $A_2$, %
may have the same base tensor $\hat{T}(A_1)=\hat{T}(A_2)$, and from a tensor $\hat{T}$ one may
obtain different multilinear maps by varying how the modes of $\hat{T}$
are assigned to input and output sockets.

\paragraph*{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 \emph{multilinear form} of $A$.
We also set $F(A)=A$ when $A$ is a multilinear form.

For example, the form of the $n \times n$ square-matrix multiplication
map is the form $F(X, Y, Z) = \sum_{i \in [n]} \sum_{j \in [n]}
\sum_{k \in [n]} X_{ij}Y_{jk}Z_{ik}$.

\subsection{Branch decompositions and branchwidth}

A \emph{branch decomposition} of a (hyper)graph $G$ consists of
(i) a tree $T$ whose every vertex has degree either one or three, and
(ii) a bijection $\pi$ between the (hyper)edge set of $G$ and the set of
vertices of degree one in $T$. Deleting an edge $e\in E(T)$ from $T$
partitions $T$ into two subtrees, %
 $T_1$ and $T_2$, which via $\pi$
%
give rise  %
to a partition of the (hyper)edges of $G$ into
two sets,  %
$E_1$ and $E_2$.
The \emph{width} $w(e)$
of the partition induced by $e$ is the number of vertices of $G$ that are
incident to at least one (hyper)edge in $E_1$ and at least one (hyper)edge
in $E_2$. The \emph{width} of the branch decomposition $(T,\pi)$ is the maximum
of the widths $w(e)$ for $e\in E(T)$. The \emph{branchwidth} $\bw(G)$ of $G$
is the minimum width of a branch decomposition of $G$.

For graphs, we recall the following upper bound on branchwidth.

\begin{claim}[Robertson and Seymour~\cite{RobertsonS1991}]
  For every $n \ge 3$, $\bw(K_n) = \lceil 2n/3 \rceil$.  Consequently, $\bw(G) \le \lceil 2 |V(G)|/3 \rceil$ for every graph $G$.
\end{claim}






\section{Examples of multilinear maps}
\label{sect:examples}

This section reviews the specific multilinear maps that we study in this
%
paper.  %
Together with each map we describe its associated
tensor and a socketing of the tensor that realizes the map.

\subsection{Discrete Fourier transform}

\label{sect:dft}

Let $n\geq 2$ be an integer and let $\rho\in\F$ be a primitive
$n^\text{th}$ root of unity in the field $\F$ if it exists.%
\footnote{That is, $\rho$ satisfies $\rho^n=1$ and $\rho^{n/k}\neq 1$
for all integer divisors $k\geq 2$ of $n$.}{}
Define the $n\times n$ symmetric matrix $\Phi$ with
entries $\Phi_{i,j}=\rho^{(i-1)(j-1)}$ for all $i,j\in [n]$.
The \emph{discrete Fourier transform (DFT) of order $n$ at $\rho$} is the
linear map $L:\F^{[n]}\rightarrow \F^{[n]}$ defined for all $x\in\F^{[n]}$
by the matrix-vector multiplication $L(x)=\Phi x$.
In particular, the matrix $\Phi$ is the tensor
associated with $L$. The matrix $\Phi$ has two modes,
namely its rows and columns.
To realize $L$, take the columns of $\Phi$ as the input socket, and the rows
as the output socket.

\subsection{Determinant and permanent}

%
%
We   %
write $S_n$ for the %
%
group of all permutations
$\sigma:[n]\rightarrow [n]$
(the symmetric group of degree $n$).  %
For $\sigma \in S_n$, let $c(\sigma)$ be the number of
cycles in the cycle decomposition of $\sigma$,
where each fixed point of $\sigma$ is counted as a cycle.
Further standard examples of multilinear %
%
%
maps
%
include the determinant and
the  %
permanent,  %
\begin{align}
\label{eq:det and per}
\det A &=
\sum_{\sigma\in S_n}(-1)^{n-c(\sigma)}\prod_{i\in[n]}a_{i,\sigma(i)} &
\per A &=
\sum_{\sigma\in S_n}\prod_{i\in[n]}a_{i,\sigma(i)}\,,
\end{align}
both of which are $n$-linear in the $n$ columns (or the $n$ rows) of the
matrix $A=(a_{ij})_{i,j\in[n]}$.
The determinant and 
the  %
permanent are associated with order-$n$  %
tensors
$\hat{T}^{(\det)}, \hat{T}^{(\per)} \in \F^{[n] \times [n] \times \cdots \times [n]}$
defined for all $j = (i_1,i_2,\ldots,i_n) \in [n] \times [n] \times \cdots \times [n]$ by

\begin{align}
\label{tensor:det}
\hat{T}^{(\det)}_{j}&=
\begin{cases}
(-1)^{n-c(j)} & \text{if } j \in S_n\\
0 & \text{otherwise}
\end{cases} &
\hat{T}^{(\per)}_{j}&=
\begin{cases}
1 & \text{if } j \in S_n\\
0 & \text{otherwise}.
\end{cases}
\end{align}
A socketing of $\hat{T}^{(\det)}$ and $\hat{T}^{(\per)}$ that realizes the determinant and
the  %
permanent, respectively, is to take each of the $n$ modes as an input socket corresponding to $A$.
%
The determinant and permanent tensors are not closed under taking Kronecker products when $n \geq 2$, 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$.

\subsection{Matrix multiplication}
\label{sect:mm}

Let $n$, $r$, and $m$ be positive integers.
Perhaps the most fundamental example of a bilinear map is the map
that multiplies
an $n\times r$ matrix $A=(A_{ij})_{i\in[n],\,j\in [r]}$ with
an $r\times m$ matrix $B=(B_{ij})_{i\in[r],\,j\in [m]}$
to obtain the $n\times m$ product matrix $C=(C_{ij})_{i\in [n]\,,j\in [m]}$
defined for all $i\in[n]$ and $j\in [m]$ by
\begin{equation}
\label{eq:mm}
C_{ij}=\sum_{k\in[r]} A_{ik}B_{kj}\,.
\end{equation}
It is natural to view the input $A\in\F^{[n]\times [r]}$ as a 2-tensor,
and similarly so for the input $B\in\F^{[r]\times [m]}$, and the
output $C\in\F^{[n]\times [m]}$. Thus, \eqref{eq:mm} is naturally
associated with the 6-tensor
$\hat{T} \in\F^{[n]\times [r]\times [r]\times [m]\times [n]\times [m]}$ with
entries defined for all $i_1,i_2\in [n]$, $j_1, j_2\in[m]$, and
$k_1,k_2\in[r]$ by
\begin{equation}
\label{eq:mm-t}
\hat{T}_{i_1\!k_1\!k_2j_1\!i_2j_2}=
\begin{cases}
1 & \text{if $i_1=i_2$ and $j_1=j_2$ and $k_1=k_2$};\\
0 & \text{otherwise}.
\end{cases}
\end{equation}
To realize \eqref{eq:mm} using \eqref{eq:mm-t}, we can use the socketing
grouped by parentheses in
$([n]\times [r])\times([r]\times [m])\times([n]\times [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 $\bra n,r,m\ket$ as a shorthand for the tensor \eqref{eq:mm-t}.
From \eqref{eq:mm-t} and the definition of the Kronecker product
it is immediate that matrix-multiplication tensors satisfy
\begin{equation}
\label{eq:mm-kron}
\bra n_1,r_1,m_1\ket
\otimes
\bra n_2,r_2,m_2\ket
=
\bra n_1n_2,r_1r_1,m_1m_2\ket\,.
\end{equation}
That is, matrix multiplication tensors are closed under taking  Kronecker products.


\subsection{Group algebra product}

Let $(\mathbb{A},+)$ be an Abelian group of order $n$.
Another fundamental example of a bilinear map is to convolve
two vectors $f\in\F^{\mathbb{A}}$ and $g\in\F^{\mathbb{A}}$ according to the
group operation of $\mathbb{A}$ to obtain
the vector $h=f*g\in\F^{\mathbb{A}}$, defined for all $k\in \mathbb{A}$ by
\begin{equation}
\label{eq:conv}
h_k=\sum_{j\in \mathbb{A}}f_{(k-j)}\,g_j\,.
\end{equation}
The map \eqref{eq:conv} is associated with the $3$-tensor
$\hat{T}\in\F^{\mathbb{A}\times\mathbb{A}\times\mathbb{A}}$ defined for all
$i,j,k\in \mathbb{A}$ by
\begin{equation}
\label{eq:conv-t}
\hat{T}_{ijk}=
\begin{cases}
1 & \text{$i+j=k$};\\
0 & \text{otherwise}.
\end{cases}
\end{equation}
A socketing of the three modes of \eqref{eq:conv-t} that
realizes \eqref{eq:conv}
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
%
%
$\F^{\mathbb{A}}$  %
equipped with the convolution product $*$ is the
\emph{group algebra} $\F[\mathbb{A}]$.


\subsection{Kruskal operator}
\label{sect:kruskal}

Let $n_1,n_2,\ldots,n_\ell$ and $r$ be positive integers.
Matrix multiplication generalizes naturally to the $\ell$-linear task
of multiplying $\ell$ matrices
$A^{(1)}\in\F^{[n_1]\times [r]}$,
$A^{(2)}\in\F^{[n_2]\times [r]}$,
$\ldots$,
$A^{(\ell)}\in\F^{[n_\ell]\times [r]}$
to obtain the order-$\ell$ tensor
$Y\in\F^{[n_1]\times [n_2]\times \cdots\times [n_\ell]}$
defined for all
$(i_1,i_2,\ldots,i_\ell)\in[n_1]\times[n_2]\times\cdots\times[n_\ell]$ by
\begin{equation}
\label{eq:kruskal}
Y_{i_1i_2\cdots i_\ell}
=\sum_{j\in [r]} A^{(1)}_{i_1j}A^{(2)}_{i_2j}\cdots A^{(\ell)}_{i_\ell j}\,.
\end{equation}
%
%
%
This map 
%
is known as the \emph{Kruskal operator}~\cite{Kruskal1977,Kolda2006}%
\footnote{Kolda~\cite{Kolda2006} calls this operator the Kruskal operator.
Kruskal~\cite{Kruskal1977} studied %
%
%
%
the special case $\ell = 3$.}{}
%
of the matrices $A^{(1)},A^{(2)},\ldots,A^{(\ell)}$.

The map \eqref{eq:kruskal} is associated with the $3\ell$-tensor
\[
\hat{T}\in\F^{%
[n_1]\times [r]\times
[n_2]\times [r]\times
\cdots \times
[n_\ell]\times [r]\times
[n_1]\times [n_2]\times\cdots\times [n_\ell]}
\]
defined for all
$i_1,i_1'\in [n_1]$,
$i_2,i_2'\in [n_2]$,
$\ldots$,
$i_\ell,i_\ell'\in [n_\ell]$
and
$j_1,j_2,\ldots,j_\ell\in [r]$
by
\begin{equation}
\label{eq:kruskal-t}
\hat{T}_{i_1j_1i_2j_2\cdots i_\ell j_\ell i_1'i_2'\cdots i_\ell'}=
\begin{cases}
1 & \text{if $i_1=i_1'$, $i_2=i_2'$, $\ldots$, $i_\ell=i_\ell'$ and $j_1=j_2=\ldots=j_\ell$};\\
0 & \text{otherwise}.
\end{cases}
\end{equation}
A socketing of \eqref{eq:kruskal-t} that realizes \eqref{eq:kruskal}
is to take each of the $\ell$ pairs of modes
$[n_1]\times[r]$, $[n_2]\times[r]$, $\ldots$, $[n_\ell]\times [r]$
as an input socket and the final $\ell$ modes
$[n_1]\times [n_2]\times\cdots\times[n_\ell]$ as the output socket.

%
%
Let us write $\bra n_1,n_2,\ldots,n_\ell \mid r\ket$ for the tensor
%
\eqref{eq:kruskal-t}. Analogously to the closure property \eqref{eq:mm-kron}
for matrix multiplication tensors, we observe that
\begin{equation}
\label{eq:kruskal-kron}
%
%
%
\bra n_1,n_2,\ldots,n_\ell\mid r\ket
\otimes
%
%
\bra n_1',n_2',\ldots,n_\ell' \mid r'\ket
%
=
%
%
\bra n_1n_1',n_2n_2',\ldots,n_\ell n_\ell' \mid rr'\ket\,.
%
\end{equation}
That is, Kruskal operator tensors are closed under taking Kronecker products.
Furthermore, we observe that $\bra n,r,m\ket$ and %
%
$\bra n,m \mid r\ket$ are equal after
%
 reordering of the modes. That is, the
matrix multiplication tensor \eqref{eq:mm-t} is the special case
of the Kruskal operator tensor \eqref{eq:kruskal-t} when $\ell=2$.


\subsection{Homomorphism-counting forms}

\label{sect:binom}

Further multilinear %
%
maps
%
arise
naturally by algebraization of combinatorial problems. For example,
the linear form of the matrix multiplication map
\begin{equation}
\label{eq:3-choose-2}
\sum_{i,j,k\in [n]}A_{ij}B_{jk}C_{ki}
\end{equation}
can be used to count the %
triangles in a graph, and the form
\begin{equation}
\label{eq:4-choose-2}
\sum_{i,j,k,\ell\in [n]}
A_{ij}B_{ik}C_{i\ell}D_{jk}E_{j\ell}F_{k\ell}
\end{equation}
can be used to count the %
occurrences of any 4-vertex subgraph in
a graph by varying the six $n\times n$ matrices
$A,B,C,D,E,F\in\F^{[n]\times [n]}$. A more complicated
variant takes as input four $3$-tensors
$A, B, C, D \in\F^{[n]\times [n]\times [n]}$
of shape $n\times n\times n$ and considers the linear form
\begin{equation}
\label{eq:4-choose-3}
\sum_{i,j,k,\ell\in [n]}
A_{ijk}B_{ik\ell}C_{ij\ell}D_{jk\ell}\,.
\end{equation}
An $n^{4-\delta}$ time algorithm for the associated trilinear map $(A, B, C) \mapsto D$ would imply an algorithm for the Max 3-Sat problem with running time $(2-\delta')^n$ \cite{Williams2005}.

The forms \eqref{eq:3-choose-2}, \eqref{eq:4-choose-2}, \expeqref{and}{eq:4-choose-3} are all special cases of what we call a \emph{homomorphism-counting form}
defined by a hypergraph $P$, or, succinctly, a $P$-\emph{linear form}.
In more precise terms, let $P$ be a $k$-uniform hypergraph on $v \ge k$ vertices and write $\binom{[v]}{k}$ for the set of $k$-element subsets of $[v]$.  For each hyperedge $S=\{i_1,i_2,\ldots,i_k\} \in E(P)\subseteq \binom{[v]}{k}$ of $P$, let $X^{(S)}$ be an input tensor of shape $[n]^S$.  The \emph{$P$-linear form} of \emph{order $n$} is the form
\begin{equation} \label{eq:homomorphism_form}
\sum_{\sigma \in [n]^{V(P)}} \prod_{S \in E(P)} X^{(S)}_{\sigma|_S},
\end{equation}
where $\sigma|_S$ is the restriction of $\sigma$ to the $k$ indices in $S$.
For example, the forms \eqref{eq:3-choose-2}, \eqref{eq:4-choose-2}, \expeqref{and}{eq:4-choose-3} are the $P$-linear forms corresponding to $P$ being a triangle, a $K_4$, and a complete $3$-uniform hypergraph on $4$ vertices, respectively.
It is immediate that \eqref{eq:homomorphism_form} is an $|E(P)|$-linear map.

The map~\eqref{eq:homomorphism_form} is associated with a tensor $\hat{T}$ of 
order $k \cdot |E(P)|$ whose modes are
%
%
$M = \{\,(S,i) \mid S \in E(P), i \in S \,\}$ with index sets
%
$J((S,i)) = [n]$. The entries of $\hat{T}$ are defined by
\begin{equation}
\label{eq:linear-forms-t}
\hat{T}_j=
\begin{cases}
1 & \text{if $\exists \sigma \in [n]^{V(P)}$ such that $j_{(S,i)}=\sigma_i$ for every $(S,i) \in M$};\\
0 & \text{otherwise}.
\end{cases}
\end{equation}
A socketing of \eqref{eq:linear-forms-t} that realizes \eqref{eq:homomorphism_form} is given by one input socket for each hyperedge $S \in E(P)$ such that
the socket contains the $k$ modes $(S,i)$ for $i \in S$.

Let us observe that the tensors of the forms \eqref{eq:4-choose-2} and
\eqref{eq:4-choose-3} are actually the same---they are both of order
$12$, have volume $n^{12}$, and are in fact equal to the outer product
of the $n \times n \times 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 \expref{Section}{sec:socket-width lower bound} that while there
are non-trivial tensor network algorithms for evaluating
\eqref{eq:4-choose-2}, no such algorithms exist for
\eqref{eq:4-choose-3}.

Let us write $\bra n\ket_P$
for the tensor $\hat{T}$ as defined
in \eqref{eq:linear-forms-t}. Analogously to the closure
properties \eqref{eq:mm-kron} \expeqref{and}{eq:kruskal-kron}, we observe the
closure property
\begin{equation}
  \label{eq:binom-kron}
  \bra n\ket_P \otimes \bra n'\ket_P = \bra nn'\ket_P\,.
\end{equation}

\section{Tensor networks}
\label{sec:tensor network defs}

\subsection{Networks}

A \emph{network} (or \emph{diagram})
consists of a finite set $V$ of \emph{vertices},
a finite set $E$ of \emph{hyperedges},
an \emph{incidence relation} $I\subseteq V\times E$, and
a \emph{boundary} $B\subseteq E$.
A network is \emph{nondegenerate} if every hyperedge is incident to at least
one vertex. In what follows we assume that all networks are nondegenerate.
A hyperedge $e\in E$ is a \emph{loop} if $e\notin B$ and $e$ is incident
to exactly one vertex.

For a vertex $v\in V$, let us write $I(v)=\{e\in E:(v,e)\in I\}$
for the set of hyperedges incident to $v$. Dually, for a hyperedge $e\in E$, let
us write $I(e)=\{v\in V:(v,e)\in 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 hyperedges of $D$, the incidence relation
of $D$, and the boundary of $D$, respectively.

For example, on the left in \eqref{fig:intro matrix mul 2} (\expref{page}{fig:intro matrix mul 2}),
we see a network with five vertices $V = \{A, B, \alpha, \beta, \gamma\}$,
seven hyperedges $E = \{i, j, \ell, i', k, k', j'\}$, and boundary $B =
\{i, j\}$.  The vertices incident to $i'$ are $I(i') = \{A, \alpha\}$.

\paragraph*{Induced networks}
For a network $D$ and a nonempty subset $W\subseteq V(D)$,
the \emph{induced} network $D[W]$ consists of the vertices in $W$ together with the hyperedges of
$D$ that are incident to at least one vertex in $W$; the boundary of
$D[W]$ consists of all hyperedges that are at the boundary of $D$
or incident to a vertex outside $W$.  Formally,
\begin{equation}
\label{eq:induced}
\begin{aligned}
  V(D[W])&=W\,,\\
  E(D[W])&=\{e\in E(D):\text{$\exists w \in W$ s.t.~$(w,e)\in I(D)$}\}\,,\\
  I(D[W])&=I(D)\cap\left(V(D[W])\times E(D[W])\right)\,,\\
  B(D[W])&=\left(B(D)\cap E(D[W])\right)\cup
  %
  \{e\in E(D[W])\!:\text{$\exists v \in V(D) \!\setminus\! W$ s.t.~$(v,e)\in I(D)$}\}.
\end{aligned}
\end{equation}
For a vertex $v\in V$, we abbreviate $D[v]=D[\{v\}]$.
Note that the boundary of $D[v]$ consists of all non-loop
hyperedges incident to $v$ in $D$.

For example, for the network on the left in \eqref{fig:intro matrix
  mul 2}, the induced network $D[\{\alpha, A\}]$ has hyperedges $E(D[\{\alpha, A\}]) = \{i',k, \ell\}$ and boundary $B(D[\{\alpha,A\}]) = \{\ell\}$.

\subsection{Tensor networks}

Let $D$ be a network.
We \emph{index} $D$ by associating with each hyperedge $e \in E$ an \emph{index set} $J(e)$ of size $\ell(e)$.  Induced networks inherit indexing by restriction.
Next we associate with each vertex $v\in V$ a tensor
$T(v)\in\F^{J(I(v))}$. We say that $D$ equipped with the tensors
$(T(v))_{v \in V}$ is a \emph{tensor network}.

The \emph{value} of a tensor network $D$, or the tensor \emph{represented by} $D$, is a tensor $T(D) \in \F^{J(B)}$, defined for all $i \in J(B)$ by
\begin{equation}
\label{eq:tensor-rep}
T(D)_i=
\sum_{j\in J(E(D)\setminus B)}
\prod_{v\in V}T(v)_{ij}\,.
\end{equation}
Observe that in \eqref{eq:tensor-rep}
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.

\subsection{Contracting tensors}

Let $D$ be a tensor network and let $W\subseteq V(D)$ be a nonempty set
of vertices. Let $w$ be a new element not in $V$.
We may \emph{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,
\begin{equation}
\label{eq:contraction}
\begin{aligned}
V(D/W)&=(V(D)\setminus W)\cup\{w\}\,,\\
E(D/W)&=E(D)\setminus\left(E(D[W])\setminus B(D[W])\right)\,,\\
I(D/W)&=\left(I(D)\setminus I(D[W])\right)\cup\{(w,e):e\in B(D[W])\}\,,\\
B(D/W)&=B(D)\,,\\
T(w)&=T(D[W])\,.
\end{aligned}
\end{equation}
The \emph{cost} of contracting $W$ in $D$ is
$c(D,W)=\prod_{e\in E(D[W])}|J(e)|$.
The value of a tensor network is invariant under contraction, \ie,
for all nonempty $W\subseteq V(D)$ it holds that $T(D)=T(D/W)$ (see
\expref{Lemma}{lem:invariance} for a proof).

For example, contracting $W = \{\alpha, A\}$ in the network on the
left in \eqref{fig:intro matrix mul 2} results in the network shown in
the second step, where the tensor $T = T(D[\{\alpha, A\}])$ of the new (unlabelled) vertex
is a vector of length $\ell$, which in position $u$ takes the value
$T_u = \sum_{i', k} \alpha_{i'ku} A_{i'k}$.


\subsection{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=D_0$ be a tensor network with at least one tensor.
For $k=1,2,\ldots,t$, select a nonempty
subset $W_{k-1}\subseteq V(D_{k-1})$ such that $W_{k-1}$ has at least two
tensors or consists of a single tensor with a loop.
Set $D_k=D_{k-1}/W_{k-1}$ and observe that the number of tensors and/or modes
decreases by at least one in the contraction.
Suppose that $D_t$ is loopless and consists of a single tensor.
We say that such a sequence of contractions is an \emph{execution} of $D$
in $t$ \emph{steps}.
The \emph{cost} of the execution is
$\max_{k=1,2,\ldots,t} c(D_{k-1},W_{k-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(D_t) = T(D)$.
The \emph{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 $D_{k} =
D_{k-1}/W_{k-1}$ takes $O(c(D_{k-1}, W_{k-1})) \le c(D)$ time to
evaluate, and there are $O(V(D))$ steps.

\begin{restatable}{lemma}{BinaryExecutionLemma}
\label{lem:binary}
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.
\end{restatable}

\expref{Lemma}{lem:binary}  is proven in \expref{Appendix}{sect:structure_min_cost_execution}.
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.

For example, \eqref{fig:intro matrix mul 2} illustrates an execution
of the network shown there, both as a sequence of contractions of
pairs of vertices, and more succinctly as an execution tree overlaid
on top of the network.

\subsection{Cost of a multilinear map}
\label{sec:map cost}

Let us now define the cost of a multilinear map via the minimum-cost
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
\[
A:\F^{J(E_1)}\times\F^{J(E_2)}\times\cdots \times\F^{J(E_\ell)}
      \rightarrow \F^{J(E')}
\]
be an $\ell$-linear map. Consider the tensor $\hat{T}(A)$ of $A$ and the
associated input sockets $E_1,E_2,\ldots,E_\ell$ and the output socket
$E'$. Let $D^*$ be an arbitrary tensor network such that $T(D^*)=\hat{T}(A)$ and
the boundary satisfies $B(D^*) =E_1\cup E_2\cup\cdots\cup E_\ell\cup E'$.
Modify the network $D^*$ as follows.
For each $k=1,2,\ldots,\ell$, introduce a new vertex to $D^*$,
make the new vertex incident to each of the modes in the input socket $E_k$,
and associate the new vertex with a tensor $X^{(k)}\in\F^{J(E_k)}$.
Remove the modes $E_1\cup E_2\cup\cdots\cup E_\ell$ from the boundary of $D^*$.
Let us denote the resulting network by $D$ and call the introduced $\ell$
new vertices the \emph{socket vertices} of $D$.
We observe that $B(D)=E'$ and $A(X^{(1)},X^{(2)},\ldots,X^{(\ell)})=T(D)$.
Furthermore, the cost $c(D)$ is independent of the value of
$X^{(k)}\in\F^{J(E_k)}$ for $k=1,2,\ldots,\ell$.
We say that $D$ is a \emph{realization} of $A$ if it can be obtained
from $A$ by this process, and write $\mathscr{D}(A)$ for the set of all
tensor network realizations $D$ of $A$.

The \emph{cost} of the map $A$ is
$c(A)=\min_{D\in\mathscr{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 $\mathscr{D}(A)$
is nonempty.

\section{Upper bounds}
\label{sec:upper bounds}

This section presents tensor-network algorithms for the maps
introduced in \expref{Section}{sect:examples}. We start with our key technical result
that cost is submultiplicative (\expref{Theorem}{thm:general upper bound},
stated formally as \expref{Theorem}{thm:submul-am}),
which then enables us to represent essentially the fastest known algorithms
using tensor networks, and, in the case of $P$-linear forms, also
improve on earlier work as reviewed in \expref{Section}{sect:our}.

Recall that the cost of an execution of a network is the maximum
number of operations of any step (contraction) in that execution,
rather than the total running time (number of operations).  With the
exception of \expref{Theorem}{thm:general upper bound}, the results in
this section are stated as the resulting upper bound on running time
but they are all derived by obtaining upper bounds on cost.

\subsection{Submultiplicativity of cost}
\label{sec:submultiplicativity}

Let $E_1,E_2,\ldots,E_\ell,E'$ be pairwise disjoint sets of indexed modes
such that $E_1,E_2,\ldots,E_\ell$ are nonempty. Let
\[
A:\F^{J(E_1)}\times\F^{J(E_2)}\times\cdots \times\F^{J(E_\ell)}
      \rightarrow \F^{J(E')}
\]
be an $\ell$-linear map.
For a positive integer $k$, we
define the $\ell$-linear map $A^{\otimes k}$ such that its tensor satisfies $T(A^{\otimes k})=T(A)^{\otimes k}$.  Then
\[
A^{\otimes k}:\F^{J(E_1)^k}\times\F^{J(E_2)^k}\times\cdots \times\F^{J(E_\ell)^k}
      \rightarrow \F^{J(E')^k}.
\]
Note that $T(A^{\otimes k}) = T(A)^{\otimes 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 $\hat{T}(A^{\otimes k})$ is
the $k$-fold outer product of $\hat{T}(A)$ with itself---that is, its
index sets have the same sizes, but its order is $k$ times larger.

Let $D$ be a network that realizes $A$ and let $\td$ be an execution
tree for $D$.
For each internal vertex $x$ in $\td$ (that is, a vertex obtained by contraction),
define the \emph{amortized cost} of $x$ by splitting into the following
three cases:
\begin{enumerate}%
\item
if neither of the two subtrees of $x$ contains a socket vertex,
the amortized cost of $x$ is $1$;
\item
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$;\footnote{Here, 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$.}
\item
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$.
\end{enumerate}

The \emph{amortized cost} $a(\td)$ of $\td$ is the maximum of the amortized
costs of the internal vertices of $\td$. Since the amortized cost of each
internal vertex of $\td$ is at most its cost, we have $a(\td)\leq 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
\emph{not by the cost of the contraction but rather by volume}.
This is because in a $k^{\text{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
\expref{Theorem}{thm:general upper bound}.

Before proceeding with the proof, let us illustrate the
key ideas in visual terms. Let us start with the three illustrations in
\eqref{fig:diag-base}.
\slimfigure{1.0}{figures/ub_tensor_rank}{diag-base}
Suppose the leftmost network in \eqref{fig:diag-base}
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 \eqref{fig:diag-base}, we have adjoined two socket
vertices to the input sockets to obtain
a realization $D$. On the right in \eqref{fig:diag-base}, we display an
execution tree $\td$ for $D$. Observe that the bottom-most internal vertices
of $\td$, and the top-most internal vertex of $\td$, have type (ii). The
internal vertex in the center has type (iii). (There are no internal vertices
of type (i).) Supposing that all the modes have length at least $2$,
we also observe that the vertices of type (ii) have
amortized cost strictly less than their contraction cost.


Let us now consider the $k^{\text{th}}$ power
of \eqref{fig:diag-base} visually, for $k=4$:

\slimfigure{0.44}{figures/ub_kronecker}{diag-base-kron}

The leftmost network in \eqref{fig:diag-base-kron} depicts the
$k$-fold outer product of the network on the left
in \eqref{fig:diag-base} 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 \eqref{fig:diag-base-kron},
we have adjoined two socket vertices to the input sockets to obtain
a realization $D^{\otimes k}$ of $A^{\otimes k}$. On the right in \eqref{fig:diag-base-kron},
we display an execution tree $\tdk$ for $D^{\otimes k}$. Observe how each
of the internal vertices of type (ii) in $\td$ gets expanded to a sequence
of $k$ internal vertices in $\tdk$. This transformation from $\td$ to $\tdk$
is the gist of the following theorem.

\begin{theorem}[Formal statement of \expref{Theorem}{thm:general upper bound}]
\label{thm:submul-am}
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
\begin{equation}
\label{eq:submul-am}
c(A^{\otimes k})\leq a(\td)^{k-1} c(\td)\,.
\end{equation}
Furthermore, this realization of $A^{\otimes k}$ consists of
at most $k \cdot |V(D)|$ vertices.
\end{theorem}

\begin{proof}
Let $D^*$ be the subnetwork of $D$ with $T(D^*)=\hat{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 $\hat{T}(A^{\otimes k})$. Attaching the resulting network
to tensors at sockets gives a realization of $A^{\otimes k}$.
Let us write $D^{\otimes k}$ for this realization.

To establish \eqref{eq:submul-am}, it suffices to construct an execution
tree $\tdk$ for $D^{\otimes k}$ whose cost satisfies
$c(\tdk)\leq a(\td)^{k-1} c(\td)$. We construct $\tdk$
by rewriting $\td$ from leaves towards the root
to consider the $k$ copies of each vertex in $D^*$. We start with leaf vertices which are the vertices of $D^{\otimes k}$.
We split the process into cases (i), (ii), and (iii)
as in the definition of amortized cost.
Let $x$ be the internal vertex 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^{\otimes k}$ individually. This creates $k$ new internal vertices
in $\tdk$ that are all copies of $x$.  We set these $k$ vertices as the vertices
that correspond to $x$ in the subsequent steps. Each of these contractions in $\tdk$ has the
same cost as the contraction indicated by $x$ in $\td$. This cost is less than or equal to $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
$\tdk$ corresponding to $y$ and $k$ identical vertices
in $\tdk$
corresponding to $z$. We contract these $k$ vertices individually each with
the vertex that corresponds to $y$. This creates $k$ new internal vertices
in $\tdk$, where we set the topmost vertex as the vertex that corresponds
to $x$ in the subsequent steps. After the $i$th 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 $i$th 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 vertices of $x$ in $\td$.
By the structure of the earlier steps, we have that a single vertex in
$D^{\otimes k}$ corresponds to $y$,
and similarly for $z$. We contract these two vertices. This creates one new
internal vertex in $\tdk$, which we set as the vertex that corresponds
to $x$ in the subsequent steps. This tensor has $k$ copies of modes of $x$. The cost of this contraction in $\tdk$ is the cost of the corresponding contraction in $\td$ to the $k^\text{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 contracting $y$ and $z$ is the same as the cost of contracting $y$ and $z$. Hence the cost of this contraction in $\tdk$ is less than or equal to $a(\td)^k \leq a(\td)^{k-1} c(\td)$.

This rewriting process produces an execution tree $\tdk$
for $D^{\otimes k}$ with $c(\tdk)\leq a(\td)^{k-1} c(\td)$.
\end{proof}

An immediate corollary is that tensor networks can use low rank
decompositions of $T(A)$ to efficiently evaluate $A^{\otimes k}$.

\begin{corollary}[Submultiplicativity of low-rank executions]
  \label{cor:low rank execution}
  Let $A: \F^{J(E_1)} \times \F^{J(E_2)} \times \cdots \times
  \F^{J(E_\ell)} \rightarrow \F^{J(E')}$ be a multilinear map.  Define
  %
  $m \!=\! \max\{|J(E_1)|, |J(E_2)|, \ldots, |J(E_\ell)|, |J(E')|\}$ and
  $r = \rk T(A)$.  Then $c(A^{\otimes k}) \le \max(r, m)^{k} \min(r, m)$
\end{corollary}

\begin{proof}
  By taking a star-like network topology (as in \eqref{fig:diag-base})
  we get an execution with $a(\td) = \max(r, m)$ and cost $c(\td) = m \cdot
  r$.
\end{proof}



\subsection{Fast matrix multiplication}
\label{sec:matrix mul upper bound}

Let us now illustrate the use of \expref{Theorem}{thm:submul-am} by capturing
fast matrix multiplication with tensor networks. We start by recalling that
for a constant $h>0$, we write $\omega(h)$ for the rectangular matrix
multiplication exponent
(see \expref{Section}{sect:our}). %
It is immediate that
$\max(2,h+1)\leq\omega(h)\leq h+2$; for the state-of-the-art bounds
on $\omega(h)$,
see Le Gall and Urrutia~\cite{LeGallU2017}. %

\begin{lemma}
\label{lem:mm}
For all constants $h>0$ and $\epsilon>0$ it holds that
an $n\times\lfloor n^h\rfloor$
matrix may be multiplied with an $\lfloor n^h\rfloor\times n$ matrix
in $O(n^{\omega(h)+\epsilon})$ operations by executing a tensor network.
\end{lemma}
\begin{proof}
Fix an $0<\epsilon<1$. Let $0<\delta_1,\delta_2<1$ be constants whose
precise values we will fix later.
By definition of $\omega(h)$, for all $t>\omega(h)$ there exists a constant
$U>0$ such that the arithmetic complexity of multiplying
an $c\times\lfloor c^h\rfloor$ matrix with an $\lfloor c^h\rfloor\times c$
matrix is at most $Uc^t$ for all $c$. Since the rank of a bilinear map
is bounded from above by two times its (multiplicative)
complexity (see \cite[\S14.1]{Buergisser1997}), %
it follows that there exist three $3$-tensors $\alpha,\beta,\gamma$
respective shapes $(c\times b)\times d$, $(b\times c)\times d$, and
$(c\times c)\times d$ for positive integer constants $b$, $c$, and $d$ with
$\max(c^2,cb)\leq d\leq c^{\omega(h)+\delta_1}$ and
$c^{h-\delta_2}\leq b\leq c^h$
such that $\alpha,\beta,\gamma$ decompose the matrix multiplication
tensor $\bra c,b,c\ket$ defined by \eqref{eq:mm-t} as depicted below; the
indices $i_1,k_1,k_2,j_1,i_2,j_2$ refer to the tensor \eqref{eq:mm-t}.
The mode shared by $\alpha,\beta,\gamma$ in \eqref{fig:ccc} has length $d$,
the modes $i_1,i_2,j_1,j_2$ each have length $c$, and the modes
$k_1,k_2$ have length $b$.
\slimfigure{1.0}{figures/ub_matrixmul1}{ccc}
For example, for $h=1$, Strassen's decomposition~\cite{Strassen1969} as
depicted in \eqref{fig:strassen-2-2-7} below realizes \eqref{fig:ccc}
with $c=b=2$ and $r=7$.
We use the numbering in magenta to indicate correspondence between
modes in \eqref{fig:ccc} \expeqref{and}{fig:strassen-2-2-7}.
\slimfigure{1.0}{figures/ub_matrixmul2}{strassen-2-2-7}

Let us next set up an application of \expref{Theorem}{thm:submul-am}.
Let
$A:\F^{[c]\times [b]}\times \F^{[b]\times [c]}\rightarrow \F^{[c]\times [c]}$
be the bilinear map that multiplies a $c\times b$ matrix with
a $b\times c$ matrix. Observe that the tensor of $A$ is
$\hat{T}(A)=\bra c,b,c\ket$.
To realize $A$, define two input sockets in \eqref{fig:ccc},
namely $\{i_1,k_1\}$ and $\{k_2,j_1\}$
to obtain a realization $D$ and an execution tree $\td$ as follows:
\slimfigure{1.0}{figures/ub_tensor_rank}{diag-base-2}
Since $\max(c^2,cb)\leq d$, the amortized cost of $\td$ satisfies
$a(\td)=d$. The cost is $c(\td)=\max(c^2,cb)d$.

Let the matrices $X\in\F^{[n]\times[\lfloor n^h\rfloor]}$
and $Y\in\F^{[\lfloor n^h\rfloor]\times[n]}$ be given. We construct
a tensor network that multiplies $X$ and $Y$.
We may assume that $\delta_2<h$.
Let $k=\lceil\frac{h\log n}{(h-\delta_2)\log c}\rceil$.
We observe that $n^h\leq c^{(h-\delta_2)k}\leq b^k$
and $n\leq c^{(1-\delta_2/h)k}\leq c^k$.
Extend the matrices $X,Y$ to $X\in\F^{[c^k]\times [b^k]}$ and
$Y\in\F^{[b^k]\times [c^k]}$ by inserting rows and columns with
zero-entries.

Since $\bra c,b,c\ket^{\otimes k}=\bra c^k,b^k,c^k\ket$ by
\eqref{eq:mm-kron}, we have that $A^{\otimes k}$ is the map that
multiplies a $c^k\times b^k$ matrix with a $b^k\times c^k$ matrix.
Using \expref{Theorem}{thm:submul-am} with $D$ and $\td$, we obtain
$c(A^{\otimes k})\leq a(\td)^{k-1}c(\td)=d^{k}\max(c^2,cb)$.
Moreover, the realization $D^{\otimes k}$ of $A^{\otimes k}$
given by \expref{Theorem}{thm:submul-am} consists of
$|V(D^{\otimes k})|=O(k)$ vertices.
We can now associate $X$ and $Y$ with the
two socket vertices of $D^{\otimes k}$, taking care to
associate $X$ with the left socket (originating from $\{i_1,k_1\}$ and $\alpha$)
and $Y$ with the right socket (originating from $\{k_1,j_1\}$ and $\beta$).
(Cf.~\eqref{fig:diag-base-kron} for an illustration how $D$ and $\td$
in \eqref{fig:diag-base-2} yield $D^{\otimes k}$ and $\tdk$.)
Executing $D^{\otimes k}$ then results in the product matrix
$A^{\otimes k}(X,Y)=XY$ in
\[
\begin{split}
d^{k}\max(c^2,cb)|V(D^{\otimes k})|
 &\leq c^{(\omega(h)+\delta_1)k}c^2b|V(D^{\otimes k})| \\
 &\leq n^{(\omega(h)+\delta_1)(h/(h-\delta_2))}c^{5+h}b|V(D^{\otimes k})| \\
 &=O(n^{\omega(h)+\epsilon})
\end{split}
\]
operations for all large enough $n$; here we have used the elementary
upper bound $\omega(h)\leq h+2$ and selected $\delta_1,\delta_2$ to be
small enough constants (that depend on the constants $h$ and $\epsilon$).
\end{proof}

The following lemma illustrates that we can also capture rectangular matrix
multiplication by reduction to square matrix multiplication using tensor
networks. This lemma in particular covers the cases when $r$ does not grow
as a polynomial function of $n$. We also observe that if $\omega=2$, the upper
bounds in the lemma are optimal up to the choice of $\epsilon>0$ because of
the size of the input/output.

\begin{lemma}
\label{lem:rmm}
For all $\epsilon>0$ it holds that we may multiply an $n\times r$ matrix
with an $r\times n$ matrix by executing a tensor network in
\begin{enumerate}%
\item
$O(n^{\omega+\epsilon-1}r)$ operations when $r\geq n$, and
\item
$O(n^2r^{\omega+\epsilon-2})$ operations when $r\leq n$.
\end{enumerate}
\end{lemma}

\begin{proof}
Fix an $\epsilon>0$ and let $\alpha,\beta,\gamma$ be three 3-tensors
of shape $(c\times c)\times d$ for constants $b=c$ and $d$
as in the proof of \expref{Lemma}{lem:mm}.
Let the matrices $X\in\F^{[n]\times [r]}$ and $Y\in\F^{[r]\times[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=c^k$ and $r=c^t$ for positive integers $t\geq k$.

Observe that we can compute the $n\times n$ product matrix $XY$ by
taking the sum of $\frac{r}{n}=c^{t-k}$ matrix products of size $n\times 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 \eqref{fig:ccc-r-geq-n}
on the right.
\slimfigure{1.0}{figures/ub_matrixmul3}{ccc-r-geq-n}
That is,
we join $t-k$ column modes of $X$ with the matching $t-k$ row modes of $Y$
using $t-k$ identity matrices $I_c$
(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 $c^k\times c^k$ matrices as depicted by $\bra c^k,c^k,c^k\ket$
in \eqref{fig:ccc-r-geq-n}; this matrix multiplication network is obtained
as in the proof of \expref{Lemma}{lem:mm} with $b=c$. The result is a multiplication
network $\bra n,r,n\ket$ as depicted in \eqref{fig:ccc-r-geq-n} on the left.
We execute this network using the structure on the right in
\eqref{fig:ccc-r-geq-n} by first
contracting (with zero cost)
the identity matrices $I_c$ with $Y$. We then execute the
remaining network as in the proof of \expref{Lemma}{lem:mm}.
For large enough $n$, the cost of the execution is at most
$c^{k(\omega+\epsilon/2)+2}c^{t-k+1}$, which translates to
$O(n^{\omega+\epsilon}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=c^k$ and $n=c^t$ for positive integers $t\geq k$.

Observe that we can compute the $n\times n$ product matrix $XY$ by
taking $(\frac{n}{r})^2=c^{2(t-k)}$ matrix products of
size $r\times r$.

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 \eqref{fig:ccc-r-geq-n}
on the right.
\slimfigure{1.0}{figures/ub_matrixmul4}{ccc-r-leq-n}
That is, we join $t-k$ row modes of $X$ each to an identity matrix $I_c$
whose other mode is at the boundary. Similarly, we join matching $t-k$
column modes of $Y$ each to an identity matrix $I_c$ 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 $c^k\times c^k$ matrices as depicted by $\bra c^k,c^k,c^k\ket$
in \eqref{fig:ccc-r-leq-n}; this matrix multiplication network is obtained
as in the proof of \expref{Lemma}{lem:mm} with $b=c$. The result is a multiplication
network $\bra n,r,n\ket$ as depicted in \eqref{fig:ccc-r-leq-n} on the left.
We execute this network using the structure on the right in
\eqref{fig:ccc-r-leq-n} by first
contracting (with zero cost)
the identity matrices $I_c$ with $X$ and $Y$, respectively.
We then execute the remaining network as in the proof
of \expref{Lemma}{lem:mm}.
For large enough $r$, the cost of the execution is at most
$c^{k(\omega+\epsilon/2)+2}c^{2(t-k)+1}$, which translates to
$O(n^2r^{\omega-1+\epsilon})$ operations since the network
has $O(k)$ vertices whose contractions have nonzero cost.
\end{proof}

Let us conclude this subsection with a well-known lemma on rectangular
matrix multiplication that we can also capture with tensor networks.

\begin{lemma}
  \label{lem:general rectangular mul}
  For all non-negative integers $a,b,c$ and $\epsilon > 0$
  it holds that we may multiply an $n^a \times n^b$ matrix by an
  $n^b\times n^c$ matrix via a tensor network in
  $O(n^{\max(a+b,b+c,a+c) (\omega + \epsilon) / 2})$ operations.

\end{lemma}

\begin{proof}
By symmetry we may assume that $a\leq c$. Thus there are three cases
to consider, namely (i) $a\leq b\leq c$, (ii) $a\leq c\leq b$, and
(iii) $b\leq a\leq c$.

When $a\leq b\leq c$, we need to achieve $O(n^{(b+c)(\omega+\epsilon)/2})$
operations. Toward this end, it suffices to multiply an $n^b\times n^b$ matrix
with an $n^b\times n^c$ matrix, which can be implemented as $n^{c-b}$
multiplications of two square matrices of size $n^b\times n^b$.
Proceeding analogously as in \expref{Lemma}{lem:rmm}, we obtain a network that
can be executed in $O(n^{c-b}n^{b(\omega+\epsilon/2)})$ operations.
We have $c-b+b(\omega+\epsilon)\leq (b+c)(\omega+\epsilon)/2$ as desired
since $c\geq b$, $\omega\geq 2$, and $\epsilon\geq 0$.

When $a\leq c\leq b$, we need to achieve $O(n^{(b+c)(\omega+\epsilon)/2})$
operations. Toward this end, it suffices to multiply an $n^c\times n^b$ matrix
with an $n^b\times n^c$ matrix, and apply part (i) of \expref{Lemma}{lem:rmm} to obtain
a network that can be executed in $O(n^{b+c(\omega+\epsilon-1)})$ operations.
We have $b+c(\omega+\epsilon-1)\leq (b+c)(\omega+\epsilon)/2$ as desired
since $b\geq c$, $\omega\geq 2$, and $\epsilon\geq 0$.

When $b\leq a\leq c$, we need to achieve $O(n^{(a+c)(\omega+\epsilon)/2})$
operations. Toward this end, it suffices to multiply an $n^a\times n^b$ matrix
with an $n^b\times n^c$ matrix. An easy modification of part (ii) of
\expref{Lemma}{lem:rmm} gives a network that can be executed in
$O(n^{a+c+b(\omega+\epsilon-2)})$ operations.
We have $a+c+b(\omega+\epsilon-2)\leq (a+c)(\omega+\epsilon)/2$ as desired
since $b\leq a$, $b\leq c$, $\omega\geq 2$, and $\epsilon\geq 0$.
\end{proof}


\subsection{Homomorphism-counting for pattern graphs of small branchwidth}

Our main result in this section is the following upper bound for $P$-linear forms when $P$ is a graph
of small branchwidth.

\begin{lemma}
  \label{lem:branchwidth ub}
  For any fixed pattern graph $P$ and every $\epsilon > 0$, there is a tensor network that evaluates the $P$-linear form of order $n$
  in $O(n^2 + n^{\bw(P) (\omega + \epsilon) / 2})$ operations.
\end{lemma}


\begin{proof}
  Consider any branch decomposition of $P$ of
  width $\bw(P)$.  Rooting this decomposition arbitrarily by subdividing
  any edge and taking the newly added vertex as root, we obtain a
  binary rooted tree $T$ with $|E(P)|$ leaves where the leaves are
  identified by the edges of $P$.  Let $r$ be the root of $T$ and
  for each vertex $u$ of $T$, let:
  \begin{enumerate}
  \item $C_u \subseteq V(P)$ (mnemonic: $C$ for ``crossing'' or ``cut'') be the set of
    all vertices of $P$ that appear both in some leaf in the subtree
    rooted at $u$, and in some leaf outside the subtree.  By
    definition $|C_u| \le \bw(P)$ for all $u$, and $C_r = \emptyset$.

  \item $D_u \subseteq V(P)$ (mnemonic: $D$ for ``done'') be the set of all vertices of $P$ that
    appear only in leaves in the subtree rooted at $u$, and not
    outside.  Note that $C_u$ and $D_u$ form a partition of the set of
    all vertices appearing in some leaf in the subtree rooted at $u$,
    and that $D_r = V(P)$.

  \item $E_u \subseteq E(P)$ be the set of all leaves of the subtree
    of $T$ rooted at $u$ (recall that each leaf of $T$ corresponds to
    an edge).  Note that $E_r = E(P)$.

  \item $A_u \in \F^{[n]^{C_u}}$ be the following %
%
order-$|C_u|$
%
   tensor
    of shape $n \times n \times \cdots \times n$ defined for a position $i \in [n]^{C_u}$ by
    \[
    (A_u)_i = \sum_{j \in [n]^{D_u}} \prod_{S \in E_u} X^{(S)}_{(ij)_{|S}},
    \]
    where $ij \in [n]^{C_u \cup D_u}$ is the Cartesian product of $i$
    and $j$.
  \end{enumerate}

  Note that $A_r$ equals the value of the $P$-linear
  form \eqref{eq:homomorphism_form}.
  Furthermore, for a leaf $u$ of $T$ corresponding to an edge $\{x_1, x_2\}$ of
  $P$,
  the tensor  %
   %
  $A_u$ is easy to compute: if %
  %
  %
  both $x_1$ and $x_2$  %
    %
  have degree
  at least $2$, then $A_u$ simply equals the input tensor
  $X^{\{x_1,x_2\}}$.  On the other hand if $x_1$ and/or $x_2$ has
  degree $1$, then $A_u$ is either a vector or a scalar, being either
  the row sums, column sums, or sum of all entries of
  $X^{\{x_1,x_2\}}$.  Each of these is readily computed in $O(n^2)$
  time by a contraction of $X^{\{x_1,x_2\}}$ with an appropriate
  tensor of ones.

  As we shall see below, for every non-leaf vertex $x$ of $T$ with
  children $y$ and $z$, the tensor $A_x$ equals the contraction of
  $A_y$ and $A_z$.
  Thus, the desired result would follow if we can show that the
  contraction of two siblings $A_y$ and $A_z$ can be computed by a
  tensor network in $O(n^{\bw(P) (\omega+\epsilon)}/2)$ operations.  We
  now proceed to establish this.




    Partition $C_x$ into $C_{xy} \cup C_{xz} \cup C_{xyz}$ where
    $C_{xyz} = C_x \cap C_y \cap C_z$, $C_{xy} = C_x \setminus C_z$
    and $C_{xz} = C_x \setminus C_y$ (note that every element of $C_x$
    must appear in exactly one of $C_y$ and $C_z$ so these three sets
    indeed partition $C_x$).  Symmetrically partition $C_y$ into
    $C_{xy} \cup C_{yz} \cup C_{xyz}$ and $C_z$ into
    $C_{xz} \cup C_{yz} \cup C_{xyz}$.  
    Note that $C_{yz} \subseteq D_x$ and that the contraction of $A_y$ and $A_z$ at position $(i,j,k)$ for $i \in [n]^{C_{xy}}$, $j \in [n]^{C_{xz}}$, $k \in [n]^{C_{xyz}}$ is exactly
    \[
    \sum_{\ell \in [n]^{C_{yz}}} A_y(i,k,\ell) A_z(j,k,\ell) =  A_x(i,j,k)
    \]
    Let $a = |C_{xy}|$, $b = |C_{yz}|$, and $c = |C_{xz}|$.  Split
    each mode in $C_{xy}$ into two separate modes $C_{xy}^{(x)}$ and
    $C_{xy}^{(y)}$ where the former is used to index $A_x$ and the
    latter is used to index $A_y$.  Similarly split the modes in $C_{xz}$ and
    $C_{yz}$, but \emph{not} the modes in $C_{xyz}$.

    The contraction of $A_y$ and $A_z$ can then be evaluated using
    rectangular matrix multiplication with the following tensor
    network.
    \slimfigure{1.0}{branchwidth-sketch}{branchwidth}

    By \expref{Lemma}{lem:general rectangular mul}, this network can be
    evaluated in
    $O(n^{|C_{xyz}|} n^{\max(a+b, b+c, a+c) (\omega+\epsilon)/2})$
    operations.  Since $a + b + |C_{xyz}| = |C_y| \le \bw(P)$,
    $b+c + |C_{xyz}| = |C_z| \le \bw(P)$, and
    $a+c + |C_{xyz}| = |C_x| \le \bw(P)$, the number of operations used to
    contract $A_y$ and $A_z$ is bounded by
    $O(n^{\bw(P) (\omega+\epsilon)/2})$.
\end{proof}



\subsection{Clique-counting forms}

For counting $v$-cliques, the general upper bound for $P$-linear forms
(\expref{Lemma}{lem:branchwidth ub}) with $P=K_v$ gives a running time of
$O(n^{(\omega+\epsilon)\lceil 2v/3 \rceil /2}) = O(n^{(\omega +
  \epsilon)\lfloor v/3 \rfloor + \tfrac{(\omega+\epsilon)}{2}(v \bmod
  3)})$.  In this section, we give a slightly improved tensor-network
algorithm, matching the running time of the currently fastest known algorithm
of Eisenbrand and Grandoni \cite{EisenbrandG2004}.  That this is possible
is more or less immediate given that tensor networks can do fast rectangular
matrix multiplication.  It can also be viewed as a consequence of a more
careful analysis of the proof of \expref{Lemma}{lem:branchwidth ub} where,
towards the end, instead of using the generic upper bound of
\expref{Lemma}{lem:general rectangular mul} for rectangular matrix
multiplication, we use the precise shape of the bottleneck matrix
multiplication needed for the $v$-clique case. For completeness,
we give a more direct argument below.

For brevity, throughout this section we refer to the $P$-linear form
for $P=K_v$ as the $\binom{v}{2}$-linear form.
\begin{lemma}
  \label{lem:v choose 2 linear form upper bound}
For all constants $\epsilon>0$ and $v \geq 3$, the $\binom{v}{2}$-linear form of order $n$
can be evaluated by executing a tensor network in
$O(n^{\beta+\epsilon})$ operations, where $\omega v/3 \le \beta \le \omega v/3 + (v \bmod 3)$ is the exponent of the arithmetic complexity of the $\bra n^{\lfloor v/3 \rfloor}, n^{\lfloor (v+1)/3 \rfloor}, n^{\lfloor (v+2)/3 \rfloor} \ket$ matrix multiplication map.
\end{lemma}


\begin{proof}
  Let $S_1$, $S_2$, and $S_3$ be an arbitrary partition of the $v$
  vertices of $K_v$ into sets of sizes $\lfloor v/3 \rfloor$, $\lfloor
  (v+1)/3 \rfloor$ and $\lfloor (v+2)/3 \rfloor$, respectively.
  Let $E_{ij} = E(S_i, S_i \cup S_j)$ be the edges inside $S_i$ and
  between $S_i$ and $S_j$.  In particular, $E_{12}$, $E_{23}$ and $E_{31}$
  form a partition of the edges of $K_v$.

  We construct a network for evaluating the clique-counting form as
  follows.  First, contract all inputs $X^{(ab)}$ with $ab \in E_{12}$
  na\"\i{}vely.  This results in a tensor $Y^{(12)}$ with volume $n^{|S_1|
    + |S_2|}$ which we view as an $n^{|S_1|} \times n^{|S_2|}$ matrix
  where the rows are indexed by multisubsets $R$ of $[n]$ of size $|S_1|$
  and the columns by multisubsets $C$ of size $|S_2|$; the entry at
  row $R$, column $C$ is the $0$-$1$ indicator of whether $R \cup C$ is
  a set of size $|S_1|+|S_2|$ where all vertices of $R$ have edges to
  all other vertices in $R \cup C$.
  Contract all of $E_{23}$ and
  $E_{31}$ similarly, obtaining an $n^{|S_2|} \times n^{|S_3|}$ matrix
  $Y^{(23)}$ and an $n^{|S_3|} \times n^{|S_1|}$ matrix $Y^{(31)}$.
  The cost of creating $Y^{(ij)}$ is simply its volume $n^{|S_i|+|S_j|} \le n^{\beta}$.

  Next, perform the matrix multiplication $Z = Y^{(12)} \cdot Y^{(23)}$ in
  time $O(n^{\beta + \epsilon})$ using the same method as in the proof
  of \expref{Lemma}{lem:mm}.  The matrix $Z$ at row $R
  \in [n]^{|S_1|}$, column $C \in [n]^{|S_3|}$ counts the 
%
  subsets $U\in [n]^{|S_2|}$ such that $W = R \cup C \cup U$ is a set of
  size $|S_1| + |S_2| + |S_3|$ (viewing $R$, $C$ and $U$ as multisubsets of
  $[n]$ in the obvious way) where all vertices in $R \cup U$ have
  edges to all other vertices in $W$.

  Finally, contract $Z$ with $Y^{(31)}$ (identifying the rows of
  $Z$ with the columns of $Y^{(31)}$ and vice versa) in time $n^{|S_3|
    + |S_1|} \le n^{\beta}$ to obtain the number of $v$-cliques in the
  input graph.
\end{proof}





\subsection{Fast Fourier transforms and fast convolution}

\label{sect:fft}

Let us next express fast Fourier transforms as tensor networks and their
executions.
We start by observing that the Cooley--Tukey~\cite{CooleyT1965} fast
Fourier transform on $\Z_{2^k}$ can be implemented as a tensor network.
We assume $\rho$ is a primitive $(2^k)^\text{th}$ root of unity in
the field $\F$.

\begin{lemma}
\label{lem:fft}
The discrete Fourier transform for the Abelian group $\Z_{2^k}$ can
be computed by executing a tensor network in $O(2^kk)$ operations.
\end{lemma}
\begin{proof}
The case $k=0$ is immediate so let us assume that $k\geq 1$.
We construct a tensor
network whose execution multiplies a vector $x\in\F^{[2^k]}$ with the DFT
matrix $\Phi$ in \expref{Section}{sect:dft} for $n=2^k$
to yield the result $\Phi x\in\F^{[2^k]}$.
Toward this end, let us write $I_m$ for an
$m\times m$ identity matrix,
\begin{equation}
\label{eq:h2}
H_2=\left[\begin{array}{rr}1&1\\1&-1\end{array}\right]
\end{equation}
for the $2\times 2$ Hadamard-Walsh matrix, and
$R^{(k,j)}\in\F^{[2^k]}$ for the vector obtained by concatenating
$2^j$ copies of the vector
\[
[\underbrace{1,1,\ldots,1}_{2^{k-1-j}},
 \underbrace{\rho^{2^j\cdot 0},\rho^{2^j\cdot 1},\ldots,\rho^{2^j\cdot(2^{k-1-j}-1)}}_{2^{k-1-j}}]
\]
for $j=0,1,\ldots,k-2$.
%
%
We can decompose $\Phi$ into a sequence
of $2^k\times 2^k$ matrices 
(see, \eg, \cite{VanLoan1992})  %
\begin{equation}
\label{eq:cooley-tukey}
\Phi=P^{(k)}B^{(k,k-1)}T^{(k,k-2)}B^{(k,k-2)}\cdots T^{(k,1)}B^{(k,1)}T^{(k,0)}B^{(k,0)}
\end{equation}
consisting of alternating butterfly matrices
\[
B^{(k,j)}=
\underbrace{I_2\otimes I_2\otimes \cdots\otimes I_2}_{j}
\otimes H_2 \otimes
\underbrace{I_2\otimes I_2\otimes \cdots\otimes I_2}_{k-j-1}
\]
and diagonal twiddle matrices
\[
T^{(k,j)}=\text{diag}(R^{(k,j)})
\]
followed by a permutation matrix $P^{(k)}$ that permutes the indices
in $[2^k]$ viewed as $k$-bit strings by reversing the bit-order.
Since only the $(j+1)^\text{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 \eqref{eq:cooley-tukey}
can be represented as a tensor network $D^*$ as depicted below (for $k=5$)
so that all the modes have length $2$.
\slimfigure{0.62}{figures/ub_fft_product}{diag-phi-5}
We can now connect the network \eqref{fig:diag-phi-5} to a data vector
$x\in\F^{[2^k]}$ to obtain the network $D$ below:
\slimfigure{0.62}{figures/ub_fft_with_input}{diag-phi-x-5}
Below we depict in red an execution tree $\td$ with cost $2^{k+1}$
for the network \eqref{fig:diag-phi-x-5}. Observe that the mode
permutation (multiplication with the matrix $P^{(5)}$) is not part of
the execution since the permutation amounts to merely rearranging
the modes.
\slimfigure{0.62}{figures/ub_fft_with_exec}{diag-phi-x-5-exec}
Since the network has $O(k)$ tensors, the execution
\eqref{fig:diag-phi-x-5-exec} can be carried out in $O(2^kk)$ operations in $\F$.
\end{proof}

\begin{lemma}
\label{lem:fwht}
The discrete Fourier transform for the elementary Abelian group $\Z_{2}^k$ can
be computed by executing a tensor network in $O(2^kk)$ operations.
\end{lemma}
\begin{proof}
This proof is analogous to the proof of \expref{Lemma}{lem:fft} but omits the twiddle matrices
$T^{(k,j)}$ and the final permutation matrix $P^{(k)}$ from the
decomposition of the tensor network.
\end{proof}

The following corollary is immediate from \expref{Lemma}{lem:fft}.

\begin{lemma}
\label{lem:conv}
The group algebra products on $\F[\Z_{2^k}]$ and $\F[\Z_2^k]$
can be computed by executing a tensor network in $O(2^kk)$ operations whenever
$2$ is a unit in $\F$.
\end{lemma}
\begin{proof}
We start with $\F[\Z_{2^k}]$.
Let $f,g\in\F^{[2^k]}$ be two vectors given as input. Our task is to
compute the $\Z_{2^k}$-convolution $f*g\in\F^{[2^k]}$.
The case $k=0$ is immediate so suppose that $k\geq 1$.
Recalling that $f*g=\Phi^{-1}((\Phi f)\cdot (\Phi g))$, where
``$\cdot$'' denotes an elementwise (Hadamard) product of two vectors of
length $2^k$, let us construct a tensor network as follows.
First take the FFT of $f$ and $g$ using \expref{Lemma}{lem:fft},
then multiply the resulting vectors elementwise, and
finally take the inverse FFT by
replacing $\rho$ with $\rho^{-1}$ in \expref{Lemma}{lem:fft} and
multiplying with the diagonal matrix $\frac{1}{2^k}I_{2^k}$.
Below we display (for $k=5$) the resulting network $D$ that executes to $f*g$.
\slimfigure{0.28}{figures/ub_convolution}{diag-conv}
The execution of the network proceeds from right to left analogously to
\eqref{fig:diag-phi-x-5-exec}.
\slimfigure{0.28}{figures/ub_convolution_with_exec}{diag-conv-exec}
The cost of this execution is $2^{k+1}$.
Since the network has $O(k)$ tensors, the execution
\eqref{fig:diag-conv-exec} can be carried out in $O(2^kk)$ operations in $\F$.

The case of $\F[\Z_2^k]$ is analogous but replacing \expref{Lemma}{lem:fft}
with \expref{Lemma}{lem:fwht} and modifying the networks accordingly.
\end{proof}



\subsection{Yates' algorithm}

A particularly simple use case for \expref{Theorem}{thm:submul-am}
occurs when $A:\F^{[s]}\rightarrow\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$.

Then, \expref{Theorem}{thm:submul-am} immediately implies that we can evaluate
$A^{\otimes k}:\F^{[s]^k}\rightarrow\F^{[t]}$ using a tensor network
with cost $\max(s^{k+2},t^{k+2})$ and $O(k)$ vertices. In particular, the
network can be executed in $O(\max(s^{k+2},t^{k+2})k)$ operations in $\F$.
This network in essence realizes Yates' algorithm~\cite{Yates1937}
for multiplying an $s^k$-length vector with the $k^\text{th}$
Kronecker power of an $s\times t$ matrix to obtain $t^k$-length vector.

Applying the previous observation to $A=H_2$ in \eqref{eq:h2} with $s=t=2$,
we obtain \expref{Lemma}{lem:fwht} as an immediate corollary. Similarly,
other choices of $2\times 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~\cite{BjorklundHKK2007,BjorklundHKK2008,BjorklundHK2009}.
In particular, the pair of mutually inverse $2\times 2$ matrices
\[
Z_2=\left[\begin{array}{rr}
1&1\\
0&1
\end{array}\right]\,,\qquad
M_2=\left[\begin{array}{rr}
1&-1\\
0&1
\end{array}\right]
\]
yield, as $Z_2^{\otimes k}$ and $M_2^{\otimes k}$, the zeta and
M\"obius tranforms for the lattice $(\{0,1\}^k,\subseteq,\cap,\cup)$
of all subsets of a $k$-element set, partially ordered by subset inclusion.
\expref{Theorem}{thm:submul-am} yields immediately the standard algorithms
(normally developed via Yates's algorithm)
for the fast zeta and the fast M\"obius transforms via tensor networks.
These networks can then be combined as in the proof of
\expref{Lemma}{lem:conv} to yield the associated bilinear convolution maps
(multiplication maps in the semigroup algebra
$\F[(\{0,1\}^k,\subseteq,\cap,\cup)]$) to realize these maps in
$O(2^kk)$ operations. We omit the details due to similarity
with \expref{Lemma}{lem:conv}.



\subsection{Kruskal operator}

We proceed to implement the Kruskal operator by taking Kronecker products
and reducing to fast rectangular matrix multiplication. Let us first
proceed via \expref{Lemma}{lem:rmm} relying on square matrix multiplication.

\begin{lemma}
\label{lem:kruskal}
For all constants $\epsilon>0$ and $\ell=1,2,\ldots$
it holds that we may evaluate the Kruskal operator
of $\ell$ matrices of shape $n\times r$ by executing a tensor network in
\begin{enumerate}%
\item
$O(n^{\lceil\ell/2\rceil(\omega+\epsilon-1)}r)$ operations when $r\geq n^{\lceil \ell/2\rceil}$, and
\item
$O(n^{2\lceil\ell/2\rceil}r^{\omega+\epsilon-2})$ operations when $r\leq n^{\lceil \ell/2\rceil}$.
\end{enumerate}
\end{lemma}
\begin{proof}
Fix an $\epsilon>0$ and let $\alpha,\beta,\gamma$ be three 3-tensors
of shape $(c\times c)\times d$ for constants $b=c$ and $d$
as in the proof of \expref{Lemma}{lem:mm}.
Let $A^{(1)},A^{(2)},\ldots,A^{(\ell)}\in\F^{[n]\times[r]}$ be given as input.
We construct a tensor network that computes the output $Y$ of the
Kruskal operator \eqref{eq:kruskal}.

Without loss of generality we may assume that $\ell$ is even by
introducing a matrix $A^{(\ell+1)}\in\F^{[n]\times[r]}$ filled with
$1$-entries and setting $\ell\leftarrow\ell+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 take Kronecker products of the matrices
$A^{(1)},A^{(2)},\ldots,A^{(\ell/2)}$ and
$A^{(\ell/2+1)},A^{(\ell/2+2)},\ldots,A^{(\ell)}$
\emph{in the vertical dimension only} to obtain two matrices
$B\in\F^{[n^{\ell/2}]\times [r]}$
and
$C\in\F^{[n^{\ell/2}]\times [r]}$,
respectively. We then multiply $B$ and the transpose of $C$ using fast
rectangular matrix multiplication from \expref{Lemma}{lem:rmm} to obtain
$Y\in\F^{[n^{\ell/2}]\times [n^{\ell/2}]}$. It is immediate from
\expref{Lemma}{lem:rmm} that this
results in the operation counts claimed in (i) and (ii) as long as we
can realize the idea using tensor networks.
Taking Kronecker product in the vertical dimension only can be realized by joining
all the \emph{horizontal} dimensions to a common mode, which becomes the
inner mode for matrix multiplication. The resulting network is
depicted below (for $\ell=6$), where either \eqref{fig:ccc-r-geq-n}
or \eqref{fig:ccc-r-leq-n} is used for the
subnetwork indicated with $\bra n^{\ell/2},r,n^{\ell/2}\ket$
depending on whether (i) or (ii) holds.
\slimfigure{1.0}{figures/ub_kruskal}{kruskal-diag}
In drawing \eqref{fig:kruskal-diag} 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)},\ldots,A^{(\ell)}$ is in fact subdivided by inserting
an identity matrix $I_c$ just before the incidence to the input matrix.
The network \eqref{fig:kruskal-diag} is executed first by contracting
the (zero-cost) identity matrices $I_c$, then contracting
$A^{(1)},A^{(2)},\ldots,A^{(\ell/2)}$ and
$A^{(\ell/2+1)},A^{(\ell/2+2)},\ldots,A^{(\ell)}$, and finally proceeding
to execute the subnetwork $\bra n^{\ell/2},r,n^{\ell/2}\ket$ as
in \expref{Lemma}{lem:rmm}.
\end{proof}

The next lemma gives a sharper conclusion using the rectangular matrix
multiplication exponents $\omega(h)$ when $r$ is assumed to grow
polynomially as a function of $n$.

\begin{lemma}
\label{lem:kruskal-2}
For all constants $\epsilon>0$, $\rho>0$, and $\ell=1,2,\ldots$
it holds that we may evaluate the Kruskal operator
of $\ell$ matrices of shape $n\times r$, where $r=\lfloor n^\rho\rfloor$,
by executing a tensor network in
$O\bigl(n^{\lceil\ell/2\rceil\omega\left(\frac{\rho}{\lceil\ell/2\rceil}\right)+\epsilon}\bigr)$ operations.
\end{lemma}
\begin{proof}
Proceed as in the proof of \expref{Lemma}{lem:kruskal}, but implement the subnetwork
for $\bra n^{\lceil\ell/2\rceil},r,n^{\lceil\ell/2\rceil}\ket$ as in
\expref{Lemma}{lem:mm}.
More precisely, take $N=n^{\lceil\ell/2\rceil}$, $h=\rho/\lceil\ell/2\rceil$,
and observe that
$\bra N,\lfloor N^h\rfloor,N\ket=\bra n^{\lceil\ell/2\rceil},r,n^{\lceil\ell/2\rceil}\ket$.
\end{proof}

To our knowledge,
%
\expref{Lemmas}{lem:kruskal} \expref{and}{lem:kruskal-2}  %
capture the state of the art for
computing the Kruskal operator.

\subsection{The permanent}

The following lemma observes that essentially the fastest known algorithm
for the permanent, namely Ryser's algorithm~\cite{Ryser1963}, can be
realized as a tensor network. Here by essentially fastest known we
mean the base of the exponential running time. Sub-exponential speed-ups
to Ryser's algorithm are known, see, \eg, Bj\"orklund~\cite{Bjorklund2016}.

\begin{lemma}
The permanent of an $n\times n$ matrix can be computed by executing
a tensor network in $O(2^nn)$ operations.
\end{lemma}
\begin{proof}
We observe that Ryser's algorithm~\cite{Ryser1963} for the
permanent \eqref{eq:det and per}, namely the inclusion--exclusion expression
\[
\per A=\sum_{S\subseteq [n]}(-1)^{n-|S|}\prod_{i\in [n]}\sum_{j\in S}a_{ij}
\]
is implementable with a star-shaped tensor network consisting of
$n$ matrices of shape $2^n\times n$ joined together by a common mode (of length $2^n$), 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 $2^n$ subsets $S\subseteq [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\times 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 $2^n$ until the scalar $\per A$ remains.
\end{proof}




\section{A lower bound for the cost of a multilinear map}
\label{sec:general lower bound}

In this section, we prove a general lower bound on the cost of
evaluating a multilinear map using tensor networks, as defined in
\expref{Section}{sec:map cost}.  The lower bound is expressed in terms of the \emph{socket-width} of a multilinear map, which we
now proceed to define.

Let $A:\F^{J(E_1)}\times\F^{J(E_2)}\times\cdots \times\F^{J(E_\ell)}
\rightarrow \F^{J(E')}$ be an $\ell$-linear map.  A \emph{socket-tree}
of $A$ is a tree $\ts$ whose $\ell+1$ leaf vertices are the sockets
$E_1,E_2,\ldots,E_\ell, E'$ of $A$ and whose internal vertices all have
degree exactly $3$.  Associate with each edge $e = \{x_R, x_C\}$ of $\ts$
the two subtrees $\ts(x_R, e)$ and $\ts(x_C, e)$ obtained by
removing $e$, where $\ts(x_R, e)$ is the subtree containing $x_R$ and $\ts(x_C,
e)$ is the subtree containing $x_C$.  Let $L(x_R, e)$
be the set of leaves in $\ts(x_R, e)$ and let $L(x_C, e)$
be the set of leaves in $\ts(x_C, e)$.

The sets $L(x_R, e)$ and $L(x_C,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(x_R,e)$ index the rows and the modes in  $L(x_C,e)$ index
the columns of $M(\ts,e)$.  The \emph{width} of $\ts$ at $e$ is the
rank of $M(\ts, e)$, and the \emph{width} of $\ts$ is
$w(\ts)=\max_{e\in E(\ts)} \rk(M(\ts,e))$.

Let us write $\mathscr{S}(A)$ for the set of all socket-trees of the
multilinear form $A$.  We define the \emph{socket-width} of $A$ to be
$w(A)=\min_{\ts\in\mathscr{S}(A)} w(\ts)$.

The rest of this section is devoted to proving \expref{Theorem}{thm:general lower bound}:

\GeneralLowerBoundTheorem*

First, we prove that without loss of generality, we may restrict
attention to forms rather than general maps.

\begin{claim}
For any multilinear map $A$, it holds that $c(A) \ge c(F(A))$.
\end{claim}
\begin{proof}
We observe that $A$ and $F(A)$ satisfy $\hat{T}(A)=\hat{T}(F(A))$. Any network
$D\in \mathscr{D}(A)$ can be modified to a network
$D'\in \mathscr{D}(F(A))$ by attaching a tensor $X' \in \F^{J(E')}$ to the boundary
of $D$. Let $D\in \mathscr{D}(A)$ be such that
$c(D)=c(A)$. The minimum-cost execution of $D$, followed
by contracting $T(D)$ and $X'$, is an execution of $D'$. Its
cost is $c(A)$, since the cost of contracting of $T(D)$ and $X'$ is $\prod_{e \in B(D)} |J(e)|$ and $\prod_{e \in B(D)} |J(e)| \leq c(A)$, because the last step of the minimum-cost execution of $D$ contracts a set $W$ with all modes $e \in B(D)$ incident to $W$. Thus, $c(A)\ge c(F(A))$.
\end{proof}

Furthermore, $w(A) = w(F(A))$ for every multilinear map $A$, since
$w(A)$ only depends on the tensor $T(A)$, but not on which of its coordinates (if any) is the output.
Thus it suffices to prove \expref{Theorem}{thm:general lower bound} for
multilinear forms, which we now proceed to do.

\begin{lemma}
  For any multilinear form $F$, it holds that $c(F) \ge w(F)$.
\end{lemma}

\begin{proof}
  Let $D\in\mathscr{D}(F)$ be such that $c(D)=c(F)$. It is a tensor
  network with empty boundary and a socket vertex $S_i \in V(D)$ for
  each input socket $E_i$, where $i=1,2,\ldots,\ell$. Its tensor is
  $T(D) = F(X^{(1)}, X^{(2)},\ldots, X^{(\ell)})$ where $X^{(i)} =
  T(S_i)$ for $i=1,2,\ldots,\ell$.

  By \expref{Lemma}{lem:binary}, 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
  vertex 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  $S_1,S_2,\ldots,S_\ell$ instead of the sockets $E_1,E_2,\ldots,E_\ell$.
  To establish the lemma, it suffices to show that
  $\td$ has cost at least $w(\ts)$, since $w(\ts) \geq w(F)$.

  Let $e = \{x_R, x_C\} \in E(\ts)$ be an edge of the socket tree
  $\ts$ with $\rk(M(\ts, e)) = w(\ts)$, and let $\widetilde{e}$ be an edge of
  the execution tree $\td$ in the subdivision of $e$ appearing in
  $\td$. Without loss of generality we may assume that $\widetilde{e}$ is directed from the part of $\td$ corresponding to $x_R$ towards the part corresponding to $x_C$ (if not, simply switch names of $x_R$ and $x_C$).  Define  $S_R = L(x_R, e)$ and
  $S_C = L(x_C, e)$.  Let $W_R \subseteq V(D)$ be the set of
  non-socket vertices of $D$ that appear on the same side of $\widetilde{e}$ in $\td$ with socket vertices $S_R$ and let
  $W_C$ be the set of remaining non-socket vertices of $D$.  See \expref{Figure}{fig:lower bound proof} for an illustration of all these definitions.
  Finally, let $D' = D / S_R / S_C / W_R / W_C$ be the
  result of contracting each of these four sets of vertices of
  $D$.
  For notational convenience, we identify the four vertices of
  the new network with the four subsets $S_R, S_C, W_R, W_C$.

  \begin{figure}
    \begin{subfigure}[b]{0.52\textwidth}
      \centering
      \includegraphics[scale=0.86]{lowerbound-proof-fig1-D}
      \caption{Example of a possible execution tree $\td$.  Given the
        choice of $e$ in the corresponding socket tree $\ts$ shown on
        the right there are four possible choices of $\widetilde{e}$.}
    \end{subfigure}
    \qquad
    \begin{subfigure}[b]{0.4\textwidth}
      \centering
      \includegraphics{lowerbound-proof-fig1-S}
      \caption{The corresponding socket tree $\ts$. The exact choice of $\widetilde{e}$ in $\td$ determines which part of the
        cut is the $x_R$ part, and which is the $x_C$ part.}
      \label{fig:lb proof b}
    \end{subfigure}
    \caption{Illustration of the notation used for the execution and socket trees.
    }
    \label{fig:lower bound proof}
  \end{figure}

  Now, the tensor $P = T(D'[W_R\cup S_R])$ appears as an intermediate result in
  the execution $\td$,\footnote{Note that this follows from our choice that the $R$ part of $D$ is below $\tilde{e}$ in the execution tree, and that the same is not necessarily true for the tensor $T(D'[W_C \cup S_C])$. E.g.~if in \expref{Figure}{fig:lower bound proof} we had instead taken $\tilde{e}$ to be the edge further down which joins $X^{(1)}$ and $X^{(2)}$ with $A^{(1)}$ then $T(D'[W_C \cup S_C])$ would be the contraction of $A^{(1)}$, $A^{(2)}$, $X^{(3)}$ and $X^{(4)}$, which is not an intermediate result in the execution of $\td$.} hence the volume of $P$ is a lower bound on the cost of $\td$.

  We group the modes of $D'$ incident on $S_R$ or $W_R$ as shown in
  \expref{Figure}{fig:lower bound proof 2}: $E_{SW}$ are all modes in $D'$
  incident exactly upon $S_R$ and $W_R$, $E_{WC}$ are all modes
  incident on $W_R$ but not on $S_R$, $E_{SC}$ are all modes incident
  on $S_R$ but not $W_R$, and finally $E_{SWC}$ are all modes incident
  upon $S_R$, $W_R$, and at least one of $S_C$ or $W_C$.  Write
  $E_{S} = E_{SW} \cup E_{SC} \cup E_{SWC}$ for the modes incident on
  $S_R$, and similarly $E_{C} = E_{WC} \cup E_{SC} \cup E_{SWC}$ for
  all modes incident upon at least one of $S_R$ or $W_R$, and at least one
  of $S_C$ or $W_C$.  Note that $|J(E_C)|$ is precisely the volume of $P$
  which we aim to lower bound.

  \begin{figure}
    \centering
    \includegraphics[scale=1.1]{lowerbound-proof-fig2-general}
    \caption{Illustration of $D'$.  We group the modes of $D'$ based on how they connect $S_R$, $S_C$, and the ``$C$ part'' of $D'$.}
    \label{fig:lower bound proof 2}
  \end{figure}

Define a matrix $A \in \F^{J(E_S)} \times \F^{J(E_{C})}$ as follows.  We identify its row indices $i \in J(E_S)$ as being triples $i = (i_{SW},i_{SC},i_{SWC}) \in J(E_{SW}) \times J(E_{SC}) \times J(E_{SWC})$ and similarly its column indices $j \in J(E_{C})$ are triples $j = (j_{SC},j_{WC},j_{SWC}) \in J(E_{SC}) \times J(E_{WC}) \times J(E_{SWC})$.  Then the entries of $A$ are
  \begin{equation*}
    A_{(i_{SW},i_{SC},i_{SWC}),(j_{SC},j_{WC},j_{SWC})} =
  \begin{cases}
    T(D'[W_R])_{i_{SW},j_{WC},j_{SWC}} & \!\!\text{if } i_{SC} = j_{SC} \wedge i_{SWC}=j_{SWC},\\
    0 & \!\!\text{otherwise},
  \end{cases}
  \end{equation*}
  In the case when $E_S = E_{SW}$ (\ie, all modes incident on $S_R$ connect only to $W_R$), $A$ is simply a flattening of $T(D'[W_R])$. Recall that $T(D'[S_R]) \in \prod_{e \in E_S}\F^{J(e)}$. Then for every $j = (j_{SC},j_{WC},j_{SWC}) \in J(E_C)$, we have
  \begin{align*}
    \sum_{i \in J(E_S)} A_{i,j} T(D'[S_R])_{i} &= \sum_{i_{SW} \in J(E_{SW})} A_{(i_{SW},j_{SC},j_{SWC}),j} T(D'[S_R])_{i_{SW},j_{SC},j_{SWC}} \\
    &= \sum_{i_{SW}} T(D'[W_R])_{i_{SW},j_{WC},j_{SWC}} T(D'[S_R])_{i_{SW},j_{SC},j_{SWC}}\\
    &= P_{j_{SC},j_{WC},j_{SWC}} = P_j
  \end{align*}
  (recall that $P$ is the contraction of $T(D'[W_R])$ and $T(D'[S_R])$).
  Viewing $T(D'[S_R])$ as a row vector in $\F^{J(E_S)}$ we see that
  $P$ is simply the
  vector-matrix product $P = T(D'[S_R]) \cdot A \in \F^{J(E_C)}$.

  Symmetrically, for the other half of $D'$, we can write $Q =
  T(D'[W_C\cup S_C])$ as a matrix-vector product $Q = B \cdot T(D'[S_C]) \in \F^{J(E_{C})}$ where $B$ is a matrix corresponding to $T(D'[W_S])$ analogously to how $A$ corresponds to $T(D'[W_R])$.

  Thus we have $T(D) = T(D'[S_R]) \cdot A \cdot
  B \cdot T(D'[S_C])$.  Recall that for each
  socket vertex $S_i$ in the original network $D$, we have $T(S_i) = X^{(i)}$.  Denoting $X_R = T(D'[S_R])$ and $X_C = T(D'[S_C])$, we get $X_R = \bigotimes_{S_i \in S_R} X^{(i)}$ and $X_C = \bigotimes_{S_i \in S_C} X^{(i)}$.\footnote{These identities use the fact that $D$ is derived from a \emph{non-degenerate} network $D^*$ for $\hat{T}(F)$.  In particular, every mode in the network $D$ is incident upon at least one non-socket vertex, hence all modes incident upon $S_R$ are boundary modes in $D'[S_R]$, and similarly for $S_C$.}
    Hence
  \[
  F(X^{(1)}, X^{(2)}, \ldots, X^{(\ell)}) = X_R \cdot A \cdot B \cdot X_C.
  \]
  It follows that $A \cdot B$ is the flattening of $T(F)$
  to a matrix with rows indexed by the sockets in $S_R$ and columns
  indexed by the sockets in $S_C$.  But this flattening is precisely
  the matrix $M(\ts, e)$, implying that $|J(E_{C)}| \ge \rk(M(\ts, e)) =
  w(\ts)$, as desired.
\end{proof}


\section{Lower bounds for socket-width}
\label{sec:socket-width lower bound}

In this section we establish lower bounds on socket-width for concrete
maps.

\subsection{Determinant and permanent}
\label{sec:det and per socket width lower bounds}
\label{sec:permanent barrier}

We now prove lower bounds for the socket width of the determinant and
permanent.
Let us start with the following trivial observation.

\begin{claim}
  \label{claim:balanced edge}
  For any socket tree $\ts$ with $n \ge 2$ leaves, there is an edge $e = \{x_R, x_C\}$
  such that $n/3 \le |L(x_R, e)| < 2n/3$.
\end{claim}

\begin{proof}
  Consider all edges $e = \{x_R, x_C\}$ such that $|L(x_R, e)| \ge n/3$.  At
  least one such edge certainly exists since $n \ge 2$. Indeed, an edge
  $e = \{x_R, x_C\}$ incident to a leaf $x_C$ has $|L(x_R, e)| = n-1$
  leaves.  Among these, choose an edge such that $\ts(x_R, e)$ is of minimal size.
%
  Assume for contradiction that $|L(x_R, e)| \ge 2n/3$.  But then one of
  the two subtrees of $x_R$ in $\ts(x_R, e)$ must have at least $n/3$
  leaves, and since they are smaller than $\ts(x_R, e)$, this contradicts
  the minimality of $\ts(x_R, e)$.
\end{proof}

\begin{lemma}
For every positive integer $n\geq 2$, the socket-width of both the determinant and the permanent of an $n\times n$ matrix is at least $\binom{n}{\lceil n/3 \rceil}$.
\end{lemma}
\begin{proof}
  Let $\ts$ be a socket tree for the permanent, let $e = \{x_R,
  x_C\}$ be an arbitrary edge in $\ts$, and let $k = |L(x_R, e)|$ 
be the number of
  leaves in $\ts(x_R, e)$.  We now show that $\rk(M(\ts, e)) \ge
  \binom{n}{k}$.

  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(x_R, e)$ are rows $1$ to $k$, and the leaves of $\ts(x_C,
  e)$ are rows $k+1$ to $n$.  The rows of $M(\ts, e)$ are indexed by
  a tuple $j_R = (i_1, \ldots, i_k) \in [n]^k$, and the columns are indexed by a
  tuple $j_C = (i_{k+1}, \ldots, i_n) \in [n]^{n-k}$.  The entry of
  $M(\ts, e)$ at position $(j_R, j_C)$ is $1$ if $(i_1, i_2, \ldots,
  i_n)$ is a permutation.  For any set $U \in \binom{[n]}{k}$, let $u_1 <
  u_2 < \ldots < u_k$ be the elements of $U$ in ascending order and
  define $j_R(U) = (u_1, \ldots, u_k)$; let $u_{k+1} < u_{k+2} < \ldots < u_{n}$ be the elements of $[n]
  \setminus U$ in ascending order and define $j_C(U) = (u_{k+1}, u_{k+2}, \ldots,
  u_n)$.

  For $U_1, U_2 \in \binom{[n]}{k}$, the entry of $M(\ts, e)$ at position $(j_R(U_1),
  j_C(U_2))$ equals $1$ if $U_1 = U_2$, and $0$ otherwise. This
  induces a $\binom{n}{k} \times \binom{n}{k}$ identity submatrix
  of $M(\ts, e)$, implying $\rk(M(\ts, e)) \ge \binom{n}{k}$.

  By \expref{Claim}{claim:balanced edge}, $\ts$ has an edge $e$ with $n/3
  \le k < 2n/3$.  For that edge, $\rk(M(\ts, e)) \ge \binom{n}{k} \ge \binom{n}{\lceil n/3 \rceil}$, 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.
\end{proof}

The preceding proof is similar to a lower bound by Nisan
(\cite{Nisan91}, Lemma 2) used to obtain lower bounds for algebraic
branching programs.  But the lower bounds obtained there can be made
as sharp as $\Omega(2^n)$ whereas in our setting, we cannot rule out
the possibility of a tensor network that avoids splitting the $n$
variables in two approximately equal size parts.  This means that the best we can
obtain with our current method is $\binom{n}{\lceil n/3 \rceil}$
instead of $\binom{n}{n/2}$.

%
\subsection{\texorpdfstring{$P$-linear}{P-linear} forms}

Suppose $\ts$ is a socket tree for a $P$-linear form for a $k$-uniform
hypergraph $P$ on $v$ vertices.
Recall that the sockets of this form correspond to the elements
of $E(P) \subseteq \binom{[v]}{k}$.
Given an edge $e \in E(\ts)$ and a vertex $x
\in V(\ts)$, we write \[U(x, e)=\bigcup_{S \in L(x,e)} S \subseteq [v].\]

\begin{claim}
  \label{claim:binom form sockwidth lb 1}
  Let $\ts$ be a socket tree for the $P$-linear form of order $n$.
  Let $e =
  \{x_R, x_C\} \in E(\ts)$ and suppose $|U(x_C, e) \cap U(x_R, e)|= u$.
  Then the socket width of $\ts$ is at least $w(\ts) \ge n^{u}$.

\end{claim}

\begin{proof}
  Let $m = n^u$. We show that $\rk(M(\ts, e)) \ge
  m$ by identifying an $m \times m$ identity submatrix of $M(\ts, e)$.

  %
  %
  Define $E_R = \{\,(S, i) \mid S \in L(x_R, e), i \in S\,\}$
  %
  to be the modes contained in the sockets on the $x_R$ side of $e$, and analogously %
 %
  %
  $E_C
  = \{\,(S, i) \mid S \in L(x_C, e), i \in S\,\}$.
  %

  The rows of $M(\ts, e)$ are indexed by $J(E_R)$ and the columns are indexed by $J(E_C)$. We will consider an $m \times m$ submatrix of $M(\ts, e)$ whose rows and columns are indexed by the elements $\sigma \in \prod_{i \in A} [n_i]$. More specifically, each row of the submatrix is indexed by $j_R$ where $j_R|_{(S,i)}=\sigma|_i$ for $i \in A$, and $j_R|_{(S,i)} = 1$ for $i \not \in A$. Each column is indexed by $j_C$ where $j_C|_{(S,i)}=\sigma|_i$ for $i \in A$ and $j_C|_{(S,i)}=1$  for $i \not \in A$.

The value of the submatrix at position $(j_{R}, j_{C})$ is $1$ if there exists $\sigma \in \prod_{i \in A} [n_i]$ such that $j_R|_{(S,i)}=\sigma|_i$ and $j_C|_{(S,i)}=\sigma|_i$ for all $i \in A$ and $0$ otherwise. We obtain
  an $m \times m$ identity matrix as desired.
\end{proof}

From this claim, the branchwidth-based lower bound is immediate.

\begin{lemma}
  \label{lem:lb-binom-2}
  For any hypergraph $P$, the socket width of the $P$-linear form
  of order $n$ is at least $n^{\bw(P)}$.
\end{lemma}
\begin{proof}
  Any socket tree for a $P$-linear form can be directly
  viewed as a branch decomposition of $P$.  Thus, by definition every
  socket tree for the form has an edge $e = \{x_R, x_C\}$ where
  $|U(x_C,e) \cap U(x_R,e)| \ge \bw(P)$, and the lemma now follows
  from \expref{Claim}{claim:binom form sockwidth lb 1}.
\end{proof}

For counting homomorphisms of hypergraph cliques, that is,
the $P$-linear form for the complete $k$-uniform hypergraph
$P=\binom{[v]}{k}$ on $v$ vertices, we need the
following simple lower bound on the branchwidth of complete
hypergraphs (which is most likely known, but we are not aware of a
reference).

\begin{lemma}
  For $v > k \ge 3$, the complete $k$-uniform hypergraph on $v$ vertices has branchwidth $v$.
\end{lemma}

\begin{proof}
  Let $T$ be an arbitrary branch decomposition of the hypergraph.
We claim that there always
exists an edge $e^* = \{x^*_R, x^*_C\}$ such that $U(x^*_R, e^*) = U(x^*_C, e^*) = [v]$, implying that the width of the decomposition is at least $v$.
Towards establishing this claim, we first observe that for every edge $e = \{x_R, x_C\}$,
at least one of
  $U(x_R, e)$ and $U(x_C, e)$ is equal to $[v]$. Indeed, assume towards contradiction
  that there is an edge $e = \{x_R, x_C\}$ with
  $i_1 \not\in U(x_R, e)$ and $i_2 \not\in U(x_C, e)$ for some not
  necessarily distinct $i_1, i_2 \in [v]$.  Since $k \ge 2$, there exists
  an edge $S \supseteq \{i_1, i_2\}$, and that edge must appear in
  either $\ts(x_R, e)$  or $\ts(x_C,  e)$, violating the assumption.

  Now suppose for contradiction that the claim about the existence of $e^*$ does not hold.
  Direct each edge towards the subtree which covers $[v]$ (which, by the observation above, always exists).  For
  example, if $U(x_R, e) = [v]$ and $U(x_C, e) \ne [v]$ then $e$ is
  directed towards $x_R$.

   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 edge, which covers $k < v$ elements.  Thus $x^*$
  has degree $3$.  Let the three edges incident to $x^*$ be $e_1 =
  \{x^*, y_1\}$, $e_2 = \{x^*, y_2\}$ and $e_3 = \{x^*, y_3\}$.  Since
  all the edges are directed towards $x^*$ there are $i_1, i_2, i_3
  \in [v]$ such that $i_1 \not\in S(y_1, e_1)$, $i_2 \not\in S(y_2,
  e_2)$ and $i_3 \not\in S(y_3, e_3)$.  Since $k \ge 3$ there exists an
  edge $S \supseteq \{i_1,i_2,i_3\}$.  But now the edge $S$ cannot appear in any of the subtrees rooted at $y_1$, $y_2$, or $y_3$.
  Since these three subtrees together cover all leaves, this yields
  the desired contradiction and we conclude that there must exist an
  edge $e^* = \{x^*_R, x^*_C\}$ such that $U(x^*_R, e^*) = U(x^*_C, e^*) = [v]$
  and therefore the branchwidth is $v$.
\end{proof}


\subsection{Kruskal operator}

We say that an $\ell$-linear Kruskal operator is \emph{$n$-uniform} if
the lengths of the modes satisfy $n=n_1=n_2=\cdots=n_\ell$.

\begin{lemma}
For positive integers $n$ and $r$, the socket-width of an $n$-uniform $\ell$-linear Kruskal operator is at least $\max\left(n^{\ell}, n^{\lceil\ell/2\rceil}r\right)$.
\end{lemma}
\begin{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 \times n \times \cdots \times n$ ($\ell$
  times) that is obtained by applying the Kruskal operator to the input matrices
  $A^{(i)}$ of shape $n \times r$, where $1 \le i \le \ell$.

  Consider the neighbor $x$ of the output socket.  It has three
  neighbors: the output socket leaf, and two other vertices $x_R$ and
  $x_C$.  Either the subtree rooted at $x_R$ or the one rooted at $x_C$
  must contain $u \geq \lceil \ell/2 \rceil$ input sockets (since
  together they contain all $\ell$ input sockets).  Let $e$ be the
  edge leading to that subtree.

  We claim that $\rk(M(\ts, e)) \ge n^u r$.  Suppose without loss of
  generality that the input sockets $A^{(1)}, \ldots, A^{(u)}$ are in
  the subtree rooted at $x_R$, and that the input sockets $A^{(u+1)},
  \ldots, A^{(\ell)}$ 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 $(i_1, j_1, \ldots, i_u, j_u)$ where each
  $i_s \in [n]$ and each $j_t \in [r]$. Each column is indexed by
  a sequence of $\ell + 2(n-u)$ indices $(i_1', \ldots, i_\ell';$ $
  i_{u+1}, j_{u+1}, \ldots, i_{\ell}, j_{\ell})$ where each $i_s, i'_{s'} \in [n]$
  and each $j_t \in [r]$.  An entry of $M(\ts, e)$ is $1$ if
  and only if $i_1' = i_1, i_2' = i_2, \ldots, i_\ell' = i_\ell$, and
  $j_1 = j_2 = \ldots = j_\ell$.

  For any $i_1, \ldots, i_u \in [n]$ and $j \in [r]$, consider the row index $(i_1, j, i_2, j, \ldots, i_u, j)$ and the column
  index $(i_1, i_2, \ldots, i_u, 1, 1, \ldots, 1; 1, j, 1, j, \ldots,
  1, j)$.  The
  $n^u r \times n^ur$ submatrix of $M(\ts, e)$ induced by these sets of
  row and column indices is the identity matrix, thus $\rk(M(\ts, e))
  \ge n^u r$ as desired.

  For the $n^{\ell}$ lower bound, we
  instead consider the edge $e'$ joining $x$ with the output socket.
  Now the rows are indexed by $(i_1, j_1, i_2, j_2, \ldots, i_\ell, j_\ell)$  and the
  columns by $(i_1', \ldots, i_\ell')$.  The
  $n^\ell \times n^\ell$ identity submatrix is obtained by taking for
  every $i_1, \ldots, i_\ell \in [n]$, the row $(i_1, 1, i_2, 1, \ldots, i_\ell, 1)$ and the column $(i_1, \ldots, i_\ell)$.
\end{proof}




%

\appendix


\section{Background on tensor networks}

\label{sect:exec}

This appendix summarizes some results on tensor network contractions, minimum-cost executions, and explains the connection between the Holant framework and tensor networks.   In the language of graphical models, computing the value of a tensor network is known as the sum-product inference task and the results in \expref{Appendices}{sec:invariance_property} \expref{and}{sect:structure_min_cost_execution} can be found in~\cite[Part II]{KollerF2009}.

\subsection{Invariance property} \label{sec: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.

\begin{lemma}[Invariance]
\label{lem:invariance}
Let $D$ be a tensor network. For all nonempty $W\subseteq V(D)$ it holds that $T(D)=T(D/W)$.
\end{lemma}
\begin{proof}
Let $W\subseteq V(D)$ be nonempty, let $w$ be the vertex that replaces $D[W]$ in  $D/W$ and let $i\in J(B(D/W))=J(B(D))$.
From \eqref{eq:induced}, \eqref{eq:tensor-rep}, \expeqref{and}{eq:contraction},
it follows that
\[
\begin{split}
T(D/W)_i
&=
\sum_{j\in J(E(D/W)\setminus B(D/W))}
\prod_{v\in (V(D)\setminus W) \cup \{w\}}T(v)_{ij}\\
&=
\sum_{j\in J(E(D/W)\setminus B(D/W))}
T(w)_{ij}\prod_{v\in V(D)\setminus W}T(v)_{ij}\\
&=
\sum_{j\in J(E(D/W)\setminus B(D))}
T(D[W])_{ij}\prod_{v\in V(D)\setminus W}T(v)_{ij}\\
&=
\sum_{j\in J(E(D/W)\setminus B(D))}\
\sum_{j'\in J(E(D[W])\setminus B(D[W]))}\
\prod_{w\in W}T(w)_{ijj'}
\prod_{v\in V(D)\setminus W}T(v)_{ij}\\
&=
\sum_{j\in J(E(D/W)\setminus B(D))}\
\sum_{j'\in J(E(D[W])\setminus B(D[W]))}\
\prod_{v\in V(D)}T(v)_{ijj'}\\
&=
\sum_{j''\in J(E(D)\setminus B(D))}\
\prod_{v\in V(D)}T(v)_{ij''}\\
&=T(D)_i\,.
\end{split}
\]
\end{proof}


\subsection{The structure of a minimum-cost execution} \label{sect:structure_min_cost_execution}

In this section, we analyze the structure of a minimum-cost execution. In particular, we prove \expref{Lemma}{lem:binary}, which states that each contracted set has size at most two, and also show that one can always contract adjacent vertices in a network.

\BinaryExecutionLemma* \label{lem:binary_appendix}

\begin{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 hyperedges incident to a vertex can 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=\{w_1,w_2,\ldots,w_s\}$ of size at least $s\geq 3$, and let $w$ be the new vertex after this contraction. Then we can replace the contraction by $W$ with
two contractions by $W'=\{w_1,w_2,\ldots,w_{s-1}\}$ and $W''=\{w,w_s\}$ without increasing the
cost of the execution. The cost of contracting $W'$ is less than or equal to the cost of contracting $W$, because every hyperedge incident to $W'$ is also incident to $W$. The cost of contracting $W''$ is less than or equal to the cost of contracting $W$, because the set of hyperedges incident to $w$ is contained in the set of hyperedges incident to $W'$. We repeat this procedure until all contracted sets in the
execution have size at most two.
\end{proof}

Two tensors in a tensor network are called \emph{adjacent}
if they are incident to a common mode.

\begin{lemma}[Execution by contracting adjacent tensors]
\label{lem:adjacent}
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.
\end{lemma}
\begin{proof}
Consider a minimum-cost execution of $D$ such that each contracted
set has size two; such an execution exists by \expref{Lemma}{lem:binary_appendix}.
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 \emph{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,w_1\},\{uw_1,w_2\}$, $\ldots$, $\{uw_1\ldots w_{s-1},w_s\}$; similarly, let the contraction sets containing $v$ or a descendant of $v$ and not containing a descendant of $u$ be $\{v,z_1\}$, $\{vz_1,z_2\},\ldots$, $\{vz_1\ldots z_{t-1},z_t\}$. Here $w_1,\ldots,w_s,z_1,\ldots,z_t$ can be vertices of $D$ or vertices obtained after contraction steps.  Contracting $\{uw_1\ldots w_s,vz_1 \ldots z_t\}$  gives the vertex $uw_1 \ldots w_s v z_1 \ldots z_t$, which  appears also in the original execution. Hence, after a certain number of 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 $\{uw_1\ldots w_{i-1},w_i\}$ in the modified execution with $1 \leq i \leq s$. There is a $j$ satisfying $1 \leq j \leq t$ so that the original execution contracts $\{uw_1 \ldots w_{i-1}vz_1 \ldots z_j,w_i\}$. Then the cost of contracting $\{uw_1\ldots w_{i-1},w_i\}$ is at most the cost of contracting $\{uw_1 \ldots w_{i-1}vz_1 \ldots z_j,w_i\}$, because every hyperedge incident to the vertex $uw_1\ldots w_{i-1}$ in the modified execution has to be incident to $uw_1 \ldots w_{i-1}vz_1 \ldots z_j$ in the original execution. Otherwise, there would be a hyperedge in $D$ that is incident only to vertices in $\{u,w_1, \ldots, w_{i-1},v,z_1, \ldots, z_j\}$, and in particular both to vertices in $\{u,w_1, \ldots, w_{i-1}\}$ and in $\{v,z_1, \ldots, z_j\}$. This is impossible, because then $uw_1\ldots w_{i-1}$ and $vz_1 \ldots z_j$ would be adjacent vertices in the modified execution, but by assumption $uw_1\ldots w_s$ and $vz_1 \ldots z_t$ are the first adjacent descendants of $u$ and $v$ in the modified execution. Similarly, we can show that the cost of contracting $\{vz_1\ldots z_{j-1},z_j\}$ in the modified execution for $1 \leq j \leq t$ is less than the cost of contracting a set in the original execution.

Second we consider the cost of contracting $\{uw_1\ldots w_s,vz_1 \ldots z_t\}$ in the modified execution. Without loss of generality, we can assume that in the original execution the vertex $uw_1\ldots w_svz_1 \ldots z_t$ is obtained from contracting $\{uw_1\ldots w_svz_1 \ldots z_{t-1}, z_t\}$. We will show that the cost of contracting $\{uw_1\ldots w_s,vz_1 \ldots z_t\}$ in the modified execution is less than or equal to the cost of contracting $\{uw_1\ldots w_svz_1 \ldots z_{t-1}, z_t\}$ in the original execution. Indeed, every hyperedge incident to $uw_1\ldots w_s$ in the modified execution is incident to $uw_1\ldots w_svz_1 \ldots z_{t-1}$ in the original execution, because otherwise there would be a hyperedge in $D$ that is incident only to vertices in $\{u,w_1, \ldots, w_s,v,z_1, \ldots, z_{t-1}\}$, and in particular both to vertices in $\{u,w_1, \ldots, w_s\}$ and $\{v,z_1, \ldots, z_{t-1}\}$. However, by assumption $uw_1\ldots w_s$ and $vz_1 \ldots z_t$ are the first adjacent descendants of $u$ and $v$ in the modified execution. Similarly, every hyperedge incident to $vz_1 \ldots z_t$ in the modified execution is incident to $uw_1\ldots w_svz_1 \ldots z_{t-1}$ or $z_t$ in the original execution, because otherwise there would be a hyperedge in $D$ that is incident only to vertices in $\{u,w_1, \ldots, w_s,v,z_1, \ldots, z_{t-1}\}$, and in particular both to vertices in $\{u,w_1, \ldots, w_s\}$ and $\{v,z_1, \ldots, z_{t-1}\}$. This contradicts that $uw_1\ldots w_s$ and $vz_1 \ldots z_t$ 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.
\end{proof}

\subsection{Holant framework} \label{sec:Holant_theory}

In this section, we elaborate on the connection between tensor networks and the Holant framework. We follow the exposition in~\cite{CaiLX2011}. The main object of the Holant framework is a signature grid. A \emph{signature grid} is a triple $\Omega = (G,\mathcal{F},\pi)$, where $G=(V,E)$ is an undirected graph, $\mathcal{F}$ is a set of functions and $\pi$ assigns to each vertex $v \in V$ a multivariate function $f_v \in \mathcal{F}$ with input variables corresponding to the edges incident to $v$ and taking values in a finite set $S$. The function $f_v$ is called the signature of $v$. The edges of $G$ are considered to be variables that take values in the set $S$. An assignment $\sigma : E \rightarrow S$ gives an evaluation $\prod_{v \in V} f_v(\sigma|E(v))$, where $E(v)$ is the set of edges incident to a vertex~$v$. The Holant of a signature grid is the sum of these evaluations over all the assignments $\sigma$:
$$
\text{Holant}_{\Omega}=\sum_{\sigma:E \rightarrow S} \prod_{v \in V} f_v(\sigma|E(v)).
$$
A generalization of a signature grid is an \emph{$\mathcal{F}$-gate} that additionally allows dangling edges for input and output variables.

Signature grids are special instances of tensor networks with the restriction that all hyperedges are of size two and the index sets associated to different edges are equal. Signature grids correspond to tensor networks with empty boundary; $\mathcal{F}$-gates do not have the restriction. A signature $f_v$ associated to a vertex $v$ in a signature grid corresponds precisely to a tensor $T(v)$ associated to a vertex $v$ in a tensor network.  The Holant of a signature grid is the same as the value of the corresponding tensor network.


\paragraph{Acknowledgements.}  We are grateful to Andreas Bj\"orklund for highlighting branchwidth
to us as a natural parameter to generalize from clique-counting to counting
homomorphisms, and to our anonymous reviewers for their extensive reading of the paper and many helpful suggestions.

\bibliographystyle{tocplain}   %

%
%
%
%
\bibliography{bibstrings,v018a016,bibtail}

%
%
%
%
%
\begin{tocauthors}
\begin{tocinfo}[austrin]
  Per Austrin\\
  Associate professor\\
  School of Electrical Engineering and Computer Science\\
  KTH Royal Institute of Technology\\
  Sweden\\
  austrin\tocat{}kth\tocdot{}se \\   %
  \url{https://www.csc.kth.se/~austrin/}        %
\end{tocinfo}
\begin{tocinfo}[kaski]
  Petteri Kaski\\
  Associate professor\\
  Department of Computer Science\\
  Aalto University\\
  Finland\\
  petteri\tocdot{}kaski\tocat{}aalto\tocdot{}fi \\   %
  \url{https://www.aalto.fi/en/people/petteri-kaski}   %
\end{tocinfo}
\begin{tocinfo}[kubjas]
  Kaie Kubjas\\
  Assistant professor\\
  Department of Mathematics and Systems Analysis\\
  Aalto University\\
  Finland\\
  kaie\tocdot{}kubjas\tocat{}aalto\tocdot{}fi \\   %
  %
 \url{https://www.kaiekubjas.com}      %
\end{tocinfo}

\end{tocauthors}

%
%
%
%
%
%
%
%
%
%
%
%
%
%
\begin{tocaboutauthors}
\begin{tocabout}[austrin]  %
  \textsc{Per Austrin} graduated from
  \href{https://www.kth.se/}{KTH Royal Institute of Technology} in 2008;
  his advisor was %
  %
  \href{https://people.kth.se/~johanh/}{Johan H\aa{}stad}.
   %
  The subject of his thesis was
  hardness of approximation and discrete harmonic analysis.
  In his spare time he sometimes enjoys algorithmic programming contests.
\end{tocabout}

\begin{tocabout}[kaski]  %
\textsc{Petteri Kaski} graduated from the %
  %
  %
  %
  %
  \href{https://www.aalto.fi/en}{Helsinki University of Technology}
  %
  in 2005;
his advisor was %
  %
  \href{https://users.aalto.fi/~pat/}{Patric \"Osterg\aa{}rd}.
  %
  %
  The subject of his thesis was
  algorithms for classification of combinatorial objects. He enjoys 
  the interplay of algorithms, algebra, and combinatorics.
\end{tocabout}

\begin{tocabout}[kubjas]  %
  \textsc{Kaie Kubjas}
  graduated from the  %
  \href{https://www.fu-berlin.de/en/index.html}{Free University of Berlin}
  in 2013; her advisors were
  %
   \href{https://www.mi.fu-berlin.de/en/math/groups/ag-diskret-algebra-geom/members/Professoren/christian_haase.html}{Christian Haase} 
   %
   and %
   %
   %
    %
   \href{http://www.math.fu-berlin.de/altmann/}{Klaus Altmann}. 
   %
The subject of her thesis was algebraic and combinatorial aspects 
of group-based models.
    She enjoys applying algebraic geometry to other fields.
  %
  %
  %
  %
  %
  %
Kubjas discovered her love for mathematics in her school years in Tartu,
Estonia under the guidance and mentoring of her mathematics teachers 
Reene \~{O}igus and
\href{https://www.tartu.ee/et/tunnustatud-isikud/hele-kiisel}{%
Hele Kiisel}.  %
Thanks to the encouragement and support
of her teachers, Kubjas got involved in mathematics competitions.
  %
\end{tocabout}
\end{tocaboutauthors}

\end{document}
