Tensor network complexity of multilinear maps

Per Austrin, Petteri Kaski, Kaie Kubjas

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 $…