SODA Conference 2023 Conference Paper
Interactive Coding with Small Memory
- Klim Efremenko
- Bernhard Haeupler
- Yael Tauman Kalai
- Gillat Kol
- Nicolas Resch
- Raghuvansh R. Saxena
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.