Bernhard Haeupler: How to Have a Conversation Despite Noise

Error correcting codes have transformed the way we transfer information. In particular, they give computationally efficient ways to protect one-way communications against noise by adding minimal amounts of redundancy. This talk will survey and explain recent results on coding schemes that do the same for interactive communications, that is, which protect interactive conversations against arbitrary errors/noise. The interactive setting is much harder than its classic one-way counterpart because a single (entirely) corrupted message can completely derail a conversation. In addition to that, decisions on when and how to add redundancy become harder because parties do not know in advance what they will send / talk about in a conversation.

This will be an interactive board talk which will briefly recall some old(er) results which show the existence/feasibility of coding schemes for conversations but then focus on understanding brand-new results [Ghaffari, H., Sudan, STOC’14; Ghaffari, H., FOCS’14; H., FOCS’14] which include the first computationally efficient coding schemes tolerating the maximal amount of noise in various settings as well as the first coding schemes with optimal communication rate for random and adversarial errors.

Come and join the fun! No prior knowledge on the topic is required/expected.