Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH scholarly article en Cohen, Gil; Samocha, Shahar License: Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)
when quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-125632


Palette-Alternating Tree Codes



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].

BibTeX - Entry

  author =	{Gil Cohen and Shahar Samocha},
  title =	{{Palette-Alternating Tree Codes}},
  booktitle =	{35th Computational Complexity Conference (CCC 2020)},
  pages =	{11:1--11:29},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-156-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{169},
  editor =	{Shubhangi Saraf},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-125632},
  doi =		{10.4230/LIPIcs.CCC.2020.11},
  annote =	{Keywords: Tree Codes, Coding Theory, Interactive Coding Scheme}

Keywords: Tree Codes, Coding Theory, Interactive Coding Scheme
Seminar: 35th Computational Complexity Conference (CCC 2020)
Issue date: 2020
Date of publication: 17.07.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI