On the Communication Complexity of Equality

Status
Live
Title
On the Communication Complexity of Equality
Date
04 Oct, 2021 ⸱
Excerpt
Published
Oct 4, 2021
Tags
exportober
exposition
sketchnotes
Feature on homepage
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.