Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR20-141 | 11th September 2020 21:00

Candidate Tree Codes via Pascal Determinant Cubes


Authors: Inbar Ben Yaacov, Gil Cohen, Anand Kumar Narayanan
Publication: 16th September 2020 20:46
Downloads: 141


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 tree code property requires structure that remains elusive. To the best of our knowledge, only one candidate appears in the literature, due to Moore and Schulman (ITCS 2014).

We put forth a new candidate for an explicit asymptotically-good tree code. Our construction is an extension of the vanishing rate tree code by Cohen-Haeupler-Schulman (STOC 2018) combined with a vanishing distance tree code by Gelles et al. (SODA 2016). The correctness of our construction relies on a conjecture that we introduce on certain Pascal determinants indexed by the points of the Boolean hypercube. We furnish evidence supporting our conjecture through numerical computation, combinatorial arguments from planar path graphs and based on well-studied heuristics from arithmetic geometry.

ISSN 1433-8092 | Imprint