These are some quick sketchnotes based on this lecture by Ryan O’Donnell, a part of the playlist for the awesome CS Theory Toolkit course. You can walk through the arguments below.
I should mention that while the Schwartz-Zippel-DeMillo-Lipton lemma is invoked in the notes below, one could make do with just the fact that over any field $F$, any degree $n$ polynomial has at most $n$ roots, as pointed out by @dsivakumar — thanks!
In the fourth slide from the end, why [DeMillo--Lipton]--Schwartz--Zippel Lemma? You only need that number of roots of a polynomial (over Z mod q) of degree n is no more than n. You don't need D-L/S/Z, which gives a general version for multivariate polynomials, right?
— D. Sivakumar (@dsivakumar) June 6, 2020
Subscribe to our newsletter
Stay updated with the latest articles, tutorials, and insights from our team. We'll never spam your inbox.
By subscribing, you agree to our Privacy Policy and consent to receive updates from our company.