Tensor network complexity of multilinear maps
share
We study tensor networks as a model of arithmetic computation for evaluating multilinear maps. This model turns out to be strong enough to capture the current best algorithms for a variety of problems, e.g., O(n^ω + ϵ) time matrix multiplication, O(n n) time discrete Fourier transform, O(n^(ω+ϵ)t + j) time (3t+j)-clique counting and O^*(2^n) time for computing the permanent of a matrix. While powerful, the model still has limitations, and we are able to show a number of unconditional lower bounds for various linear maps, including: (a) an Ω(n^ 2v/3 ) time lower bound for v-clique, matching the upper bound if ω = 2. (b) an Ω(2^0.918n) time lower bound for the permanent of an n × n matrix. (c) an Ω(n^4) time lower bound for the trilinear map D_ijk = ∑_l A_ijlB_ikl C_jkl generalizing matrix multiplication, taking three n × n × n tensors A, B, C and producing an n × n × n tensor D, ruling out tensor networks as an approach to obtaining non-trivial algorithms for hyperclique counting and the Max-3-CSP problem.
READ FULL TEXT