Tensor network complexity of multilinear maps

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Researchers

Research units

  • KTH Royal Institute of Technology
  • Sorbonne Université

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ω+ϵ) time matrix multiplication, and in addition many other algorithms such as O(nlog n) time discrete Fourier transform and O(2n) 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(ω+ϵ)t) time algorithms for counting 3t-cliques can be implemented with tensor networks, even though the underlying tensor has border rank n3t 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(ω+ϵ) 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: (a) an Ω(nbw(P)) time lower bound for counting homomorphisms from P to an n-vertex graph, matching the upper bound if ω = 2. In particular for P a v-clique this yields an Ω(nd2v/3e) time lower bound for counting v-cliques, and for P a k-uniform v-hyperclique we obtain an Ω(nv) 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. (b) an Ω(20.918n) time lower bound for the permanent of an n × n matrix.

Details

Original languageEnglish
Title of host publication10th Innovations in Theoretical Computer Science, ITCS 2019
EditorsAvrim Blum
Publication statusPublished - 1 Jan 2019
MoE publication typeA4 Article in a conference publication
EventInnovations in Theoretical Computer Science Conference - San Diego, United States
Duration: 10 Jan 201912 Jan 2019
Conference number: 10

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Volume124
ISSN (Print)1868-8969

Conference

ConferenceInnovations in Theoretical Computer Science Conference
Abbreviated titleITCS
CountryUnited States
CitySan Diego
Period10/01/201912/01/2019

    Research areas

  • Arithmetic complexity, Lower bound, Multilinear map, Tensor network

ID: 36033058