Revised: December 20, 2020

Published: June 22, 2022

**Keywords:**arithmetic complexity, lower bound, multilinear map, tensor network

**Categories:**complexity theory, arithmetic complexity, lower bound, multilinear, tensor, tensor network, counting, homomorphism, branchwidth, permanent

**ACM Classification:**F.1.1, F.2.2, G.2.1, G.2.2

**AMS Classification:**15A69, 68Q17, 68Q25, 68W05, 05C85, 14Q20

**Abstract:**
[Plain Text Version]

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.

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