Deterministic Communication Complexity - Lecture 23b of CS Theory Toolkit

Explore the fundamentals of deterministic communication complexity in this 37-minute lecture from Carnegie Mellon University's graduate course "CS Theory Toolkit." Delve into key concepts such as communication protocols, communication matrices, combinatorial rectangles, and the deterministic communication complexity of equality. Examine the Log Rank conjecture and its implications. Learn from Professor Ryan O'Donnell as he covers essential topics for research in theoretical computer science. Gain insights from recommended resources like Kushilevitz and Mansour's "Communication Complexity" and Rao and Yehudayoff's "Communication Complexity and Applications." Access additional course materials through CMU's Diderot system for a comprehensive understanding of this critical area in computer science theory.

Intro
Communication Protocol
Communication Matrix
Communication Problem
Partitioning
Hypothetical
Partitions
Communication Protocols
Combinatorial Rectangle
Mondrian Style
Theorem
Alternative Proof
Log rank conjecture