Lossless interactive source coding: Zero error coding, the CFO problem. Lossless Interactive function computation: Information complexity, internal and external information, protocol compression, direct sum and product theorems, coding over networks. Lossy interactive source coding and computation: Rates for a fixed number of rounds, the limit of infinite rounds. Single-user communication with feedback: Posterior matching, Burnashev exponent, channels with memory, Colored Gaussian channels, finite state channels, universal communications. Multiuser communication with feedback: Capacity bounds for the Broadcast channel, MAC channel, and interference channel, noisy and generalized feedback. The two-way channel: Shannon inner and outer capacity bounds, directed information characterization, schemes for the binary multiplying channel. Interactive protocols for noisy computation over binary symmetric channels: Reliable simulation via tree codes, bounds on the interactive channel capacity. Discussion of open problems.

Course significance:

The last decade has seen a growing interest in the study of the fundamental limits of interactive compression, computation, and communications, with the goal of better understanding the gains in rate, reliability, and robustness offered by interactive protocols. These questions constitute a natural extension of classical information theory problems which have traditionally focused on one-way flow of information. The purpose of this course is to present and discuss information theoretic aspects of interaction recently investigated in both the information theory and communication complexity literature. This is a young field with many recent breakthroughs and numerous intriguing problems; the time is ripe for a comprehensive course on the subject, which I believe will be of much interest to graduate students in information theory and communications.