Theory of Computing
-------------------
Title     : Tensor Network Complexity of Multilinear Maps
Authors   : Per Austrin, Petteri Kaski, and Kaie Kubjas
Volume    : 18
Number    : 16
Pages     : 1-54
URL       : https://theoryofcomputing.org/articles/v018a016

Abstract
--------

We study _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.

  1. [(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. 
  2. [(b)] An $\Omega(2^{0.918n})$ time lower bound for the 
determinant and the permanent of an $n \times n$ matrix.