Opening Yao's Minimax Theorem and $\mathrm{IP}_2$'s Communication Complexity
Yao's Minimax Theorem and 's Communication Complexity
- Length
- 20 min
- Level
- Graduate
- Recorded
- Carnegie Mellon University2020
Chapter 1 of 4: Distributional communication complexity
Yao's Minimax Theorem converts lower bounds for randomized communication complexity into lower bounds for deterministic protocols facing a single hard input distribution. O'Donnell defines distributional communication complexity, where a deterministic protocol must succeed with bounded error under a fixed distribution. Yao's principle then equates the two measures. With the uniform distribution as the hard case, O'Donnell proves that inner product mod 2 requires linear randomized communication. The proof splits a protocol into combinatorial rectangles, then uses Fourier analysis and Parseval's formula to bound each rectangle's discrepancy in the Hadamard matrix. A closing remark explains why disjointness resists product distributions and needs information theory.
Your comment is kept while you sign up.Sign in
Bounds rectangle discrepancy with Parseval's formula to show inner product mod 2 needs linear communication.
Yao's Minimax Theorem converts lower bounds for randomized communication complexity into lower bounds for deterministic protocols facing a single hard input distribution. O'Donnell defines distributional communication complexity, where a deterministic protocol must succeed with bounded error under a fixed distribution. Yao's principle then equates the two measures. With the uniform distribution as the hard case, O'Donnell proves that inner product mod 2 requires linear randomized communication. The proof splits a protocol into combinatorial rectangles, then uses Fourier analysis and Parseval's formula to bound each rectangle's discrepancy in the Hadamard matrix. A closing remark explains why disjointness resists product distributions and needs information theory.
This lecture
Lecture 75 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.