Coding for Interactive Communication

In his seminal 1948 paper, Shannon conceived the field of coding theory, allowing a sender to deliver a single message to a receiver, despite noise introduced by the communication links. Unfortunately, coding techniques developed since then are insufficient for modern communication systems, where instead of a sender communicating a message to a receiver, two or more parties are involved in an interaction -- a conversation.

The field of coding for interactive communication aims at solving exactly the above question by obtaining coding schemes that allow two or more parties to complete their conversation despite possible noise in the communication channels. In order to be useful, such coding schemes are required to feature desirable properties such as having an efficient computation time, or adding only a small amount of redundancy (i.e. having a good rate).

In this talk I will describe the realm of interactive coding, and a few of the exciting coding techniques developed in recent years, as well as several of the applications derived from these coding techniques. In particular, I will discuss efficient coding schemes for two parties in the presence of stochastic noise, and upper and lower bounds on the communication (i.e., on the rate) of coding scheme in the multiparty case in the presence of stochastic noise.