Information Theory in Computer Science
This note explains the
following topics: Shearer's Lemma, Entropy, Relative Entropy, Hypothesis
testing, total variation distance and Pinsker's lemma, Stability in Shearer's
Lemma, Communication Complexity, Set Disjointness, Direct Sum in Communication
Complexity and Internal Information Complexity, Data Structure Lower Bounds via
Communication Complexity, Algorithmic Lovasz Local Lemma, Parallel Repetition
Theorem, Graph Entropy and Sorting.
Author(s): Madhu Sudan
NA Pages