In this paper we show that simple semidefinite programs inspired by degree$4$ SOS can exactly solve the tensor nuclear norm, tensor decomposition, andtensor completion problems on tensors with random asymmetric components . This gives the first theoretical guarantees for exact tensorcompletion in the overcomplete regime . This matches the best known results for approximate versions of theseproblems given by Barak \& Moitra (2015) for tensor completion, and Ma, Shi \&Steurer (2016) for . tensor . decomposition . For tensor. completion, weshow that w.h.p. can exactly recover an \$(n\times n\times .

Author(s) : Bohdan Kivva, Aaron Potechin