Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Inbar Ben Yaacov:

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

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

ISSN 1433-8092 | Imprint