Access Restriction

Author Brakerski, Zvika ♦ Kalai, Yael Tauman ♦ Naor, Moni
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2014
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Interactive coding
Abstract Consider two parties who wish to communicate in order to execute some interactive protocol π. However, the communication channel between them is noisy: An adversary sees everything that is transmitted over the channel and can change a constant fraction of the bits arbitrarily, thus interrupting the execution of π (which was designed for an error-free channel). If π only contains a single long message, then a good error correcting code would overcome the noise with only a constant overhead in communication. However, this solution is not applicable to interactive protocols consisting of many short messages. Schulman [1992, 1993] introduced the notion of interactive coding: A simulator that, given any protocol π, is able to simulate it (i.e., produce its intended transcript) even in the presence of constant rate adversarial channel errors, and with only constant (multiplicative) communication overhead. However, the running time of Schulman's simulator, and of all simulators that followed, has been exponential (or subexponential) in the communication complexity of π (which we denote by $\textit{N}).$ In this work, we present three efficient simulators, all of which are randomized and have a certain failure probability (over the choice of coins). The first runs in time $poly(\textit{N}),$ has failure probability roughly $2^{-N},$ and is resilient to 1/32-fraction of adversarial error. The second runs in time $\textit{O}(\textit{N}$ log $\textit{N}),$ has failure probability roughly $2^{-N},$ and is resilient to some constant fraction of adversarial error. The third runs in time $\textit{O}(\textit{N}),$ has failure probability $1/poly(\textit{N}),$ and is resilient to some constant fraction of adversarial error. (Computational complexity is measured in the RAM model.) The first two simulators can be made $\textit{deterministic}$ if they are a priori given a random string (which may be known to the adversary ahead of time). In particular, the simulators can be made to be nonuniform and deterministic (with equivalent performance).
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2014-12-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 61
Issue Number 6
Page Count 30
Starting Page 1
Ending Page 30

Open content in new tab

   Open content in new tab
Source: ACM Digital Library