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. https://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: https://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: |
| ||||||||||||||||
ORCID: |
| ||||||||||||||||
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: |
| ||||||||||||||||
Subject Keywords: | tree codes, sparse polynomials, explicit constructions | ||||||||||||||||
DOI: | 10.1145/3188745.3188928 | ||||||||||||||||
Record Number: | CaltechAUTHORS:20180823-141633075 | ||||||||||||||||
Persistent URL: | https://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: | 16 Nov 2021 00:32 |
Repository Staff Only: item control page