期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2020
卷号：2020
页码：1-36
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：Tree codes are combinatorial structures introduced by Schulman [Sch93] 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 [MS14]. 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-HaeuplerSchulman [CHS18] combined with a vanishing distance tree code by Gelles et al. [GHK 16]. 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.
