2026-07-21T12:28:51Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12563 2024-03-06T10:50:27Z ddc:004 open_access

Palette-Alternating Tree Codes Cohen, Gil Samocha, Shahar Tree Codes Coding Theory Interactive Coding Scheme A 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 [Schulman, 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 code and serves as an alternative to the scheme obtained by [R. Gelles et al., 2016]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Gil Cohen and Shahar Samocha 2020 Is Part Of LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2020.11 urn:nbn:de:0030-drops-125632 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.11 eng https://creativecommons.org/licenses/by/3.0/legalcode