Abstract:Since the introduction of tree codes by Schulman (STOC 1993), explicit construction of asymptotically good tree codes has remained a notorious challenge. A work by Cohen, Haeupler and Schulman (STOC 2018), as well as the state-of-the-art construction by Ben Yaacov, Cohen, and Yankovitz (STOC 2022) have achieved codes with rate $\Omega(1/\log\log n)$, exponentially improving upon the original rate $\Omega(1/\log n)$ construction of Evans, Klugerman and Schulman from 1994. All of these constructions rely, at least in part, on increasingly sophisticated methods of combining (block) error-correcting codes.
In this work, we identify a fundamental barrier to constructing tree codes using known techniques. We introduce a key property which we call immediacy, that, while not required by the original definition of tree codes, is shared by all known constructions and inherently arises in recursive combinations of error-correcting codes. Our main technical contribution is the proof of a rate-immediacy trade-off, which, in particular, implies that any tree code with constant distance and non-trivial immediacy must necessarily have vanishing rate. By applying our rate-immediacy trade-off to existing constructions, we establish that their known rate analyses are essentially optimal given their actual error-correction properties. More broadly, our work highlights the need for fundamentally new ideas -- beyond the recursive use of error-correcting codes -- to achieve substantial progress in explicitly constructing asymptotically good tree codes.
| Comments: | Added further discussion and examples. To appear in proceedings of CCC 2026 |
| Subjects: | Information Theory (cs.IT); Computational Complexity (cs.CC); Discrete Mathematics (cs.DM) |
| Cite as: | arXiv:2504.09388 [cs.IT] |
| (or arXiv:2504.09388v2 [cs.IT] for this version) | |
| https://doi.org/10.48550/arXiv.2504.09388 arXiv-issued DOI via DataCite |
From: Piyush Srivastava [view email]
[v1]
Sun, 13 Apr 2025 00:47:48 UTC (26 KB)
[v2]
Fri, 22 May 2026 07:03:01 UTC (29 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。