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
