Tensor Reconstruction Beyond Constant Rank
share
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 deterministic algorithm that reconstructs polynomials computed by Σ^[k]⋀^[d]Σ circuits in time 𝗉𝗈𝗅𝗒(n,d,c) ·𝗉𝗈𝗅𝗒(k)^k^k^10 2. A randomized algorithm that reconstructs polynomials computed by multilinear Σ^k]∏^[d]Σ circuits in time 𝗉𝗈𝗅𝗒(n,d,c) · k^k^k^k^O(k) 3. A randomized algorithm that reconstructs polynomials computed by set-multilinear Σ^k]∏^[d]Σ circuits in time 𝗉𝗈𝗅𝗒(n,d,c) · k^k^k^k^O(k), where c=log q if 𝔽=𝔽_q is a finite field, and c equals the maximum bit complexity of any coefficient of f if 𝔽 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 ΣΠΣ 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.
READ FULL TEXT