On Decoding Cohen-Haeupler-Schulman Tree Codes
| Autor: | Anand Kumar Narayanan, Matthew Weidner |
|---|---|
| Přispěvatelé: | Institut de Mathématiques de Jussieu - Paris Rive Gauche (IMJ-PRG), Université Pierre et Marie Curie - Paris 6 (UPMC)-Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), ALgorithms for coMmunicAtion SecuriTY (ALMASTY), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS) |
| Rok vydání: | 2020 |
| Předmět: |
FOS: Computer and information sciences
Discrete mathematics Information Theory (cs.IT) Computer Science - Information Theory Open problem [MATH.MATH-IT]Mathematics [math]/Information Theory [math.IT] Computational Complexity (cs.CC) Treewidth Computer Science - Computational Complexity Tree (data structure) Bounded function Error detection and correction Constant (mathematics) Time complexity Decoding methods Mathematics |
| Zdroj: | SODA ACM-SIAM Symposium on Discrete Algorithms, SODA 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Jan 2020, Salt Lake City, UT, United States. pp.1337-1356, ⟨10.1137/1.9781611975994.81⟩ Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms |
| DOI: | 10.1137/1.9781611975994.81 |
| Popis: | International audience; Tree codes, introduced by Schulman [26, 27], are combinatorial structures essential to coding for interactive communication. An infinite family of tree codes with both rate and distance bounded by positive constants is called asymptotically good. Rate being constant is equivalent to the alphabet size being constant. Schulman proved that there are asymptotically good tree code families, yet their explicit construction remains an outstanding open problem. In a major breakthrough, Cohen, Haeupler and Schulman [12] constructed explicit tree code families with constant distance, but over an alphabet polylogarithmic in the length. Our main result is a randomized polynomial time decoding algorithm for these codes making novel use of the polynomial method. The number of errors corrected scales roughly as the block length to the three-fourths power, falling short of the constant fraction error correction guaranteed by the constant distance. We further present number theoretic variants of Cohen-Haeupler-Schulman codes, all correcting a constant fraction of errors with polylogarithmic alphabet size. Towards efficiently correcting close to a constant fraction of errors, we propose a speculative convex optimization approach inspired by compressed sensing. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|