License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2020.7
URN: urn:nbn:de:0030-drops-116927
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/11692/
Efremenko, Klim ;
Haramaty, Elad ;
Kalai, Yael Tauman
Interactive Coding with Constant Round and Communication Blowup
Abstract
The problem of constructing error-resilient interactive protocols was introduced in the seminal works of Schulman (FOCS 1992, STOC 1993). These works show how to convert any two-party interactive protocol into one that is resilient to constant-fraction of error, while blowing up the communication by only a constant factor. Since these seminal works, there have been many followup works which improve the error rate, the communication rate, and the computational efficiency.
All these works only consider only an increase in communication complexity and did not consider an increase in round complexity. This work is the first one that considers the blowup of round complexity in noisy setting. While techniques from other papers can be easily adapted encode protocols with arbitrarily round complexity this coding schemes will lead to large(and usually unbounded) increase in round complexity of the protocol.
In this work, we show how to convert any protocol Π, with no a priori known communication bound, into an error-resilient protocol Π', with comparable computational efficiency, that is resilient to constant fraction of adversarial error, while blowing up both the communication complexity and the round complexity by at most a constant factor. We consider the model where in each round each party may send a message of arbitrary length, where the length of the messages and the length of the protocol may be adaptive, and may depend on the private inputs of the parties and on previous communication. We consider the adversarial error model, where ε-fraction of the communication may be corrupted, where we allow each corruption to be an insertion or deletion (in addition to toggle).
In addition, we try to minimize the blowup parameters: In particular, we construct such Π' with (1+Õ(ε^(1/4))) blowup in communication and O(1) blowup in rounds. We also show how to reduce the blowup in rounds at the expense of increasing the blowup in communication, and construct Π' where both the blowup in rounds and communication, approaches one (i.e., no blowup) as ε approaches zero. We give "evidence" that our parameters are "close to" optimal.
BibTeX - Entry
@InProceedings{efremenko_et_al:LIPIcs:2020:11692,
author = {Klim Efremenko and Elad Haramaty and Yael Tauman Kalai},
title = {{Interactive Coding with Constant Round and Communication Blowup}},
booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
pages = {7:1--7:34},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-134-4},
ISSN = {1868-8969},
year = {2020},
volume = {151},
editor = {Thomas Vidick},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/11692},
URN = {urn:nbn:de:0030-drops-116927},
doi = {10.4230/LIPIcs.ITCS.2020.7},
annote = {Keywords: Interactive Coding, Round Complexity, Error Correcting Codes}
}
|
Keywords: |
|
Interactive Coding, Round Complexity, Error Correcting Codes |
|
Collection: |
|
11th Innovations in Theoretical Computer Science Conference (ITCS 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
06.01.2020 |
