Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR22-146 | 9th November 2022 23:47

Interactive Coding with Small Memory


Authors: Klim Efremenko, Bernhard Haeupler, Gillat Kol, Nicolas Resch, Raghuvansh Saxena, Yael Tauman Kalai
Publication: 10th November 2022 01:07
Downloads: 250


In this work, we design an interactive coding scheme that converts any two party interactive protocol $\Pi$ into another interactive protocol $\Pi'$, such that even if errors are introduced during the execution of $\Pi'$, the parties are able to determine what the outcome of running $\Pi$ 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 $\Pi$ has communication complexity $T$, computational complexity $t$, and space complexity $s$, the resulting protocol $\Pi'$ is resilient to a constant $\epsilon > 0$ fraction of adversarial errors, and has communication complexity approaching $T$ as $\epsilon$ approaches $0$, $\mathrm{poly}(t)$, and space complexity $\mathcal{O}(s \log T)$.

Prior to this work, all known interactive coding schemes required the parties to use at least $\Omega(T)$ space, as the parties were required to remember the transcript of the conversation thus far, or considered weaker error models.

ISSN 1433-8092 | Imprint