We give reconstruction algorithms for subclasses of depth-$3$ arithmetic circuits. In particular, we obtain the first efficient algorithm for finding tensor rank, and an optimal tensor decomposition as a sum of rank-one tensors, when given black-box access to a tensor of super-constant rank. Specifically, we obtain the following results:
1. A deterministic algorithm that reconstructs polynomials computed by $\Sigma^{[k]}\bigwedge^{[d]}\Sigma$ circuits in time $\mathrm{poly}(n,d,c) \cdot \mathrm{poly}(k)^{k^{k^{10}}}$,
2. A randomized algorithm that reconstructs polynomials computed by multilinear $\Sigma^{[k]}\prod^{[d]}\Sigma$ circuits in time $\mathrm{poly}(n,d,c) \cdot k^{k^{k^{k^{O(k)}}}}$,
3. A randomized algorithm that reconstructs polynomials computed by set-multilinear $\Sigma^{[k]}\prod^{[d]}\Sigma$ circuits in time $\mathrm{poly}(n,d,c) \cdot k^{k^{k^{k^{O(k)}}}}$,
where $c=\log q$ if $\mathbb{F}=\mathbb{F}_q$ is a finite field, and $c$ equals the maximum bit complexity of any coefficient of $f$ if $\mathbb{F}$ is infinite.
Prior to our work, polynomial time algorithms for the case when the rank, $k$, is constant, were given by Bhargava, Saraf and Volkovich ([BSV21]).
Another contribution of this work is correcting an error from a paper of Karnin and Shpilka [KS09] (with some loss in parameters) that also affected Theorem 1.6 of [BSV21]. Consequently, the results of [KS09, BSV21] continue to hold, with a slightly worse setting of parameters. For fixing the error we systematically study the relation between syntactic and semantic notions of rank of $\Sigma\Pi\Sigma$ circuits, and the corresponding partitions of such circuits.
We obtain our improved running time by introducing a technique for learning rank preserving coordinate-subspaces. Both [KS09] and [BSV21] tried all choices of finding the "correct" coordinates, which, due to the size of the set, led to having a fast growing function of $k$ at the exponent of $n$. We manage to find these spaces in time that is still growing fast with $k$, yet it is only a fixed polynomial in $n$.
