Document Open Access Logo

Communication with Partial Noiseless Feedback

Authors Bernhard Haeupler, Pritish Kamath, Ameya Velingker

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2015.881.pdf
  • Filesize: 0.5 MB
  • 17 pages

Document Identifiers

Author Details

Bernhard Haeupler
Pritish Kamath
Ameya Velingker

Cite As Get BibTex

Bernhard Haeupler, Pritish Kamath, and Ameya Velingker. Communication with Partial Noiseless Feedback. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 881-897, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2015.881

Abstract

We introduce the notion of one-way communication schemes with partial noiseless feedback. In this setting, Alice wishes to communicate a message to Bob by using a communication scheme that involves sending a sequence of bits over a channel while receiving feedback bits from Bob for delta fraction of the transmissions. An adversary is allowed to corrupt up to a constant fraction of Alice's transmissions, while the feedback is always uncorrupted. Motivated by questions related to coding for interactive communication, we seek to determine the maximum error rate, as a function of 0 <= delta <= 1, such that Alice can send a message to Bob via some protocol with delta fraction of noiseless feedback. The case delta = 1 corresponds to full feedback, in which the result of Berlekamp ['64] implies that the maximum tolerable error rate is 1/3, while the case delta = 0 corresponds to no feedback, in which the maximum tolerable error rate is 1/4, achievable by use of a binary error-correcting code.

In this work, we show that for any delta in (0,1] and gamma in [0, 1/3), there exists a randomized communication scheme with noiseless delta-feedback, such that the probability of miscommunication is low, as long as no more than a gamma fraction of the rounds are corrupted. Moreover, we show that for any delta in (0, 1] and gamma < f(delta), there exists a deterministic communication scheme with noiseless delta-feedback that always decodes correctly as long as no more than a gamma fraction of rounds are corrupted. Here f is a monotonically increasing, piecewise linear, continuous function with f(0) = 1/4 and f(1) = 1/3. Also, the rate of communication in both cases is constant (dependent on delta and gamma but independent of the input length).

Subject Classification

Keywords
  • Communication with feedback
  • Interactive communication
  • Coding theory Digital

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Elwyn R. Berlekamp. Block Coding with Noiseless Feedback. PhD thesis, Massachusetts Institute of Technology, Cambridge, MA, USA, 1964. Google Scholar
  2. Zvika Brakerski and Yael Tauman Kalai. Efficient interactive coding against adversarial noise. In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pages 160-166, 2012. Google Scholar
  3. Zvika Brakerski, Yael Tauman Kalai, and Moni Naor. Fast interactive coding against adversarial noise. J. ACM, 61(6):35, 2014. Google Scholar
  4. Zvika Brakerski and Moni Naor. Fast algorithms for interactive coding. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013, pages 443-456, 2013. Google Scholar
  5. Mark Braverman and Klim Efremenko. List and unique coding for interactive communication in the presence of adversarial noise. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages 236-245, 2014. Google Scholar
  6. Mark Braverman and Anup Rao. Toward coding for maximum errors in interactive communication. IEEE Transactions on Information Theory, 60(11):7248-7255, 2014. Google Scholar
  7. Klim Efremenko, Ran Gelles, and Bernhard Haeupler. Maximal noise in interactive communication over erasure channels and channels with feedback. In Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, ITCS 2015, Rehovot, Israel, January 11-13, 2015, pages 11-20, 2015. Google Scholar
  8. Ran Gelles and Bernhard Haeupler. Capacity of interactive communication over erasure channels and channels with feedback. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 1296-1311, 2015. Google Scholar
  9. Ran Gelles, Ankur Moitra, and Amit Sahai. Efficient coding for interactive communication. IEEE Transactions on Information Theory, 60(3):1899-1913, 2014. Google Scholar
  10. Mohsen Ghaffari and Bernhard Haeupler. Optimal error rates for interactive coding II: efficiency and list decoding. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages 394-403, 2014. Google Scholar
  11. Mohsen Ghaffari, Bernhard Haeupler, and Madhu Sudan. Optimal error rates for interactive coding I: adaptivity and other settings. In Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 794-803, 2014. Google Scholar
  12. E. N. Gilbert. A comparison of signalling alphabets. Bell System Technical Journal, 31:504-522, 1952. Google Scholar
  13. Bernhard Haeupler. Interactive channel capacity revisited. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages 226-235, 2014. Google Scholar
  14. Gillat Kol and Ran Raz. Interactive channel capacity. In Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA, USA, June 1-4, 2013, pages 715-724, 2013. Google Scholar
  15. Morris Plotkin. Binary codes with specified minimum distance. IRE Transactions on Information Theory, 6(4):445-450, 1960. Google Scholar
  16. Leonard J. Schulman. Communication on noisy channels: A coding theorem for computation. In 33rd Annual Symposium on Foundations of Computer Science, Pittsburgh, Pennsylvania, USA, 24-27 October 1992, pages 724-733, 1992. Google Scholar
  17. Leonard J. Schulman. Deterministic coding for interactive communication. In Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, May 16-18, 1993, San Diego, CA, USA, pages 747-756, 1993. Google Scholar
  18. Leonard J. Schulman. Coding for interactive communication. IEEE Transactions on Information Theory, 42(6):1745-1756, 1996. Google Scholar
  19. Claude E. Shannon. The zero error capacity of a noisy channel. IRE Transactions on Information Theory, 2(3):8-19, 1956. Google Scholar
  20. Joel Spencer and Peter Winkler. Three thresholds for a liar. Combinatorics, Probability & Computing, 1:81-93, 1992. Google Scholar
  21. R. R. Varshamov. Estimate of the number of signals in error correcting codes. Dokl. Acad. Nauk SSSR, 117:739-741, 1957. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact