Name
Abstract | ||
|---|---|---|
We consider the task of communicating a data stream-a long, possibly infinite message not known in advance to the sender-over a channel with adversarial noise. For any given noise rate c <; 1, we show an efficient, constant-rate scheme that correctly decodes a (1 - c) fraction of the stream sent so far with high probability, or aborts if the noise rate exceeds c. In addition, we prove that no constant-rate scheme can recover more than a (1 - c) fraction of the stream sent so far with non-negligible probability, which makes our scheme optimal in that aspect. The parties are assumed to preshare a random string unknown to the channel. Our techniques can also be applied to the task of interactive communication (two-way communication) over a noisy channel. In a recent paper (Braverman and Rao, STOC11), the possibility of two-party interactive communication as long as the noise level is <; 1/4 was shown. By allowing the parties to preshare some private random string, we extend this result and construct a (nonefficient) constant-rate interactive protocol that succeeds with overwhelming probability against noise rates up to 1/2. We complete this result by proving that no constant-rate protocol can withstand noise rates > 1/2. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1109/TIT.2014.2367094 | Information Theory, IEEE Transactions |
Keywords | DocType | Volume |
channel coding,cryptographic protocols,data communication,decoding,electronic messaging,probability,random codes,channel adversarial noise,constant-rate interactive protocol,data communication,decoding,interactive communication,optimal coding,overwhelming probability,private random string,streaming authentication,two-way communication,Data streams,adversarial noise,blueberry codes,interactive communication,reliable communication,tree codes | Conference | 61 |
Issue | ISSN | Citations |
1 | 0018-9448 | 21 |
PageRank | References | Authors |
0.97 | 21 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Matthew K. Franklin | 1 | 21 | 0.97 |
| Gelles, R. | 2 | 21 | 0.97 |
| Rafail Ostrovsky | 3 | 8743 | 588.15 |
| Leonard J. Schulman | 4 | 1328 | 136.88 |