Information Theory in Computational Complexity

Lecture 1: Information Theory in Computational Complexity I
Lecture 2: Information Theory in Computational Complexity II
Lecture 3: Information Theory in Computational Complexity III
Lecture 4: Information Theory in Computational Complexity IV
This series of talks is part of the Information Theory Boot Camp. Videos for each talk will be available through the links above.

Speaker: Jaikumar Radhakrishnan, Tata Institute of Fundamental Research and Shachar Lovett, UC San Diego

We will begin with a review of communication complexity and its applications. We will discuss information theoretic methods for showing lower bounds in communication complexity, and discuss in detail tools such as round elimination and information cost and message compression, leading to recent direct sum theorems.