Document Open Access Logo

Palette-Alternating Tree Codes

Authors Gil Cohen , Shahar Samocha

PDF
Thumbnail PDF

File

LIPIcs.CCC.2020.11.pdf
  • Filesize: 0.52 MB
  • 29 pages

Document Identifiers

Author Details

Gil Cohen
  • Department of Computer Science, Tel Aviv University, Israel
Shahar Samocha
  • Department of Computer Science, Tel Aviv University, Israel

Funding

The research leading to these results has received funding from the Israel Science Foundation (grant number 1569/18) and from the Azrieli Faculty Fellowship.

Acknowledgements

We wish to thank Leonard J. Schulman for many insightful discussions over the years regarding tree codes and interactive coding schemes.

Cite AsGet BibTex

Gil Cohen and Shahar Samocha. Palette-Alternating Tree Codes. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 11:1-11:29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.CCC.2020.11

Abstract

A tree code is an edge-coloring of the complete infinite binary tree such that every two nodes of equal depth have a fraction - bounded away from 0 - of mismatched colors between the corresponding paths to their least common ancestor. Tree codes were introduced in a seminal work by Schulman [Schulman, 1993] and serve as a key ingredient in almost all deterministic interactive coding schemes. The number of colors effects the coding scheme’s rate. It is shown that 4 is precisely the least number of colors for which tree codes exist. Thus, tree-code-based coding schemes cannot achieve rate larger than 1/2. To overcome this barrier, a relaxed notion called palette-alternating tree codes is introduced, in which the number of colors can depend on the layer. We prove the existence of such constructs in which most layers use 2 colors - the bare minimum. The distance-rate tradeoff we obtain matches the Gilbert-Varshamov bound. Based on palette-alternating tree codes, we devise a deterministic interactive coding scheme against adversarial errors that approaches capacity. To analyze our protocol, we prove a structural result on the location of failed communication-rounds induced by the error pattern enforced by the adversary. Our coding scheme is efficient given an explicit palette-alternating tree code and serves as an alternative to the scheme obtained by [R. Gelles et al., 2016].

Subject Classification

ACM Subject Classification
  • Theory of computation → Error-correcting codes
Keywords
  • Tree Codes
  • Coding Theory
  • Interactive Coding Scheme

Metrics

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

References

  1. S. Agrawal, R. Gelles, and A. Sahai. Adaptive protocols for interactive communication. In Proc. IEEE International Symposium on Information Theory (ISIT), pages 595-599, 2016. Google Scholar
  2. N. Alon, M. Braverman, K. Efremenko, R. Gelles, and B. Haeupler. Reliable communication over highly connected noisy networks. In Proc. ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC), pages 165-173, 2016. Google Scholar
  3. Z. Brakerski and Y. T. Kalai. Efficient interactive coding against adversarial noise. In Proc. IEEE Symposium on Foundations of Computer Science (FOCS), pages 160-166, 2012. Google Scholar
  4. Z. Brakerski, Y. T. Kalai, and M. Naor. Fast interactive coding against adversarial noise. Journal of the ACM (JACM), 61(6):35:1-30, 2014. Google Scholar
  5. Z. Brakerski and M. Naor. Fast algorithms for interactive coding. In Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 443-456, 2013. Google Scholar
  6. M. Braverman. Towards deterministic tree code constructions. In Proc. ACM-SIGACT Innovations in Theoretical Computer Science Conference (ITCS), pages 161-167, 2012. Google Scholar
  7. M. Braverman and K. Efremenko. List and unique coding for interactive communication in the presence of adversarial noise. In Proc. IEEE Symposium on Foundations of Computer Science (FOCS), pages 236-245, 2014. Google Scholar
  8. M. Braverman, R. Gelles, J. Mao, and R. Ostrovsky. Coding for interactive communication correcting insertions and deletions. IEEE Transactions on Information Theory, 63(10):6256-6270, 2017. Google Scholar
  9. M. Braverman and A. Rao. Towards coding for maximum errors in interactive communication. In Proc. ACM Symposium on Theory of Computing (STOC), pages 159-166, 2011. Google Scholar
  10. M. Braverman and A. Rao. Toward coding for maximum errors in interactive communication. IEEE Transactions on Information Theory, 60(11):7248-7255, 2014. Google Scholar
  11. G. Cohen, B. Haeupler, and L. J. Schulman. Explicit binary tree codes with polylogarithmic size alphabet. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 535-544. ACM, 2018. Google Scholar
  12. R. 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.
  13. R. Gelles, B. Haeupler, G. Kol, N. Ron-Zewi, and A. Wigderson. Towards optimal deterministic coding for interactive communication, 2016. Google Scholar
  14. R. Gelles, A. Moitra, and A. Sahai. Efficient coding for interactive communication. IEEE Transactions on Information Theory, 60(3):1899-1913, 2014. Google Scholar
  15. Ran Gelles, Ankur Moitra, and Amit Sahai. Efficient and explicit coding for interactive communication. In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, pages 768-777. IEEE, 2011. Google Scholar
  16. M. Ghaffari and B. Haeupler. Optimal Error Rates for Interactive Coding II: Efficiency and List Decoding. In Proc. IEEE Symposium on Foundations of Computer Science (FOCS), pages 394-403, 2014. Google Scholar
  17. M. Ghaffari, B. Haeupler, and M. Sudan. Optimal error rates for interactive coding I: Adaptivity and other settings. In Proc. ACM Symposium on Theory of Computing (STOC), pages 794-803, 2014. Google Scholar
  18. B. Haeupler. Interactive Channel Capacity Revisited. In Proc. IEEE Symposium on Foundations of Computer Science (FOCS), pages 226-235, 2014. Google Scholar
  19. A. Jain, Y. T. Kalai, and A. B. Lewko. Interactive coding for multiparty protocols. In Proc. ACM Innovations in Theoretical Computer Science Conference (ITCS), pages 1-10, 2015. Google Scholar
  20. G. Kol and R. Raz. Interactive channel capacity. In STOC, volume 13, pages 715-724, 2013. Google Scholar
  21. E. Kushilevitz and N. Nisan. Communication complexity. In Advances in Computers, volume 44, pages 331-360. Elsevier, 1997. Google Scholar
  22. A. Lewko and E. Vitercik. Balancing communication for multi-party interactive coding. CoRR, abs/1503.06381, 2015. URL: http://arxiv.org/abs/1503.06381.
  23. C. Moore and L. J. Schulman. Tree codes and a conjecture on exponential sums. In Proc. ACM-SIGACT Innovations in Theoretical Computer Science Conference (ITCS), pages 145-154, 2014. Google Scholar
  24. Anand Kumar Narayanan and Matthew Weidner. On decoding Cohen-Haeupler-Schulman tree codes. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1337-1356. SIAM, 2020. Google Scholar
  25. P. Pudlák. Linear tree codes and the problem of explicit constructions. Linear Algebra and its Applications, 490:124-144, 2016. Google Scholar
  26. S. Rajagopalan and L. J. Schulman. A coding theorem for distributed computation. In Proc. ACM Symposium on Theory of Computing (STOC), pages 790-799, 1994. Google Scholar
  27. A. Rao and A. Yehudayoff. Communication complexity (early draft), 2018. Google Scholar
  28. L. J. Schulman. Communication on noisy channels: a coding theorem for computation. Proc. IEEE Symposium on Foundations of Computer Science (FOCS), pages 724-733, 1992. Google Scholar
  29. L. J. Schulman. Deterministic coding for interactive communication. In Proc. ACM Symposium on Theory of Computing (STOC), pages 747-756, 1993. Google Scholar
  30. L. J. Schulman. Postscript of 21 September 2003 to Coding for Interactive Communication. http://users.cms.caltech.edu/∼schulman/Papers/intercodingpostscript.txt, 1994. Google Scholar
  31. L. J. Schulman. Coding for interactive communication. IEEE Transactions on Information Theory, 42(6):1745-1756, 1996. Google Scholar
  32. A. A. Sherstov and P. Wu. Optimal interactive coding for insertions, deletions, and substitutions. In Proc. IEEE Symposium on Foundations of Computer Science (FOCS), 2017. 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 Imprint Privacy Contact