Projects per year
Abstract
We study tensor networks as a model of arithmetic computation for evaluating multilinear maps.These capture any algorithm based on lowrank 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 thosethat follow from lowrank 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$.
Original language  English 

Article number  16 
Pages (fromto)  154 
Number of pages  54 
Journal  THEORY OF COMPUTING 
Volume  18 
DOIs  
Publication status  Published  18 Jun 2022 
MoE publication type  A1 Journal articlerefereed 
Keywords
 arithmetic complexity
 lower bound
 multilinear map
 tensor network
Fingerprint
Dive into the research topics of 'Tensor Network Complexity of Multilinear Maps'. Together they form a unique fingerprint.Projects
 1 Finished

TAPEASE: Theory and Practice of Advance Search and Enumeration
Kaski, P. (Principal investigator) & Kohonen, J. (Project Member)
01/01/2014 → 31/01/2019
Project: EU: ERC grants