Opening Information Complexity
Information Complexity
- Length
- 28 min
- Level
- Graduate
- Recorded
- Carnegie Mellon University2020
Chapter 1 of 3: Information complexity
Information complexity measures how much a two-party protocol's transcript reveals about Alice's and Bob's inputs under a joint distribution. O'Donnell starts from distributional communication complexity and defines information cost as conditional mutual information between transcript and inputs. He presents the theorem that independent instances cost exactly times one instance. That additivity yields a linear randomized lower bound for Disjointness, using product distributions with near-zero weight on intersecting inputs. The session, from CMU 15-750: A Theorist's Toolkit, ends by equating amortized communication cost with information complexity in the limit of many instances, via protocol compression. Prerequisites are entropy, conditional mutual information and randomized communication complexity.

Your comment is kept while you sign up.Sign in
Derives a linear randomized lower bound for Disjointness from the exact additivity of information cost.
Information complexity measures how much a two-party protocol's transcript reveals about Alice's and Bob's inputs under a joint distribution. O'Donnell starts from distributional communication complexity and defines information cost as conditional mutual information between transcript and inputs. He presents the theorem that independent instances cost exactly times one instance. That additivity yields a linear randomized lower bound for Disjointness, using product distributions with near-zero weight on intersecting inputs. The session, from CMU 15-750: A Theorist's Toolkit, ends by equating amortized communication cost with information complexity in the limit of many instances, via protocol compression. Prerequisites are entropy, conditional mutual information and randomized communication complexity.
An information complexity approach to randomized communication complexity
Braverman, A. Garg, Pankratov, Weinstein '13
Bar-Yossef, Jayram, Kumar, Sivakumar '04
Ma-Ishwar-Gupta, Braverman-Rao '11
This lecture
Lecture 78 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.