"Reconstruction algorithms for low-rank tensors"
Shubhangi Saraf (Rutgers)
Monday, February 22th 2021, 2-3pm
Abstract:
In this talk we will discuss new and efficient black-box reconstruction algorithms for some classes of depth-3 arithmetic circuits. As a consequence, we will show how to obtain the first randomized polynomial-time 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 constant-rank tensor.
Based on joint work with Vishwas Bhargava and Ilya Volkovich