The Communication Complexity of Equality
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.
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