Projekteja vuodessa
Abstrakti
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$.
Alkuperäiskieli | Englanti |
---|---|
Artikkeli | 16 |
Sivut | 1-54 |
Sivumäärä | 54 |
Julkaisu | THEORY OF COMPUTING |
Vuosikerta | 18 |
DOI - pysyväislinkit | |
Tila | Julkaistu - 18 kesäk. 2022 |
OKM-julkaisutyyppi | A1 Julkaistu artikkeli, soviteltu |
Sormenjälki
Sukella tutkimusaiheisiin 'Tensor Network Complexity of Multilinear Maps'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.Projektit
- 1 Päättynyt
-
TAPEASE: Theory and Practice of Advance Search and Enumeration
01/01/2014 → 31/01/2019
Projekti: EU: ERC grants