1 Search Results for "Kubjas, Kaie"

Document
DOI: 10.4230/LIPIcs.ITCS.2019.7
Tensor Network Complexity of Multilinear Maps

Authors: Per Austrin, Petteri Kaski, and Kaie Kubjas

Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)

Abstract
We study tensor networks as a model of arithmetic computation for evaluating multilinear maps. These capture any algorithm based on low border 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 border rank n^{3t} for all t >= 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: b) 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^{ceil[2v/3]}) 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 >= 3, ruling out tensor networks as an approach to obtaining non-trivial algorithms for hyperclique counting and the Max-3-CSP problem. c) an Omega(2^{0.918n}) time lower bound for the permanent of an n x n matrix.
Cite as

Per Austrin, Petteri Kaski, and Kaie Kubjas. Tensor Network Complexity of Multilinear Maps. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 7:1-7:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{austrin_et_al:LIPIcs.ITCS.2019.7,
  author =	{Austrin, Per and Kaski, Petteri and Kubjas, Kaie},
  title =	{{Tensor Network Complexity of Multilinear Maps}},
  booktitle =	{10th Innovations in Theoretical Computer Science Conference (ITCS 2019)},
  pages =	{7:1--7:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-095-8},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{124},
  editor =	{Blum, Avrim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.7},
  URN =		{urn:nbn:de:0030-drops-101006},
  doi =		{10.4230/LIPIcs.ITCS.2019.7},
  annote =	{Keywords: arithmetic complexity, lower bound, multilinear map, tensor network}
}
  • Refine by Author
  • 1 Austrin, Per
  • 1 Kaski, Petteri
  • 1 Kubjas, Kaie

  • Refine by Classification
  • 1 Theory of computation → Computational complexity and cryptography
  • 1 Theory of computation → Design and analysis of algorithms
  • 1 Theory of computation → Models of computation

  • Refine by Keyword
  • 1 arithmetic complexity
  • 1 lower bound
  • 1 multilinear map
  • 1 tensor network

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2019

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact