On the Communication Complexity of Equality

On 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. You can walk through the arguments below (or, alternatively, sit back and watch an autoplay version instead — no audio, though).

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 , any degree polynomial has at most roots, as pointed out by @dsivakumar — thanks!

Autoplay edition.

super-embed:<div id="hyvor-talk-view"></div><script async defer type="text/javascript" src="//talk.hyvor.com/web-api/embed.js"></script>