Opening Basics of Communication Complexity
Basics of Communication Complexity
- Length
- 20 min
- Level
- Undergraduate
- Recorded
- Carnegie Mellon University2020
Chapter 1 of 4: Before the lecture
Communication complexity counts exchanged bits, not local computation, in O'Donnell's undergraduate-level treatment of the two-party model. O'Donnell contrasts deterministic and randomized protocols for equality and uses disjointness as a starting point for lower bounds.

Your comment is kept while you sign up.Sign in
Defines two-party communication complexity and analyzes the equality, disjointness, and inner-product functions.
Communication complexity counts exchanged bits, not local computation, in O'Donnell's undergraduate-level treatment of the two-party model. O'Donnell contrasts deterministic and randomized protocols for equality and uses disjointness as a starting point for lower bounds.
Communication Complexity
Communication Complexity and Applications
The Probabilistic Communication Complexity of Set Intersection
This lecture
Lecture 73 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.