@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 = "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",

}