Foundations and Trends® in Theoretical Computer Science > Vol 13 > Issue 1–2

Coding for Interactive Communication: A Survey

Ran Gelles, Bar-Ilan University, Israel, Israel, ran.gelles@biu.ac.il
 
Suggested Citation
Ran Gelles (2017), "Coding for Interactive Communication: A Survey", Foundations and Trends® in Theoretical Computer Science: Vol. 13: No. 1–2, pp 1-157. http://dx.doi.org/10.1561/0400000079

Published: 17 Oct 2017
© 2017 R. Gelles
 
Subjects
Computational aspects of communication,  Computational Models and Complexity,  Distributed computing,  Coding theory and practice
 
Keywords
Interactive communicationInteractive codingNoise-resilient systems and computation
 

Free Preview:

Article Help

Share

Download article
In this article:
1. Introduction
2. Noise Resilience
3. The Hunt for Efficient Constructions
4. Adaptive Coding Schemes
5. Communication-Efficient Coding Schemes
6. Coding Schemes over Different Noisy Channels
7. Multiparty Interactive Communication
8. Applications and Related Topics
Acknowledgements
A. Addendum
B. Summary of Known Schemes
References

Abstract

Coding for interactive communication augments coding theory to the interactive setting: instead of communicating a message from a sender to a receiver, here the parties are involved in an interactive conversation. Coding schemes allow the parties to complete their conversation despite noise added by the channel. Similar to the unidirectional case, good coding schemes can withstand a large amount of noise and succeed with high probability, while adding only a small amount of redundant information. We aim at giving a comprehensive view on the foundations of coding for interactive communication. In particular, we review basic features of coding schemes in the interactive setting, and survey the main techniques used in designing such schemes. Furthermore, we survey recent developments in interactive coding schemes, and their applications to other related fields.

DOI:10.1561/0400000079
ISBN: 978-1-68083-346-1
180 pp. $99.00
Buy book
 
ISBN: 978-1-68083-347-8
180 pp. $260.00
Buy E-book
Table of contents:
1. Introduction
2. Noise Resilience
3. The Hunt for Efficient Constructions
4. Adaptive Coding Schemes
5. Communication-Efficient Coding Schemes
6. Coding Schemes over Different Noisy Channels
7. Multiparty Interactive Communication
8. Applications and Related Topics
Acknowledgements
A. Addendum
B. Summary of Known Schemes
References

Coding for Interactive Communication: A Survey

Coding for interactive communication augments coding theory to the interactive setting: instead of communicating a message from a sender to a receiver, here the parties are involved in an interactive conversation. Coding schemes allow the parties to complete their conversation despite noise added by the channel. Similar to the unidirectional case, good coding schemes can withstand a large amount of noise and succeed with high probability, while adding only a small amount of redundant information.

Coding for Interactive Communication: A Survey provides the reader with a comprehensive view on the foundations of coding for interactive communication. In particular, it reviews the basic features of coding schemes in the interactive setting, and surveys the main techniques used in designing such schemes. It also surveys recent developments in interactive coding schemes, and their applications to other related fields.

 
TCS-079