Schwartz-Zippel Lemma

The Schwartz-Zippel lemma is a tool used in probabilistic polynomial identity testing, the problem of deciding whether a multivariate polynomial is identically zero. It states that evaluating a nonzero polynomial at a point chosen at random from a sufficiently large set is very likely to produce a nonzero result, so instead of expanding a polynomial symbolically, which can take exponential time, an algorithm can test it by evaluating it at a few random points. The result was found independently by several people: Jack Schwartz and Richard Zippel published versions of it around 1979 and 1980, Richard DeMillo and Richard Lipton had published an equivalent result in 1978, and Oystein Ore had already proved the finite-field case in 1922. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/