Tensor Network Complexity of Multilinear Maps
Loading...
Access rights
openAccess
publishedVersion
URL
Journal Title
Journal ISSN
Volume Title
A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Authors
Date
Major/Subject
Mcode
Degree programme
Language
en
Pages
54
Series
THEORY OF COMPUTING, Volume 18, pp. 1-54
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 thosethat 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$.Description
| openaire: EC/H2020/748354/EU//NonnegativeRank
Other note
Citation
Austrin, P, Kaski, P & Kubjas, K 2022, 'Tensor Network Complexity of Multilinear Maps', THEORY OF COMPUTING, vol. 18, 16, pp. 1-54. https://doi.org/10.4086/toc.2022.v018a016