A Caltech Library Service

Explicit binary tree codes with polylogarithmic size alphabet

Cohen, Gil and Haeupler, Bernhard and Schulman, Leonard J. (2018) Explicit binary tree codes with polylogarithmic size alphabet. In: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. Association for Computing Machinery , New York, NY, pp. 535-544. ISBN 978-1-4503-5559-9.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


This paper makes progress on the problem of explicitly constructing a binary tree code with constant distance and constant alphabet size. We give an explicit binary tree code with constant distance and alphabet size poly(logn), where n is the depth of the tree. This is the first improvement over a two-decade-old construction that has an exponentially larger alphabet of size poly(n). At the core of our construction is the first explicit tree code with constant rate and constant distance, though with non-constant arity - a result of independent interest. This construction adapts the polynomial interpolation framework to the online setting.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Schulman, Leonard J.0000-0001-9901-2797
Additional Information:© 2018 Association for Computing Machinery. Part of this work was done while the first author was a CMI Postdoctoral Fellow at the California Institute of Technology. The second author was supported in part by NSF grants CCF-1527110, CCF-1618280 and NSF CAREER award CCF-1750808. The third author was supported in part by NSF grant 1618795; and part of the work was done while he was in residence at the Israel Institute for Advanced Studies, supported by a EURIAS Senior Fellowship co-funded by the Marie Skłodowska-Curie Actions under the 7th Framework Programme. The second author thanks Noga Ron-Zewi and Shachar Lovett for many helpful discussions.
Funding AgencyGrant Number
Center for the Mathematics of Information, CaltechUNSPECIFIED
European Institutes for Advanced Study (EURIAS)UNSPECIFIED
Marie Curie FellowshipUNSPECIFIED
Subject Keywords:tree codes, sparse polynomials, explicit constructions
Record Number:CaltechAUTHORS:20180823-141633075
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:89095
Deposited By: Tony Diaz
Deposited On:23 Aug 2018 21:26
Last Modified:16 Nov 2021 00:32

Repository Staff Only: item control page