ECCC-Report TR18-032https://eccc.weizmann.ac.il/report/2018/032Comments and Revisions published for TR18-032en-usSun, 23 Aug 2020 22:07:34 +0300
Revision 1
| Explicit Binary Tree Codes with Polylogarithmic Size Alphabet |
Gil Cohen,
Leonard Schulman,
Bernhard Haeupler
https://eccc.weizmann.ac.il/report/2018/032#revision1This 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 $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.Sun, 23 Aug 2020 22:07:34 +0300https://eccc.weizmann.ac.il/report/2018/032#revision1
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