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, …, 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.