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
constant-rank tensor. More specifically, we provide efficient learning
algorithms that run in randomized polynomial time over general fields and in
deterministic polynomial time over the reals and the complex numbers for the
following classes:
  (1) Set-multilinear depth-$3$ circuits of constant top fan-in
$\Sigma\Pi\Sigma\{\sqcup_j X_j\}(k)$ circuits). As a consequence of our
algorithm, we obtain the first 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) Sums of powers of constantly many linear forms ($\Sigma\wedge\Sigma$
circuits). As a consequence we obtain the first polynomial-time algorithm for
tensor rank computation and optimal tensor decomposition of constant-rank
symmetric tensors.
  (3) Multilinear depth-3 circuits of constant top fan-in (multilinear
$\Sigma\Pi\Sigma(k)$ circuits). 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 (see.
Karnin-Shpilka 09').
  Prior to our work, the only polynomial-time or even subexponential-time
algorithms known (deterministic or randomized) for subclasses of
$\Sigma\Pi\Sigma(k)$ circuits that also work over large/infinite fields were
for the setting when the top fan-in $k$ is at most $2$ (see Sinha 16' and Sinha
20').
