Opening Deterministic Communication Complexity
Deterministic Communication Complexity
- Length
- 37 min
- Level
- Graduate
- Recorded
- Carnegie Mellon University2020
Chapter 1 of 6: Before the lecture
Deterministic communication complexity measures how many bits two parties with private inputs must exchange to compute a Boolean function. O'Donnell defines a protocol as a binary tree whose nodes name a speaker and a function from that speaker's input to a bit. Each leaf yields a combinatorial rectangle, so a -bit protocol partitions the communication matrix into at most monochromatic rectangles. Counting those rectangles shows that equality on -bit strings needs at least bits. The Mehlhorn-Schmidt theorem then makes the logarithm of the real rank a lower bound. The session closes with the log-rank conjecture of Lovász and Saks and Lovett's 2015 upper bound, assuming basic linear algebra.

Your comment is kept while you sign up.Sign in
O'Donnell proves equality needs bits by counting monochromatic rectangles, then bounds cost below by log rank.
Deterministic communication complexity measures how many bits two parties with private inputs must exchange to compute a Boolean function. O'Donnell defines a protocol as a binary tree whose nodes name a speaker and a function from that speaker's input to a bit. Each leaf yields a combinatorial rectangle, so a -bit protocol partitions the communication matrix into at most monochromatic rectangles. Counting those rectangles shows that equality on -bit strings needs at least bits. The Mehlhorn-Schmidt theorem then makes the logarithm of the real rank a lower bound. The session closes with the log-rank conjecture of Lovász and Saks and Lovett's 2015 upper bound, assuming basic linear algebra.
Mehlhorn-Schmidt '82
This lecture
Lecture 74 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.