@inproceedings{79112ecd62574d3689d9139d1ad25928,

title = "Explicit binary tree codes with polylogarithmic size alphabet",

abstract = "This paper makes progress on the problem of explicitly constructing a binary tree code with constant distance and constant alphabet size. For every constant < 1 we give an explicit binary tree code with distance and alphabet size poly(log n), 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). As part of the analysis, we prove a bound on the number of positive integer roots a real polynomial can have in terms of its sparsity with respect to the Newton basis—a result of independent interest.",

keywords = "Explicit constructions, Sparse polynomials, Tree codes",

author = "Gil Cohen and Bernhard Haeupler and Schulman, {Leonard J.}",

note = "Funding Information: 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{\l}odowska-Curie Actions under the 7th Framework Programme. The second author thanks Noga Ron-Zewi and Shachar Lovett for many helpful discussions. Publisher Copyright: {\textcopyright} 2018 Association for Computing Machinery.; 50th Annual ACM Symposium on Theory of Computing, STOC 2018 ; Conference date: 25-06-2018 Through 29-06-2018",

year = "2018",

month = jun,

day = "20",

doi = "10.1145/3188745.3188928",

language = "English (US)",

series = "Proceedings of the Annual ACM Symposium on Theory of Computing",

publisher = "Association for Computing Machinery",

pages = "1074--1087",

editor = "Monika Henzinger and David Kempe and Ilias Diakonikolas",

booktitle = "STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing",

}