Shubhangi Saraf (Theory Seminar)

"Reconstruction algorithms for low-rank tensors"

Shubhangi Saraf (Rutgers)
Monday, February 22th 2021, 2-3pm


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