Vishwas Bhargava, Rutgers University

Abstract

Abstract: We give new and efficient black-box reconstruction algorithms for some classes of depth-$3$ arithmetic circuits. As a consequence, we 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 {em constant-rank} tensor. We obtain the following results. 1. We give the first randomized polynomial-time proper learning algorithm for the class of set-multilinear depth-$3$ circuits of constant top fan-in ($SMLSps(k)$ circuits). This result holds over all fields, and in particular over infinite fields such as $R, C$. As a consequence we obtain the first efficient polynomial-time algorithm for tensor rank computation and optimal tensor decomposition of constant-rank tensors. This result holds for $d$ dimensional tensors for any $d$, but is interesting even for $d=3$. 2. We give the first randomized polynomial-time proper learning algorithm for the class of sums of powers of constantly many linear forms ($pow(k)$ circuits). This result holds over all fields of characteristic 0 or large enough characteristic . As a consequence we obtain the first efficient polynomial-time algorithm for tensor rank computation and optimal tensor decomposition of constant-rank symmetric tensors. 3. We give the first randomized polynomial-time proper learning algorithm for the class of multilinear depth-3 circuits of constant top fan-in (multilinear $Sps(k)$ circuits over large fields. Our algorithm works over all fields of characteristic 0 or large enough characteristic. Prior to our work the only efficient algorithms known were over polynomially-sized finite fields cite{KarninShpilka09}. Prior to our work, the only polynomial-time (or even subexponential-time) algorithms known for subclasses of $Sps(k)$ circuits that also work over large/infinite fields were for the setting when the top fan-in $k$ is at most $2$ cite{Sin16, Sin20}.

Location: The Theory of Computing Seminar is being held online. Contact the organizers for the link to the seminar. 

See: https://sites.google.com/view/dimacs-theory-seminar/home