Interactive Coding with Small Memory

In this work, we design an interactive coding scheme that converts any two party interactive protocol Π into another interactive protocol Π', such that even if errors are introduced during the execution of Π', the parties are able to determine what the outcome of running Π would be in an error-free setting. Importantly, our scheme preserves the space complexity of the protocol, in addition to the communication and computational complexities. Specifically, if the protocol Π has communication complexity T, computational complexity t, and space complexity s, the resulting protocol Π' is resilient to a constant ε > 0 fraction of adversarial errors, and has communication complexity approaching T as ε approaches 0, computational complexity poly( t ), and space complexity 𝒪( s log T ). Prior to this work, all known interactive coding schemes required the parties to use at least Ω( T ) space, as the parties were required to remember the transcript of the conversation thus far, or considered weaker error models.

Authors

• Klim Efremenko
• Bernhard Haeupler
• Yael Tauman Kalai
• Gillat Kol
• Nicolas Resch
• Raghuvansh R. Saxena

Keywords

No keywords are indexed for this paper.