ECCC-Report TR18-032https://eccc.weizmann.ac.il/report/2018/032Comments and Revisions published for TR18-032en-usThu, 15 Feb 2018 23:24:41 +0200
Paper TR18-032
| Explicit Binary Tree Codes with Polylogarithmic Size Alphabet |
Gil Cohen,
Leonard Schulman,
Bernhard Haeupler
https://eccc.weizmann.ac.il/report/2018/032This paper makes progress on the problem of explicitly constructing a binary tree code with constant distance and constant alphabet size.
For every constant $\delta < 1$ we give an explicit binary tree code with distance $\delta$ and alphabet size $(\log{n})^{O(1)}$, 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 $n^{O(1)}$.
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.
Thu, 15 Feb 2018 23:24:41 +0200https://eccc.weizmann.ac.il/report/2018/032