Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with tensor decomposition:
TR21-045 | 22nd March 2021
Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich

Reconstruction Algorithms for Low-Rank Tensors and Depth-3 Multilinear Circuits

We give new and efficient black-box reconstruction algorithms for some classes of depth-$3$ arithmetic circuits. As a consequence, we obtain the first efficient algorithm for computing the tensor rank and for finding the optimal tensor decomposition as a sum of rank-one tensors when then input is a {\it constant-rank} tensor. ... more >>>

ISSN 1433-8092 | Imprint