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!