Document Open Access Logo

Coding for Interactive Communication Correcting Insertions and Deletions

Authors Mark Braverman, Ran Gelles, Jieming Mao, Rafail Ostrovsky

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2016.61.pdf
  • Filesize: 0.58 MB
  • 14 pages

Document Identifiers

Author Details

Mark Braverman
Ran Gelles
Jieming Mao
Rafail Ostrovsky

Cite As Get BibTex

Mark Braverman, Ran Gelles, Jieming Mao, and Rafail Ostrovsky. Coding for Interactive Communication Correcting Insertions and Deletions. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 61:1-61:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ICALP.2016.61

Abstract

We consider the question of interactive communication, in which two remote parties perform a computation while their communication channel is (adversarially) noisy. We extend here the discussion into a more general and stronger class of noise, namely, we allow the channel to perform insertions and deletions of symbols. These types of errors may bring the parties "out of sync", so that there is no consensus regarding the current round of the protocol.

In this more general noise model, we obtain the first interactive coding scheme that has a constant rate and tolerates noise rates of up to 1/18 - epsilon. To this end we develop a novel primitive we name edit distance tree code. The edit distance tree code is designed to replace the Hamming distance constraints in Schulman's tree codes (STOC 93), with a stronger edit distance requirement. However, the straightforward generalization of tree codes to edit distance does not seem to yield a primitive that suffices for communication in the presence of synchronization problems. Giving the "right" definition of edit distance tree codes is a main conceptual contribution of this work.

Subject Classification

Keywords
  • Interactive communication
  • coding
  • edit distance

Metrics

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

References

  1. Shweta Agrawal, Ran Gelles, and Amit Sahai. Adaptive protocols for interactive communication. arXiv preprint arXiv:1312.4182, 2013. Google Scholar
  2. Zvika Brakerski and Yael Tauman Kalai. Efficient interactive coding against adversarial noise. In Foundations of Computer Science, IEEE Annual Symposium on, pages 160-166. IEEE Computer Society, 2012. URL: http://dx.doi.org/10.1109/FOCS.2012.22.
  3. Zvika Brakerski, Yael Tauman Kalai, and Moni Naor. Fast interactive coding against adversarial noise. J. ACM, 61(6):35:1-35:30, December 2014. URL: http://dx.doi.org/10.1145/2661628.
  4. Zvika Brakerski and Moni Naor. Fast algorithms for interactive coding. In SODA'13: Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 443-456, 2013. Google Scholar
  5. Gilles Brassard, Ashwin Nayak, Alain Tapp, Dave Touchette, and Falk Unger. Noisy interactive quantum communication. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages 296-305, 2014. URL: http://dx.doi.org/10.1109/FOCS.2014.39.
  6. Mark Braverman and Klim Efremenko. List and unique coding for interactive communication in the presence of adversarial noise. In Foundations of Computer Science (FOCS), IEEE 55th Annual Symposium on, pages 236-245, 2014. Google Scholar
  7. Mark Braverman and Anup Rao. Towards coding for maximum errors in interactive communication. In Proceedings of the Forty-third Annual ACM Symposium on Theory of Computing, STOC'11, pages 159-166, New York, NY, USA, 2011. ACM. URL: http://dx.doi.org/10.1145/1993636.1993659.
  8. Mark Braverman and Anup Rao. Toward coding for maximum errors in interactive communication. Information Theory, IEEE Transactions on, 60(11):7248-7255, Nov 2014. URL: http://dx.doi.org/10.1109/TIT.2014.2353994.
  9. 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'15, pages 11-20, New York, NY, USA, 2015. ACM. URL: http://dx.doi.org/10.1145/2688073.2688077.
  10. Matthew Franklin, Ran Gelles, Rafail Ostrovsky, and Leonard J. Schulman. Optimal coding for streaming authentication and interactive communication. In Ran Canetti and Juan A. Garay, editors, CRYPTO'13, volume 8043 of LNCS, pages 258-276. Springer Berlin, 2013. URL: http://dx.doi.org/10.1007/978-3-642-40084-1_15.
  11. Matthew Franklin, Ran Gelles, Rafail Ostrovsky, and Leonard J. Schulman. Optimal coding for streaming authentication and interactive communication. Information Theory, IEEE Transactions on, 61(1):133-145, Jan 2015. URL: http://dx.doi.org/10.1109/TIT.2014.2367094.
  12. Ran Gelles and Bernhard Haeupler. Capacity of interactive communication over erasure channels and channels with feedback. In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'15, pages 1296-1311, 2015. Google Scholar
  13. Ran Gelles, Ankur Moitra, and Amit Sahai. Efficient and explicit coding for interactive communication. In Foundations of Computer Science, 2011 IEEE 52nd Annual Symposium on, pages 768-777. IEEE Computer Society, 2011. URL: http://dx.doi.org/10.1109/FOCS.2011.51.
  14. Ran Gelles, Ankur Moitra, and Amit Sahai. Efficient coding for interactive communication. Information Theory, IEEE Transactions on, 60(3):1899-1913, March 2014. URL: http://dx.doi.org/10.1109/TIT.2013.2294186.
  15. Mohsen Ghaffari and Bernhard Haeupler. Optimal Error Rates for Interactive Coding II: Efficiency and List Decoding. In Foundations of Computer Science (FOCS), IEEE 55th Annual Symposium on, pages 394-403, 2014. Google Scholar
  16. Mohsen Ghaffari, Bernhard Haeupler, and Madhu Sudan. Optimal error rates for interactive coding I: Adaptivity and other settings. In STOC'14: Proceedings of the 46th Annual ACM Symposium on Theory of Computing, pages 794-803, 2014. URL: http://dx.doi.org/10.1145/2591796.2591872.
  17. Bernhard Haeupler. Interactive channel capacity revisited. In Foundations of Computer Science (FOCS), IEEE 55th Annual Symposium on, pages 226-235, 2014. Google Scholar
  18. Jørn Justesen. Class of constructive asymptotically good algebraic codes. Information Theory, IEEE Transactions on, 18(5):652-656, Sep 1972. URL: http://dx.doi.org/10.1109/TIT.1972.1054893.
  19. Gillat Kol and Ran Raz. Interactive channel capacity. In STOC'13: Proceedings of the 45th annual ACM Symposium on theory of computing, pages 715-724, 2013. URL: http://dx.doi.org/10.1145/2488608.2488699.
  20. Vladimir I. Levenshtein. Binary codes capable of correcting deletions, insertions and reversals. In Soviet physics doklady, volume 10, page 707, 1966. Google Scholar
  21. Rafail Ostrovsky, Yuval Rabani, and Leonard J. Schulman. Error-correcting codes for automatic control. Information Theory, IEEE Transactions on, 55(7):2931-2941, July 2009. URL: http://dx.doi.org/10.1109/TIT.2009.2021303.
  22. Leonard J. Schulman. Communication on noisy channels: a coding theorem for computation. Foundations of Computer Science, Annual IEEE Symposium on, pages 724-733, 1992. URL: http://dx.doi.org/10.1109/SFCS.1992.267778.
  23. Leonard J. Schulman. Deterministic coding for interactive communication. In STOC'93: Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, pages 747-756, New York, NY, USA, 1993. ACM. URL: http://dx.doi.org/10.1145/167088.167279.
  24. Leonard J. Schulman. Coding for interactive communication. IEEE Trans. Inf. Theory, 42(6):1745-1756, 1996. Google Scholar
  25. Leonard J. Schulman and David Zuckerman. Asymptotically good codes correcting insertions, deletions, and transpositions. Information Theory, IEEE Transactions on, 45(7):2552-2557, Nov 1999. URL: http://dx.doi.org/10.1109/18.796406.
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