Linear Independence, Alternants and Applications

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.