ECCC-Report TR20-014https://eccc.weizmann.ac.il/report/2020/014Comments and Revisions published for TR20-014en-usTue, 18 Feb 2020 17:46:07 +0200
Paper TR20-014
| Palette-Alternating Tree Codes |
Gil Cohen,
Shahar Samocha
https://eccc.weizmann.ac.il/report/2020/014A 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 (STOC 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 codes and serves as an alternative to the scheme obtained by Gelles et al. (SODA 2016)Tue, 18 Feb 2020 17:46:07 +0200https://eccc.weizmann.ac.il/report/2020/014