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. We obtain the following results: 1. A randomized algorithm that reconstructs polynomials computed by multilinear ${\Sigma }^{k]}{\prod }^{[d]}\Sigma$ circuits in time $\mathsf{poly}(n,d,c)\cdot k^{k^{k^{k^{O(k)}}}}$ 2. A randomized algorithm that reconstructs polynomials computed by set-multilinear ${\Sigma }^{k]}{\prod }^{[d]}\Sigma$ circuits in time $\mathsf{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] that 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 study the relation between syntactic and semantic ranks of $\Sigma \Pi \Sigma$ circuits. We obtain our improvement by introducing a technique for learning rank preserving coordinate-subspaces. [KS09] and [BSV21] tried all choices of finding the "correct" coordinates, which led to having a fast growing function of $k$ at the exponent of $n$. We find these spaces in time that is growing fast with $k$, yet it is only a fixed polynomial in $n$.

arXiv commentAbstract shortened to meet arXiv requirements; 56 pages