Opening Communication Complexity of Equality
Communication Complexity of Equality
- Length
- 15 min
- Level
- Graduate
- Recorded
- Carnegie Mellon University2020
Chapter 1 of 4: Before the lecture
The communication complexity of Equality asks how many bits Alice and Bob must exchange to decide whether their -bit strings match. O'Donnell starts from the degree mantra: a nonzero univariate polynomial of degree at most over a field has at most roots. Deterministic protocols need bits, but randomness cuts the cost sharply. Each party reads its string as the coefficients of a polynomial, and the two evaluate at a shared random field element. Distinct strings give a nonzero difference polynomial with at most roots, so a field of size about keeps the error below . Part of CMU 15-750, A Theorist's Toolkit, the session assumes basic finite fields, polynomial division and probability.

Your comment is kept while you sign up.Sign in
Beats the -bit deterministic bound for Equality by evaluating string polynomials at a shared random field point.
The communication complexity of Equality asks how many bits Alice and Bob must exchange to decide whether their -bit strings match. O'Donnell starts from the degree mantra: a nonzero univariate polynomial of degree at most over a field has at most roots. Deterministic protocols need bits, but randomness cuts the cost sharply. Each party reads its string as the coefficients of a polynomial, and the two evaluate at a shared random field element. Distinct strings give a nonzero difference polynomial with at most roots, so a field of size about keeps the error below . Part of CMU 15-750, A Theorist's Toolkit, the session assumes basic finite fields, polynomial division and probability.
This lecture
Lecture 29 of 89 of A Theorist's Toolkit.
Choose a node to see how it connects to this lecture. What comes before is on the leftat the top. What comes after is on the rightat the bottom. The ring is what it teaches. People and places are above. Other lectures and books are below.
Press a chosen node again to open it.