Linear Independence, Alternants, and Applications

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, . . . , f k ∈ 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, . . . , f k are also F(X S)-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.