CaltechAUTHORS
  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. http://resolver.caltech.edu/CaltechAUTHORS:20180823-141633075

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

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20180823-141633075

Abstract

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
https://doi.org/10.1145/3188745.3188928DOIArticle
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.
Funders:
Funding AgencyGrant Number
Center for the Mathematics of Information, CaltechUNSPECIFIED
NSFCCF-1527110
NSFCCF-1618280
NSFCCF-1750808
NSFCCF-1618795
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:http://resolver.caltech.edu/CaltechAUTHORS:20180823-141633075
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:89095
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:23 Aug 2018 21:26
Last Modified:23 Aug 2018 21:26

Repository Staff Only: item control page