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 O(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.