A famous theorem of Kruskal gives the simplest and arguably most fundamental criterion under which a tensor is guaranteed a unique minimum-rank decomposition. Kruskal’s condition requires that the sum of the Kruskal ranks {k_i}_{i=1}^m of the components satisfies ∑_{i∈[m]} k_i ≥ 2r + m - 1, where r denotes the rank and m the order of the tensor. However, Kruskal’s original proof and subsequent simplifications/generalizations have remained non-constructive. With the sole exception of the case (k₁ = r, k₂ = r, k₃ = 2), attributed to Jennrich - no algorithm has been established for decomposing tensors under the Kruskal condition without additional assumptions. In fact, whether there exists an efficient algorithm for decomposing a tensor under the Kruskal condition was explicitly posed as an open problem in the work of Bhaskara et al. (COLT 2014). Even slight variations of the Jennrich special case, such as the (r, r-1, 3) case, have remained algorithmically open; specifically, no sub-exponential time bound was known. In this work, we make progress on this problem by giving an elementary, constructive proof of Kruskal’s Theorem for general m-way tensors. Concretely, we give a randomized algorithm that decomposes any tensor satisfying the Kruskal condition by utilizing random projections to map the problem into a geometry of intersecting hyperplanes via a MinRank instance. Specifically for 3-way tensors satisfying k₁+k₂+k₃ = 2r+2, the algorithm achieves a runtime of n^O(k) where k = min(k₁,k₂,k₃). Thus, we extend smoothly beyond the Jennrich special case, achieving polynomial-time complexity for any family of tensors that satisfies the Kruskal condition, provided the least Kruskal rank is bounded.

Abstract. We develop a new technique for analyzing linear independence of multivariate polynomials. One of our main technical contributions is a Small Witness for Linear Independence lemma which states the following. If the polynomials [Formula: see text] over [Formula: see text] are [Formula: see text]-linearly independent then there exists a subset [Formula: see text] of size at most [Formula: see text] such that [Formula: see text] are also [Formula: see text]-linearly independent. We show how to effectively combine this lemma with the use of the alternant matrix to analyze linear independence of polynomials. We also give applications of our technique to the questions of polynomial identity testing and arithmetic circuit reconstruction. (1) We give a general technique for lifting efficient polynomial identity testing algorithms from basic classes of circuits, satisfying some closure properties, to more general classes of circuits. As one of the corollaries of this result, we obtain the first algorithm for polynomial identity testing for depth-4, constant-occur circuits that works over all fields. This strengthens a result by M. Agrawal, C. Saha, R. Saptharishi, and N. Saxena [ SIAM J. Comput., 45 (2016), pp. 1533–1562] that works in the case when the characteristic is 0 or sufficiently large. Another corollary is an identity testing algorithm for a special case of depth-5 circuits. To the best of our knowledge, this is the first algorithm for this class of circuits. (2) We give new and efficient black-box reconstruction algorithms for the class of set-multilinear depth-3 circuits of constant top fan-in, where the set-multilinear variable partition is unknown. This generalizes the results of V. Bhargava, S. Saraf, and I. Volkovich [STOC ’21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021, pp. 809–822] and S. Peleg, A. Shpilka, and B. Volk [15th Innovations in Theoretical Computer Science Conference, ITCS 2024, pp. 87:1–87:20] which work in the case of known variable partition, and correspond to tensor decomposition of constant-rank tensors.

A tensor network is a diagram that specifies a way to "multiply" a collection of tensors together to produce another tensor (or matrix). Many existing algorithms for tensor problems (such as tensor decomposition and tensor PCA), although they are not presented this way, can be viewed as spectral methods on matrices built from simple tensor networks. In this work we leverage the full power of this abstraction to design new algorithms for certain continuous tensor decomposition problems. An important and challenging family of tensor problems comes from orbit recovery, a class of inference problems involving group actions (inspired by applications such as cryo-electron microscopy). Orbit recovery problems over finite groups can often be solved via standard tensor methods. However, for infinite groups, no general algorithms are known. We give a new spectral algorithm based on tensor networks for one such problem: continuous multi-reference alignment over the infinite group SO(2). Our algorithm extends to the more general heterogeneous case.

The dimension of partial derivatives (Nisan and Wigderson, 1997) is a popular measure for proving lower bounds in algebraic complexity. It is used to give strong lower bounds on the Waring decomposition of polynomials (called Waring rank). This naturally leads to an interesting open question: does this measure essentially characterize the Waring rank of any polynomial? The well-studied model of Read-once Oblivious ABPs (ROABPs for short) lends itself to an interesting hierarchy of "sub-models": Any-Order-ROABPs (ARO), Commutative ROABPs, and Diagonal ROABPs. It follows from previous works that for any polynomial, a bound on its Waring rank implies an analogous bound on its Diagonal ROABP complexity (called the duality trick), and a bound on its dimension of partial derivatives implies an analogous bound on its "ARO complexity": ROABP complexity in any order (Nisan, 1991). Our work strengthens the latter connection by showing that a bound on the dimension of partial derivatives in fact implies a bound on the commutative ROABP complexity. Thus, we improve our understanding of partial derivatives and move a step closer towards answering the above question. Our proof builds on the work of Ramya and Tengse (2022) to show that the commutative-ROABP-width of any homogeneous polynomial is at most the dimension of its partial derivatives. The technique itself is a generalization of the proof of the duality trick due to Saxena (2008).

Multivariate multipoint evaluation is the problem of evaluating a multivariate polynomial, given as a coefficient vector, simultaneously at multiple evaluation points. In this work, we show that there exists a deterministic algorithm for multivariate multipoint evaluation over any finite field \(\mathbb {F}\) that outputs the evaluations of an m -variate polynomial of degree less than d in each variable at N points in time, \(\begin{equation*} (d^m+N)^{1+o(1)}\cdot {{\sf poly}}(m,d,\log |\mathbb {F}|), \end{equation*}\) for all \(m\in \mathbb {N}\) and all sufficiently large \(d\in \mathbb {N}\) . A previous work of Kedlaya and Umans (FOCS 2008 and SICOMP 2011) achieved the same time complexity when the number of variables m is at most \(d^{o(1)}\) and had left the problem of removing this condition as an open problem. A recent work of Bhargava, Ghosh, Kumar, and Mohapatra (STOC 2022) answered this question when the underlying field is not too large and has characteristic less than \(d^{o(1)}\) . In this work, we remove this constraint on the number of variables over all finite fields, thereby answering the question of Kedlaya and Umans over all finite fields. Our algorithm relies on a non-trivial combination of ideas from three seemingly different previously known algorithms for multivariate multipoint evaluation, namely the algorithms of Kedlaya and Umans, that of Björklund, Kaski, and Williams (IPEC 2017 and Algorithmica 2019), and that of Bhargava, Ghosh, Kumar, and Mohapatra, together with a result of Bombieri and Vinogradov from analytic number theory about the distribution of primes in an arithmetic progression. We also present a second algorithm for multivariate multipoint evaluation that is completely elementary and, in particular, avoids the use of the Bombieri–Vinogradov theorem. However, it requires a mild assumption that the field size is bounded by an exponential tower in d of bounded height . More specifically, our second algorithm solves the multivariate multipoint evaluation problem over a finite field \(\mathbb {F}\) in time, \(\begin{equation*} (d^m+N)^{1+o(1)}\cdot {{\sf poly}}(m,d,\log |\mathbb {F}|), \end{equation*}\) for all \(m\in \mathbb {N}\) and all sufficiently large \(d\in \mathbb {N}\) , provided that the size of the finite field \(\mathbb {F}\) is at most \((\exp (\exp (\exp (\cdots (\exp (d)))))\) , where the height of this tower of exponentials is fixed.

We develop a new technique for analyzing linear independence of multivariate polynomials. One of our main technical contributions is a Small Witness for Linear Independence (SWLI) lemma which states the following. If the polynomials f1,f2, …, fk ∈ F[X] over X={x1, …, xn} are F-linearly independent then there exists a subset S ⊆ X of size at most k−1 such that f1,f2, …, fk are also F(X∖ S)-linearly independent.

Multipoint evaluation is the computational task of evaluating a polynomial given as a list of coefficients at a given set of inputs. Besides being a natural and fundamental question in computer algebra on its own, fast algorithms for this problem are also closely related to fast algorithms for other natural algebraic questions such as polynomial factorization and modular composition. And while nearly linear time algorithms have been known for the univariate instance of multipoint evaluation for close to five decades due to a work of Borodin and Moenck [ 7 ], fast algorithms for the multivariate version have been much harder to come by. In a significant improvement to the state-of-the-art for this problem, Umans [ 25 ] and Kedlaya & Umans [ 16 ] gave nearly linear time algorithms for this problem over field of small characteristic and over all finite fields, respectively, provided that the number of variables n is at most \(d^{o(1)}\) where the degree of the input polynomial in every variable is less than d . They also stated the question of designing fast algorithms for the large variable case (i.e., \(n \notin d^{o(1)}\) ) as an open problem. In this work, we show that there is a deterministic algorithm for multivariate multipoint evaluation over a field \(\mathbb {F}_{q}\) of characteristic p , which evaluates an n -variate polynomial of degree less than d in each variable on N inputs in time \(\begin{equation*} \left((N + d^n)^{1 + o(1)}\text{poly}(\log q, d, n, p)\right), \end{equation*}\) provided that p is at most d o (1) , and q is at most (exp (exp (exp (...(exp ( d ))))), where the height of this tower of exponentials is fixed. When the number of variables is large (e.g., n ∉ d o (1) ), this is the first nearly linear time algorithm for this problem over any (large enough) field. Our algorithm is based on elementary algebraic ideas, and this algebraic structure naturally leads to the following two independently interesting applications: — We show that there is an algebraic data structure for univariate polynomial evaluation with nearly linear space complexity and sublinear time complexity over finite fields of small characteristic and quasipolynomially bounded size. This provides a counterexample to a conjecture of Miltersen [ 21 ] who conjectured that over small finite fields, any algebraic data structure for polynomial evaluation using polynomial space must have linear query complexity. — We also show that over finite fields of small characteristic and quasipolynomially bounded size, Vandermonde matrices are not rigid enough to yield size-depth tradeoffs for linear circuits via the current quantitative bounds in Valiant’s program [ 26 ]. More precisely, for every fixed prime p , we show that for every constant ɛ > 0, and large enough n , the rank of any \(n \times n\) Vandermonde matrix V over the field \(\mathbb {F}_{p^a}\) can be reduced to ( n /exp (Ω (poly(ɛ)log 0.53 n ))) by changing at most n Θ (ɛ) entries in every row of V , provided a ≤ poly(log n ). Prior to this work, similar upper bounds on rigidity were known only for special Vandermonde matrices. For instance, the Discrete Fourier Transform matrices and Vandermonde matrices with generators in a geometric progression [ 9 ].

An s-sparse polynomial has at most s monomials with nonzero coefficients. The Equivalence Testing problem for sparse polynomials (ETsparse) asks to decide if a given polynomial f is equivalent to (i.e., in the orbit of) some s-sparse polynomial. In other words, given f ∈ 𝔽[𝐱] and s ∈ ℕ, ETsparse asks to check if there exist A ∈ GL(|𝐱|, 𝔽) and 𝐛 ∈ 𝔽^|𝐱| such that f(A𝐱 + 𝐛) is s-sparse. We show that ETsparse is NP-hard over any field 𝔽, if f is given in the sparse representation, i.e., as a list of nonzero coefficients and exponent vectors. This answers a question posed by Gupta, Saha and Thankey (SODA 2023) and also, more explicitly, by Baraskar, Dewan and Saha (STACS 2024). The result implies that the Minimum Circuit Size Problem (MCSP) is NP-hard for a dense subclass of depth-3 arithmetic circuits if the input is given in sparse representation. We also show that approximating the smallest s₀ such that a given s-sparse polynomial f is in the orbit of some s₀-sparse polynomial to within a factor of s^{1/3 - ε} is NP-hard for any ε > 0; observe that s-factor approximation is trivial as the input is s-sparse. Finally, we show that for any constant σ ≥ 6, checking if a polynomial (given in sparse representation) is in the orbit of some support-σ polynomial is NP-hard. Support of a polynomial f is the maximum number of variables present in any monomial of f. These results are obtained via direct reductions from the 3-SAT problem.

Multivariate multipoint evaluation is the problem of evaluating a multivariate polynomial, given as a coefficient vector, simultaneously at multiple evaluation points. In this work, we show that there exists a deterministic algorithm for multivariate multipoint evaluation over any finite field F that outputs the evaluations of an m-variate polynomial of degree less than d in each variable at N points in time $(d^{m}+N)^{1+o(1)}$ poly $(m,\ d,\ \log|\mathbb{F}|)$ for all $m\in \mathbb{N}$ and all sufficiently large $d\in \mathbb{N}$. A previous work of Kedlaya and Umans (FOCS 2008, SICOMP 2011) achieved the same time complexity when the number of variables m is at most $d^{o(1)}$ and had left the problem of removing this condition as an open problem. A recent work of Bhargava, Ghosh, Kumar and Mohapatra (STOC 2022) answered this question when the underlying field is not too large and has characteristic less than $d^{o(1)}$. In this work, we remove this constraint on the number of variables over all finite fields, thereby answering the question of Kedlaya and Umans over all finite fields. Our algorithm relies on a non-trivial combination of ideas from three seemingly different previously known algorithms for multivariate multipoint evaluation, namely the algorithms of Kedlaya and Umans, that of Björklund, Kaski and Williams (IPEC 2017, Algorithmica 2019), and that of Bhargava, Ghosh, Kumar and Mohapatra, together with a result of Bombieri and Vinogradov from analytic number theory about the distribution of primes in an arithmetic progression. We also present a second algorithm for multivariate multipoint evaluation that is completely elementary and in particular, avoids the use of the Bombieri-Vinogradov Theorem. However, it requires a mild assumption that the field size is bounded by an exponential-tower in d of bounded height.

Multipoint evaluation is the computational task of evaluating a polynomial given as a list of coefficients at a given set of inputs. Besides being a natural and fundamental question in computer algebra on its own, fast algorithms for this problem are also closely related to fast algorithms for other natural algebraic questions like polynomial factorization and modular composition. And while nearly linear time algorithms have been known for the univariate instance of multipoint evaluation for close to five decades due to a work of Borodin and Moenck, fast algorithms for the multivariate version have been much harder to come by. In a significant improvement to the state of art for this problem, Umans and Kedlaya & Umans gave nearly linear time algorithms for this problem over field of small characteristic and over all finite fields respectively, provided that the number of variables n is at most do(1) where the degree of the input polynomial in every variable is less than d. They also stated the question of designing fast algorithms for the large variable case (i.e. n ∉ do(1)) as an open problem.

In this paper we study polynomials in VP_{e} (polynomial-sized formulas) and in ΣΠΣ (polynomial-size depth-3 circuits) whose orbits, under the action of the affine group GL^{aff}_n(𝔽) (the action of (A,b) ∈ GL^{aff}_n(𝔽) on a polynomial f ∈ 𝔽[x] is defined as (A,b)∘f = f(A^Tx+b)), are dense in their ambient class. We construct hitting sets and interpolating sets for these orbits as well as give reconstruction algorithms. Specifically, we obtain the following results: 1) For C_n(ℓ_1(x),…,ℓ_n(x)) ≜ Trace(\begin{pmatrix} 𝓁₁(x) & 1 \\ 1 & 0 \end{pmatrix} ⋅ … ⋅ \begin{pmatrix} 𝓁_n(x) & 1 \\ 1 & 0 \end{pmatrix}), where the 𝓁_is are linearly independent linear functions, we construct a polynomial-sized interpolating set, and give a polynomial-time reconstruction algorithm. By a result of Bringmann, Ikenmeyer and Zuiddam, the set of all such polynomials is dense in VP_e [Karl Bringmann et al., 2018], thus our construction gives the first polynomial-size interpolating set for a dense subclass of VP_e. 2) For polynomials of the form ANF_Δ(𝓁₁(x),…,𝓁_{4^Δ}(x)), where ANF_Δ(x) is the canonical read-once formula in alternating normal form, of depth 2Δ, and the 𝓁_is are linearly independent linear functions, we provide a quasipolynomial-size interpolating set. We also observe that the reconstruction algorithm of [Ankit Gupta et al., 2014] works for all polynomials in this class. This class is also dense in VP_e. 3) Similarly, we give a quasipolynomial-sized hitting set for read-once formulas (not necessarily in alternating normal form) composed with a set of linearly independent linear functions. This gives another dense class in VP_e. 4) We give a quasipolynomial-sized hitting set for polynomials of the form f(𝓁₁(x),…,𝓁_{m}(x)), where f is an m-variate s-sparse polynomial. and the 𝓁_is are linearly independent linear functions in n ≥ m variables. This class is dense in ΣΠΣ. 5) For polynomials of the form ∑_{i=1}^{s}∏_{j=1}^{d}𝓁_{i,j}(x), where the 𝓁_{i,j}s are linearly independent linear functions, we construct a polynomial-sized interpolating set. We also observe that the reconstruction algorithm of [Neeraj Kayal and Chandan Saha, 2019] works for every polynomial in the class. This class is dense in ΣΠΣ. As VP = VNC², our results for VP_{e} translate immediately to VP with a quasipolynomial blow up in parameters. If any of our hitting or interpolating sets could be made robust then this would immediately yield a hitting set for the superclass in which the relevant class is dense, and as a consequence also a lower bound for the superclass. Unfortunately, we also prove that the kind of constructions that we have found (which are defined in terms of k-independent polynomial maps) do not necessarily yield robust hitting sets.

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 and for the following classes: 1) Set-multilinear depth-3 circuits of constant top fan-in ((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 ((k) 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 (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 (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’).

We present a deterministic algorithm for reconstructing multilinear ƩпƩп(k) circuits, i.e. multilinear depth-4 circuits with fan-in k at the top + gate. For any fixed k, given black-box access to a polynomial f ϵ 픽[x1, x2, …, xn] computable by a multilinear ƩпƩп(k) circuit of size s, the algorithm runs in time quasi-poly(n, s, |픽|) and outputs a multilinear ƩпƩп(k) circuit of size quasi-poly(n, s) that computes f. Our result solves an open problem posed in [15] (STOC, 2012). Indeed, prior to our work, efficient reconstruction algorithms for multilinear ƩпƩп(k) circuits were known only for the case of k = 2 [15, 52].

In this article, we study the problem of deterministic factorization of sparse polynomials. We show that if f ∈ F[ x 1 , x 2 ,… , x n ] is a polynomial with s monomials, with individual degrees of its variables bounded by d , then f can be deterministically factored in time s poly( d )log n . Prior to our work, the only efficient factoring algorithms known for this class of polynomials were randomized, and other than for the cases of d =1 and d =2, only exponential time-deterministic factoring algorithms were known. A crucial ingredient in our proof is a quasi-polynomial sparsity bound for factors of sparse polynomials of bounded individual degree. In particular, we show that if f is an s -sparse polynomial in n variables, with individual degrees of its variables bounded by d , then the sparsity of each factor of f is bounded by s (9 d 2 log n ) . This is the first non-trivial bound on factor sparsity for d > 2. Our sparsity bound uses techniques from convex geometry, such as the theory of Newton polytopes and an approximate version of the classical Carathéodory’s Theorem. Our work addresses and partially answers a question of von zur Gathen and Kaltofen [1985] who asked whether a quasi-polynomial bound holds for the sparsity of factors of sparse polynomials.

We present a deterministic polynomial time approximation scheme (PTAS) for computing the algebraic rank of a set of bounded degree polynomials. The notion of algebraic rank naturally generalizes the notion of rank in linear algebra, i.e., instead of considering only the linear dependencies, we also consider higher degree algebraic dependencies among the input polynomials. More specifically, we give an algorithm that takes as input a set of polynomials with degrees bounded by d, and a rational number ∊ > 0 and runs in time , where M(n) is the time required to compute the rank of an n × n matrix (with field entries), and finally outputs a number r, such that r is at least (1 – ∊) times the algebraic rank of f. Our key contribution is a new technique which allows us to achieve the higher degree generalization of the results by Bläser, Jindal, Pandey (CCC’17) who gave a deterministic PTAS for computing the rank of a matrix with homogeneous linear entries. It is known that a deterministic algorithm for exactly computing the rank in the linear case is already equivalent to the celebrated Polynomial Identity Testing (PIT) problem which itself would imply circuit complexity lower bounds (Kabanets, Impagliazzo, STOC’03). Such a higher degree generalization is already known to a much stronger extent in the non-commutative world, where the more general case in which the entries of the matrix are given by polysized formulas reduces to the case where the entries are given by linear polynomials using Higman's trick, and in the latter case, one can also compute the exact rank in polynomial time (Garg, Gurvits, Oliviera, Wigderson, FOCS’16, Ivanyos, Qiao, Subrahmanyam, ITCS’17). Higman's trick only preserves the co-rank, hence it cannot be used to reduce the problem of rank approximation to the case when the matrix entries are linear polynomials. Thus our work can also be seen as a step towards bridging the knowledge gap between the non-commutative world and the commutative world.

Constructing r-th nonresidue over a finite field is a fundamental computational problem. A related problem is to construct an irreducible polynomial of degree re (where r is a prime) over a given finite field Fq of characteristic p (equivalently, constructing the bigger field Fqre). Both these problems have famous randomized algorithms but the derandomization is an open question. We give some new connections between these two problems and their variants.