Tutorial on Coding for Interactive Communication: Introduction and Overview

Although we understand how to send single messages in a way that is resilient to errors, the interactive setting is much less understood. In this introductory talk, we will define the problem of correcting errors in interactive communication (first considered by Schulman), and outline the plan for the rest of the tutorial.

Several recent works will be discussed:

1. The definition and construction of tree-codes (first used by Schulman to give a solution to this problem)
2. A way to use tree codes to recover from errors [Braverman-Rao]
3. Applications. How to recover from short-circuit errors in circuits [Kalai-Lewko-Rao], how to embed any graph metric into l1 [Lee-Mesmay-Moharrami]
4. A candidate explicit construction of tree codes [Moore-Schulman]