Document Open Access Logo

Interactive Coding with Constant Round and Communication Blowup

Authors Klim Efremenko, Elad Haramaty, Yael Tauman Kalai

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2020.7.pdf
  • Filesize: 0.63 MB
  • 34 pages

Document Identifiers

Author Details

Klim Efremenko
  • Ben Gurion University, Beersheva, Israel
Elad Haramaty
  • Harvard University, Cambridge, MA, USA
Yael Tauman Kalai
  • Microsoft Research, Boston, MA, USA

Funding

  • Efremenko, Klim: supported by the Israel Science Foundation (ISF) through grant No. 1456/18.

Cite AsGet BibTex

Klim Efremenko, Elad Haramaty, and Yael Tauman Kalai. Interactive Coding with Constant Round and Communication Blowup. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 7:1-7:34, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ITCS.2020.7

Abstract

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 of error, while blowing up the communication by only a constant factor. Since these seminal works, there have been many followup works which improve the error rate, the communication rate, and the computational efficiency. All these works only consider only an increase in communication complexity and did not consider an increase in round complexity. This work is the first one that considers the blowup of round complexity in noisy setting. While techniques from other papers can be easily adapted encode protocols with arbitrarily round complexity this coding schemes will lead to large(and usually unbounded) increase in round complexity of the protocol. In this work, we show how to convert any protocol Π, with no a priori known communication bound, into an error-resilient protocol Π', with comparable computational efficiency, that is resilient to constant fraction of adversarial error, while blowing up both the communication complexity and the round complexity by at most a constant factor. We consider the model where in each round each party may send a message of arbitrary length, where the length of the messages and the length of the protocol may be adaptive, and may depend on the private inputs of the parties and on previous communication. We consider the adversarial error model, where ε-fraction of the communication may be corrupted, where we allow each corruption to be an insertion or deletion (in addition to toggle). In addition, we try to minimize the blowup parameters: In particular, we construct such Π' with (1+Õ(ε^(1/4))) blowup in communication and O(1) blowup in rounds. We also show how to reduce the blowup in rounds at the expense of increasing the blowup in communication, and construct Π' where both the blowup in rounds and communication, approaches one (i.e., no blowup) as ε approaches zero. We give "evidence" that our parameters are "close to" optimal.

Subject Classification

ACM Subject Classification
  • Theory of computation → Interactive computation
Keywords
  • Interactive Coding
  • Round Complexity
  • Error Correcting Codes

Metrics

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

Related Versions

References

  1. Shweta Agrawal, Ran Gelles, and Amit Sahai. Adaptive protocols for interactive communication. In IEEE International Symposium on Information Theory, ISIT 2016, Barcelona, Spain, July 10-15, 2016, pages 595-599, 2016. URL: https://doi.org/10.1109/ISIT.2016.7541368.
  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. URL: https://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, 2014. URL: https://doi.org/10.1145/2661628.
  4. Zvika Brakerski and Moni Naor. Fast Algorithms for Interactive Coding. In Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '13, pages 443-456, 2013. Google Scholar
  5. Mark Braverman. Towards deterministic tree code constructions. In Innovations in Theoretical Computer Science 2012, Cambridge, MA, USA, January 8-10, 2012, pages 161-167, 2012. URL: https://doi.org/10.1145/2090236.2090250.
  6. Mark Braverman and Klim Efremenko. List and Unique Coding for Interactive Communication in the Presence of Adversarial Noise. In Proceedings of the IEEE Symposium on Foundations of Computer Science, FOCS '14, pages 236-245, 2014. Google Scholar
  7. Mark Braverman, Klim Efremenko, Ran Gelles, and Bernhard Haeupler. Constant-rate coding for multiparty interactive communication is impossible. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 999-1010, 2016. URL: https://doi.org/10.1145/2897518.2897563.
  8. 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, July 11-15, 2016, Rome, Italy, pages 61:1-61:14, 2016. URL: https://doi.org/10.4230/LIPIcs.ICALP.2016.61.
  9. Mark Braverman and Anup Rao. Towards coding for maximum errors in interactive communication. In Proceedings of the 43rd annual ACM symposium on Theory of computing, STOC '11, pages 159-166, New York, NY, USA, 2011. ACM. URL: https://doi.org/10.1145/1993636.1993659.
  10. Klim Efremenko, Ran Gelles, and Bernhard Haeupler. Maximal Noise in Interactive Communication Over Erasure Channels and Channels With Feedback. IEEE Trans. Information Theory, 62(8):4575-4588, 2016. URL: https://doi.org/10.1109/TIT.2016.2582176.
  11. Ran Gelles. Coding for Interactive Communication: A Survey. Foundations and Trends in Theoretical Computer Science, 13(1-2):1-157, 2017. URL: https://doi.org/10.1561/0400000079.
  12. Ran Gelles and Bernhard. Capacity of Interactive Communication over Erasure Channels and Channels with Feedback. SIAM J. Comput., 46(4):1449-1472, 2017. URL: https://doi.org/10.1137/15M1052202.
  13. Ran Gelles, Bernhard Haeupler, Gillat Kol, Noga Ron-Zewi, and Avi Wigderson. Towards Optimal Deterministic Coding for Interactive Communication. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 1922-1936, 2016. URL: https://doi.org/10.1137/1.9781611974331.ch135.
  14. Ran Gelles and Yael Tauman Kalai. Constant-Rate Interactive Coding Is Impossible, Even In Constant-Degree Networks. Electronic Colloquium on Computational Complexity (ECCC), 24:95, 2017. URL: https://eccc.weizmann.ac.il/report/2017/095.
  15. Ran Gelles, Ankur Moitra, and Amit Sahai. Efficient and Explicit Coding for Interactive Communication. In Proceeding of the IEEE Symposium on Foundations of Computer Science, FOCS '11, pages 768-777, 2011. Google Scholar
  16. Mohsen Ghaffari and Bernhard Haeupler. Optimal Error Rates for Interactive Coding II: Efficiency and List Decoding. CoRR, abs/1312.1763, 2013. URL: http://arxiv.org/abs/1312.1763.
  17. 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. URL: https://doi.org/10.1145/2591796.2591872.
  18. Venkatesan Guruswami and Ray Li. Efficiently decodable insertion/deletion codes for high-noise and high-rate regimes. In IEEE International Symposium on Information Theory, ISIT 2016, Barcelona, Spain, July 10-15, 2016, pages 620-624, 2016. URL: https://doi.org/10.1109/ISIT.2016.7541373.
  19. 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. URL: https://doi.org/10.1109/FOCS.2014.32.
  20. Bernhard Haeupler and Amirbehshad Shahrasbi. Synchronization strings: codes for insertions and deletions approaching the Singleton bound. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 33-46, 2017. URL: https://doi.org/10.1145/3055399.3055498.
  21. Bernhard Haeupler, Amirbehshad Shahrasbi, and Ellen Vitercik. Synchronization Strings: Channel Simulations and Interactive Coding for Insertions and Deletions. CoRR, abs/1707.04233, 2017. URL: http://arxiv.org/abs/1707.04233.
  22. Bernhard Haeupler and Ameya Velingker. Bridging the Capacity Gap Between Interactive and One-Way Communication. CoRR, abs/1605.08792, 2016. URL: http://arxiv.org/abs/1605.08792.
  23. Abhishek Jain, Yael Tauman Kalai, and Allison Lewko. Interactive Coding for Multiparty Protocols. In Proceedings of the 6th Conference on Innovations in Theoretical Computer Science, ITCS '15, pages 1-10, 2015. Google Scholar
  24. Gillat Kol and Ran Raz. Interactive channel capacity. In STOC '13: Proceedings of the 45th annual ACM symposium on Symposium on theory of computing, pages 715-724, New York, NY, USA, 2013. ACM. URL: https://doi.org/10.1145/2488608.2488699.
  25. Joseph Naor and Moni Naor. Small-Bias Probability Spaces: Efficient Constructions and Applications. SIAM J. Comput., 22(4):838-856, 1993. URL: https://doi.org/10.1137/0222053.
  26. Sridhar Rajagopalan and Leonard Schulman. A coding theorem for distributed computation. In STOC '94: Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, pages 790-799, New York, NY, USA, 1994. ACM. URL: https://doi.org/10.1145/195058.195462.
  27. 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: https://doi.org/10.1109/SFCS.1992.267778.
  28. 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: https://doi.org/10.1145/167088.167279.
  29. Leonard J. Schulman. Coding for interactive communication. IEEE Transactions on Information Theory, 42(6):1745-1756, 1996. Google Scholar
  30. Claude E. Shannon. A mathematical theory of communication. ACM SIGMOBILE Mobile Computing and Communications Review, 5(1):3-55, 2001. Originally appeared in Bell System Tech. J. 27:379-423, 623-656, 1948. Google Scholar
  31. Alexander A. Sherstov and Pei Wu. Optimal Interactive Coding for Insertions, Deletions, and Substitutions. Electronic Colloquium on Computational Complexity (ECCC), 24:79, 2017. URL: https://eccc.weizmann.ac.il/report/2017/079.
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 Imprint Privacy Contact