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 f 1 , f 2 , …, f k ∈ F [ X ] over X ={ x 1 , …, x n } are F -linearly independent then there exists a subset S ⊆ X of size at most k −1 such that f 1 , f 2 , …, f k are also F ( X ∖ S )-linearly independent.

Authors

• Vishwas Bhargava
• Shubhangi Saraf
• Ilya Volkovich

Keywords

• Alternant
• Arithmetic Circuits
• Linear Independence
• Polynomial Identity Testing
• Reconstruction