Published June 2018
| public
Book Section - Chapter
Explicit binary tree codes with polylogarithmic size alphabet
Chicago
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.
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.Additional details
- Eprint ID
- 89095
- DOI
- 10.1145/3188745.3188928
- Resolver ID
- CaltechAUTHORS:20180823-141633075
- Center for the Mathematics of Information, Caltech
- NSF
- CCF-1527110
- NSF
- CCF-1618280
- NSF
- CCF-1750808
- NSF
- CCF-1618795
- European Institutes for Advanced Study (EURIAS)
- Marie Curie Fellowship
- Created
-
2018-08-23Created from EPrint's datestamp field
- Updated
-
2021-11-16Created from EPrint's last_modified field