Interactive Coding with Small Memory

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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

Original languageEnglish (US)
Title of host publication34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023
PublisherAssociation for Computing Machinery
Number of pages27
ISBN (Electronic)9781611977554
StatePublished - 2023
Event34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023 - Florence, Italy
Duration: Jan 22 2023Jan 25 2023

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms


Conference34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023

All Science Journal Classification (ASJC) codes

  • Software
  • General Mathematics


Dive into the research topics of 'Interactive Coding with Small Memory'. Together they form a unique fingerprint.

Cite this