research-article

Free access

Towards coding for maximum errors in interactive communication

Authors:

Mark Braverman,

Anup RaoAuthors Info & Claims

STOC '11: Proceedings of the forty-third annual ACM symposium on Theory of computing

Pages 159 - 166

https://doi.org/10.1145/1993636.1993659

Published: 06 June 2011 Publication History

PDF eReader

Abstract

We show that it is possible to encode any communication protocol between two parties so that the protocol succeeds even if a (1/4-ε) fraction of all symbols transmitted by the parties are corrupted adversarially, at a cost of increasing the communication in the protocol by a constant factor (the constant depends on epsilon). This encoding uses a constant sized alphabet. This improves on an earlier result of Schulman, who showed how to recover when the fraction of errors is bounded by 1/240. We also show how to simulate an arbitrary protocol with a protocol using the binary alphabet, a constant factor increase in communication and tolerating a (1/8-ε) fraction of errors.

Supplementary Material

JPG File (stoc_3b_1.jpg)

Download
17.30 KB

MP4 File (stoc_3b_1.mp4)

Download
131.51 MB

References

[1]

Eyal Kushilevitz and Noam Nisan. Communication complexity. Cambridge University Press, Cambridge, 1997.

Digital Library

Google Scholar

[2]

Marcin Peczarski. An improvement of the tree code construction. Information Processing Letters, 99(3):92 -- 95, 2006.

Digital Library

Google Scholar

[3]

W. W. Peterson, E. J. Weldon, and Jr. Error-Correcting Codes. MIT Press, Cambridge, Massachusetts, 1972.

Google Scholar

[4]

Leonard J. Schulman. Coding for interactive communication. IEEE Transactions on Information Theory, 42(6):1745--1756, 1996.

Digital Library

Google Scholar

[5]

L. Schulman. A postcript to "Coding for Interactive Communication", 2003. http://www.cs.caltech.edu/ schulman/Papers/intercodingpostscript.txt.

Google Scholar

[6]

Claude E. Shannon. A mathematical theory of communication. Bell System Technical Journal, 27, 1948. Monograph B-1598.

Google Scholar

[7]

M. Sudan. List decoding: Algorithms and applications. Theoretical Computer Science: Exploring New Frontiers of Theoretical Informatics, pages 25--41, 2000.

Digital Library

Google Scholar

Cited By

View all

Efremenko KKol GParamonov DSaxena RSaha BServedio R(2023)The Rate of Interactive Codes Is Bounded Away from 1Proceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585249(1424-1437)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585249
Gupta MZhang RSaha BServedio R(2023)Efficient Interactive Coding Achieving Optimal Error Resilience over the Binary ChannelProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585162(1449-1462)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585162
Gupta MZhang RLeonardi SGupta A(2022)The optimal error resilience of interactive communication over binary channelsProceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3519935.3519985(948-961)Online publication date: 9-Jun-2022
https://dl.acm.org/doi/10.1145/3519935.3519985
Show More Cited By

Index Terms

Towards coding for maximum errors in interactive communication

Recommendations

List and Unique Coding for Interactive Communication in the Presence of Adversarial Noise

In this paper, we extend the notion of list decoding to the setting of interactive communication and study its limits. In particular, we show that any protocol can be encoded, with a constant rate, into a list-decodable protocol which is resilient to a ...
Interactive Coding for Multiparty Protocols
ITCS '15: Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science

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 ...
Efficient and Explicit Coding for Interactive Communication
FOCS '11: Proceedings of the 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science

We revisit the problem of reliable interactive communication over a noisy channel, and obtain the first fully explicit (randomized) efficient constant-rate emulation procedure for reliable interactive communication. Our protocol works for any discrete ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

STOC '11: Proceedings of the forty-third annual ACM symposium on Theory of computing

June 2011

840 pages

ISBN:9781450306911

DOI:10.1145/1993636

General Chair:
Lance Fortnow
Northwestern University
,
Program Chair:
Salil Vadhan
Harvard University

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 June 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

STOC'11

Sponsor:

SIGACT

STOC'11: Symposium on Theory of Computing

June 6 - 8, 2011

California, San Jose, USA

Acceptance Rates

STOC '11 Paper Acceptance Rate 84 of 304 submissions, 28%;

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

57
Total Citations
View Citations
559
Total Downloads

Downloads (Last 12 months)112
Downloads (Last 6 weeks)6

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Efremenko KKol GParamonov DSaxena RSaha BServedio R(2023)The Rate of Interactive Codes Is Bounded Away from 1Proceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585249(1424-1437)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585249
Gupta MZhang RSaha BServedio R(2023)Efficient Interactive Coding Achieving Optimal Error Resilience over the Binary ChannelProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585162(1449-1462)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585162
Gupta MZhang RLeonardi SGupta A(2022)The optimal error resilience of interactive communication over binary channelsProceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3519935.3519985(948-961)Online publication date: 9-Jun-2022
https://dl.acm.org/doi/10.1145/3519935.3519985
Gupta MKalai YZhang RLeonardi SGupta A(2022)Interactive error correcting codes over binary erasure channels resilient to > ½ adversarial corruptionProceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3519935.3519980(609-622)Online publication date: 9-Jun-2022
https://dl.acm.org/doi/10.1145/3519935.3519980
Efremenko KKol GSaxena RZhang Z(2022)Binary Codes with Resilience Beyond 1/4 via Interaction2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS54457.2022.00008(1-12)Online publication date: Oct-2022
https://doi.org/10.1109/FOCS54457.2022.00008
Efremenko KKol GSaxena RKhuller SVassilevska Williams V(2021)Optimal error resilience of adaptive message exchangeProceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing10.1145/3406325.3451077(1235-1247)Online publication date: 15-Jun-2021
https://dl.acm.org/doi/10.1145/3406325.3451077
Cohen GSamocha SAceto L(2020)Palette-alternating tree codesProceedings of the 35th Computational Complexity Conference10.4230/LIPIcs.CCC.2020.11(1-29)Online publication date: 28-Jul-2020
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2020.11
Efremenko KKol GSaxena REmek YCachin C(2020)Noisy BeepsProceedings of the 39th Symposium on Principles of Distributed Computing10.1145/3382734.3404501(418-427)Online publication date: 31-Jul-2020
https://dl.acm.org/doi/10.1145/3382734.3404501
Efremenko KKol GSaxena RMakarychev KMakarychev YTulsiani MKamath GChuzhoy J(2020)Interactive error resilience beyond 2/7Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing10.1145/3357713.3384320(565-578)Online publication date: 22-Jun-2020
https://dl.acm.org/doi/10.1145/3357713.3384320
Efremenko KKol GSaxena R(2020)Binary Interactive Error Resilience Beyond2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS46700.2020.00051(470-481)Online publication date: Nov-2020
https://doi.org/10.1109/FOCS46700.2020.00051
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

List and Unique Coding for Interactive Communication in the Presence of Adversarial Noise

Interactive Coding for Multiparty Protocols

Efficient and Explicit Coding for Interactive Communication