Document Open Access Logo

Candidate Tree Codes via Pascal Determinant Cubes

Authors Inbar Ben Yaacov, Gil Cohen, Anand Kumar Narayanan

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2021.54.pdf
  • Filesize: 0.78 MB
  • 22 pages

Document Identifiers

Author Details

Inbar Ben Yaacov
  • The Blavatnik School of Computer Science, Tel-Aviv University, Israel
Gil Cohen
  • The Blavatnik School of Computer Science, Tel-Aviv University, Israel
Anand Kumar Narayanan
  • CISPA Helmholtz Center for Information Security, Saarbrücken, Germany

Funding

  • Ben Yaacov, Inbar: Funded by the Israel Science Foundation (grant number 1569/18).
  • Cohen, Gil: Funded by the Israel Science Foundation (grant number 1569/18) and by the Azrieli Faculty Fellowship.
  • Narayanan, Anand Kumar: Supported by the European Union’s H2020 Programme (grant agreement #ERC-669891).

Acknowledgements

The second author wishes to thank Roni Con, Shir Peleg-Schatzman, Noam Peri, Tal Roth, and Shahar Samocha for interesting discussions on tree codes.

Cite As Get BibTex

Inbar Ben Yaacov, Gil Cohen, and Anand Kumar Narayanan. Candidate Tree Codes via Pascal Determinant Cubes. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 54:1-54:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2021.54

Abstract

Tree codes are combinatorial structures introduced by Schulman [Schulman, 1993] as key ingredients in interactive coding schemes. Asymptotically-good tree codes are long known to exist, yet their explicit construction remains a notoriously hard open problem. Even proposing a plausible construction, without the burden of proof, is difficult and the defining tree code property requires structure that remains elusive. To the best of our knowledge, only one candidate appears in the literature, due to Moore and Schulman [Moore and Schulman, 2014].
We put forth a new candidate for an explicit asymptotically-good tree code. Our construction is an extension of the vanishing rate tree code by Cohen-Haeupler-Schulman [Cohen et al., 2018], and its correctness relies on a conjecture that we introduce on certain Pascal determinants indexed by the points of the Boolean hypercube. Furthermore, using the vanishing distance tree code by Gelles et al. [Gelles et al., 2016] enables us to present a construction that relies on an even weaker assumption. We furnish evidence supporting our conjecture through numerical computation, combinatorial arguments from planar path graphs and based on well-studied heuristics from arithmetic geometry.

Subject Classification

ACM Subject Classification
  • Theory of computation → Error-correcting codes
Keywords
  • Tree codes
  • Sparse polynomials
  • Explicit constructions

Metrics

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

Related Versions

References

  1. Martin Aigner. A course in enumeration, volume 238 of Graduate Texts in Mathematics. Springer, Berlin, 2007. URL: https://doi.org/10.1145/1814370.1814375.
  2. Martin Aigner and Günter M. Ziegler. Proofs from The Book. Springer, Berlin, sixth edition, 2018. See corrected reprint of the 1998 original [ MR1723092], Including illustrations by Karl H. Hofmann. URL: https://doi.org/10.1007/978-3-662-57265-8.
  3. Inbar Ben Yaacov, Gil Cohen, and Anand Kumar Narayanan. Candidate tree codes via Pascal determinant cubes. ECCC, 2020. URL: https://eccc.weizmann.ac.il/report/2020/141/.
  4. Siddharth Bhandari and Prahladh Harsha. A note on the explicit constructions of tree codes over polylogarithmic-sized alphabet. arXiv preprint arXiv:2002.08231, 2020. URL: https://arxiv.org/abs/2002.08231.
  5. Zvika Brakerski, Yael Tauman Kalai, and Raghuvansh R. Saxena. Deterministic and efficient interactive coding from hard-to-decode tree codes. In 61st Annual IEEE Symposium on Foundations of Computer Science - FOCS 2020, pages 446-457. IEEE Computer Soc., Los Alamitos, CA, 2020. URL: https://doi.org/10.1109/FOCS46700.2020.00049.
  6. Mark Braverman. Towards deterministic tree code constructions. In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, pages 161-167. ACM, New York, 2012. URL: https://doi.org/10.1145/2090236.2090250.
  7. Gil Cohen, Bernhard Haeupler, and Leonard J. Schulman. Explicit binary tree codes with polylogarithmic size alphabet. In STOC'18 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 535-544. ACM, New York, 2018. URL: https://doi.org/10.1145/3188745.3188928.
  8. Gil Cohen and Shahar Samocha. Palette-alternating tree codes. In The 35th Computational Complexity Conference (CCC 2020). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.CCC.2020.11.
  9. Pierre Deligne. La conjecture de weil : I. Publications Mathématiques de l'IHÉS, 43:273-307, 1974. URL: https://doi.org/10.1007/bf02684373.
  10. Étienne Fouvry. Consequences of a result of N. Katz and G. Laumon concerning trigonometric sums. Israel Journal of Mathematics, 120:81-96, 2000. URL: https://doi.org/10.1007/s11856-000-1272-z.
  11. Étienne Fouvry and Nicholas Katz. A general stratification theorem for exponential sums, and applications. Journal Fur Die Reine Und Angewandte Mathematik - J REINE ANGEW MATH, 2001:115-166, January 2001. URL: https://doi.org/10.1515/crll.2001.082.
  12. 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, pages 1922-1936. ACM, New York, 2016. URL: https://doi.org/10.1137/1.9781611974331.ch135.
  13. Ira Gessel and Gérard Viennot. Binomial determinants, paths, and hook length formulae. Adv. in Math., 58(3):300-321, 1985. URL: https://doi.org/10.1016/0001-8708(85)90121-5.
  14. Richard W. Hamming. Error detecting and error correcting codes. Bell System Tech. J., 29:147-160, 1950. URL: https://doi.org/10.1002/j.1538-7305.1950.tb00463.x.
  15. Jørn Justesen. Class of constructive asymptotically good algebraic codes. IEEE Transactions on Information Theory, 18(5):652-656, 1972. URL: https://doi.org/10.1109/tit.1972.1054893.
  16. Sankeerth R. Karingula and Shachar Lovett. Codes over integers, and the singularity of random matrices with large entries. CoRR, abs/2010.12081, 2020. URL: https://arxiv.org/abs/2010.12081.
  17. Nicholas Katz and Gérard Laumon. Transformation de fourier et majoration de sommes exponentielles. Publications Mathématiques de l'IHÉS, 62:145-202, 1985. URL: https://doi.org/10.1007/bf02698808.
  18. Serge Lang and Andre Weil. Number of points of varieties over finite fields. American Journal of Mathematics, 76(4):819-827, 1954. URL: https://www.jstor.org/stable/2372655.
  19. Cristopher Moore and Leonard J. Schulman. Tree codes and a conjecture on exponential sums. In ITCS'14 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science, pages 145-153. ACM, New York, 2014. URL: https://doi.org/10.1145/2554797.2554813.
  20. 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. URL: https://doi.org/10.1137/1.9781611975994.81.
  21. Pavel Pudlák. Linear tree codes and the problem of explicit constructions. Linear Algebra Appl., 490:124-144, 2016. URL: https://doi.org/10.1016/j.laa.2015.10.030.
  22. Pavel Pudlák. On matrices potentially useful for tree codes. CoRR, abs/2012.03013, 2020. URL: https://arxiv.org/abs/2012.03013.
  23. Leonard J. Schulman. Deterministic coding for interactive communication. In Proceedings of the 25th annual ACM Symposium on Theory of Computing, pages 747-756, 1993. URL: https://doi.org/10.1145/167088.167279.
  24. Leonard J. Schulman. Postscript of 21 september 2003 to coding for interactive communication. http://users.cms.caltech.edu/ schulman/Papers/intercodingpostscript.txt, 1994. Google Scholar
  25. Leonard J. Schulman. Coding for interactive communication. IEEE Trans. Inform. Theory, 42(6, part 1):1745-1756, 1996. Codes and complexity. URL: https://doi.org/10.1109/18.556671.
  26. Claude E. Shannon. A mathematical theory of communication. Bell System Tech. J., 27:379-423, 623-656, 1948. URL: https://doi.org/10.1002/j.1538-7305.1948.tb01338.x.
  27. Michael Sipser and Daniel A. Spielman. Expander codes. IEEE Transactions on Information Theory, 42(6):1710-1722, 1996. URL: https://doi.org/10.1109/18.556667.
  28. Michael A. Tsfasman, Serge G. Vlăduţ, and Thomas Zink. Modular curves, Shimura curves, and Goppa codes, better than Varshamov-Gilbert bound. Mathematische Nachrichten, 109(1):21-28, 1982. URL: https://doi.org/10.1002/mana.19821090103.
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