TY - GEN

T1 - Interactive Coding with Small Memory

AU - Efremenko, Klim

AU - Haeupler, Bernhard

AU - Kalai, Yael Tauman

AU - Kol, Gillat

AU - Resch, Nicolas

AU - Saxena, Raghuvansh R.

N1 - Funding Information:
∗Ben Gurion University. Supported by the Israel Science Foundation (ISF) through grant No. 1456/18 and European Research Council Grant number: 949707. †ETHZ & Carnegie Mellon University. Supported in part by NSF grants CCF-1814603, CCF-1910588, NSF CAREER award CCF-1750808, a Sloan Research Fellowship, and the European Union’s Horizon 2020 ERC grant 949272. ‡Microsoft Research & MIT. §Princeton University. Supported by a National Science Foundation CAREER award CCF-1750443 and by a BSF grant No.
Publisher Copyright:
Copyright © 2023 by SIAM.

PY - 2023

Y1 - 2023

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85165882525&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85165882525&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:85165882525

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 3587

EP - 3613

BT - 34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023

PB - Association for Computing Machinery

T2 - 34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023

Y2 - 22 January 2023 through 25 January 2023

ER -