ECCC-Report TR21-154https://eccc.weizmann.ac.il/report/2021/154Comments and Revisions published for TR21-154en-usWed, 10 Nov 2021 13:16:50 +0200
Paper TR21-154
| Explicit Binary Tree Codes with Sub-Logarithmic Size Alphabet |
Gil Cohen,
Inbar Ben Yaacov,
Tal Yankovitz
https://eccc.weizmann.ac.il/report/2021/154Since they were first introduced by Schulman (STOC 1993), the construction of tree codes remained an elusive open problem. The state-of-the-art construction by Cohen, Haeupler and Schulman (STOC 2018) has constant distance and $(\log n)^{e}$ colors for some constant $e > 1$ that depends on the distance, where $n$ is the depth of the tree. Insisting on a constant number of colors at the expense of having vanishing distance, Gelles, Haeupler, Kol, Ron-Zewi, and Wigderson (SODA 2016) constructed a distance $\Omega(\frac1{\log n})$ tree code.
In this work we improve upon these prior works and construct a distance-$\delta$ tree code with $(\log{n})^{O(\sqrt{\delta})}$ colors. This is the first construction of a constant distance tree code with sub-logarithmic number of colors. Moreover, as a direct corollary we obtain a tree code with a constant number of colors and distance $\Omega\left(\frac1{(\log\log{n})^{2}}\right)$, exponentially improving upon the above-mentioned work by Gelles et al.
Wed, 10 Nov 2021 13:16:50 +0200https://eccc.weizmann.ac.il/report/2021/154