Feasibly Constructive Proof of Schwartz-Zippel Lemma and the Complexity of Finding Hitting Sets

Albert Atserias, Iddo Tzameret

The Schwartz-Zippel Lemma states that if a low-degree multivariate polynomial with coefficients in a field is not zero everywhere in the field, then it has few roots on every finit…