Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > TREE CODES:
Reports tagged with tree codes:
TR11-064 | 23rd April 2011
Mark Braverman

#### Towards deterministic tree code constructions

We present a deterministic operator on tree codes -- we call tree code product -- that allows one to deterministically combine two tree codes into a larger tree code. Moreover, if the original tree codes are efficiently encodable and decodable, then so is their product. This allows us to give ... more >>>

TR12-104 | 8th August 2012
Matthew Franklin, Ran Gelles, Rafail Ostrovsky, Leonard Schulman

#### Optimal Coding for Streaming Authentication and Interactive Communication

Revisions: 1

Error correction and message authentication are well studied in the literature, and various efficient solutions have been suggested and analyzed. This is however not the case for data streams in which the message is very long, possibly infinite, and not known in advance to the sender. Trivial solutions for error-correcting ... more >>>

TR17-079 | 1st May 2017
Alexander A. Sherstov, Pei Wu

#### Optimal Interactive Coding for Insertions, Deletions, and Substitutions

Interactive coding, pioneered by Schulman (FOCS 1992, STOC 1993), is concerned with making communication protocols resilient to adversarial noise. The canonical model allows the adversary to alter a small constant fraction of symbols, chosen at the adversary's discretion, as they pass through the communication channel. Braverman, Gelles, Mao, and Ostrovsky ... more >>>

TR18-032 | 14th February 2018
Gil Cohen, Bernhard Haeupler, Leonard Schulman

#### Explicit Binary Tree Codes with Polylogarithmic Size Alphabet

Revisions: 1

This paper makes progress on the problem of explicitly constructing a binary tree code with constant distance and constant alphabet size.

For every constant $\delta < 1$ we give an explicit binary tree code with distance $\delta$ and alphabet size $(\log{n})^{O(1)}$, where $n$ is the depth of the tree. This ... more >>>

TR19-147 | 31st October 2019
Gil Cohen, Shahar Samocha

#### Capacity-Approaching Deterministic Interactive Coding Schemes Against Adversarial Errors

We devise a deterministic interactive coding scheme with rate $1-O(\sqrt{\varepsilon\log(1/\varepsilon)})$ against $\varepsilon$-fraction of adversarial errors. The rate we obtain is tight by a result of Kol and Raz (STOC 2013). Prior to this work, deterministic coding schemes for any constant fraction $\varepsilon>0$ of adversarial errors could obtain rate no larger ... more >>>

TR20-014 | 16th February 2020
Gil Cohen, Shahar Samocha

#### 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 (STOC 1993) and ... more >>>

TR20-019 | 19th February 2020

#### A note on the explicit constructions of tree codes over polylogarithmic-sized alphabet

Recently, Cohen, Haeupler and Schulman gave an explicit construction of binary tree codes over polylogarithmic-sized output alphabet based on Pudl\'{a}k's construction of maximum-distance-separable (MDS) tree codes using totally-non-singular triangular matrices. In this short note, we give a unified and simpler presentation of Pudl\'{a}k and Cohen-Haeupler-Schulman's constructions.

more >>>

TR20-141 | 11th September 2020
Inbar Ben Yaacov, Gil Cohen, Anand Kumar Narayanan

#### Candidate Tree Codes via Pascal Determinant Cubes

Tree codes are combinatorial structures introduced by Schulman (STOC 1993) as key ingredients in interactive coding schemes. Asymptotically-good tree codes are long known to exist, yet their explicit construction remains a notoriously hard open problem. Even proposing a plausible construction, without the burden of proof, is difficult and the defining ... more >>>

TR21-154 | 10th November 2021
Inbar Ben Yaacov, Gil Cohen, Tal Yankovitz

#### Explicit Binary Tree Codes with Sub-Logarithmic Size Alphabet

Since 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 ... more >>>

TR22-095 | 5th July 2022
Meghal Gupta, Rachel Zhang

#### Efficient Interactive Coding Achieving Optimal Error Resilience Over the Binary Channel

Given a noiseless protocol $\pi_0$ computing a function $f(x, y)$ of Alice and Bob's private inputs $x, y$, the goal of interactive coding is to construct an error-resilient protocol $\pi$ computing $f$ such that even if some fraction of the communication is adversarially corrupted, both parties still learn $f(x, y)$. ... more >>>

ISSN 1433-8092 | Imprint