Tensor reconstruction beyond constant rank

Abstract 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: A randomized algorithm that reconstructs polynomials computed by multilinear $$\Sigma ^{[k]}\prod ^{[d]}\Sigma $$ Σ [ k ] ∏ [ d ] Σ circuits in time $$\textsf{poly}(n,d,c) \cdot k^{k^{k^{k^{O(k)}}}}$$ poly ( n , d , c ) · k k k k O ( k ) , A randomized algorithm that reconstructs polynomials computed by set-multilinear $$\Sigma ^{[k]}\prod ^{[d]}\Sigma $$ Σ [ k ] ∏ [ d ] Σ circuits in time $$\textsf{poly}(n,d,c) \cdot k^{k^{k^{k^{O(k)}}}}$$ poly ( n , d , c ) · k k k k O ( k ) , where $$c=\log q$$ c = log q if $$\mathbb {F}=\mathbb {F}_q$$ F = F q is a finite field, and c equals the maximum bit complexity of any coefficient of f if $$\mathbb {F}$$ F