"Interactive Error Correcting Codes and the Magical Power of Adaptivity"
Gillat Kol (Princeton)
Monday, March 8th 2021, 2-3pm
Abstract:
Error correcting codes (ECCs) allow for reliable data transfer over noisy channels. They had a profound impact on both the practical and theoretical communities, and over the last decades were one of the main enablers of the digital revolution. However, modern communication systems often go beyond one-way data transfer and instead operate over many rounds of interactive communication between different parties. Interactive ECCs are a generalization of classical ECCs, and they allow the conversion of any interactive communication protocol to a noise resilient one. In this talk we will focus on a modeling decision that is unique to interactive ECCs, namely, the order of communication, and see its impact on the existence of good interactive ECCs.