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.