Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR18-032 | 23rd August 2020 22:07

Explicit Binary Tree Codes with Polylogarithmic Size Alphabet

RSS-Feed




Revision #1
Authors: Gil Cohen, Bernhard Haeupler, Leonard Schulman
Accepted on: 23rd August 2020 22:07
Downloads: 828
Keywords: 


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 $\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.



Changes to previous version:

Significant changes in presentation; Construction with distance larger than one half.


Paper:

TR18-032 | 14th February 2018 03:11

Explicit Binary Tree Codes with Polylogarithmic Size Alphabet





TR18-032
Authors: Gil Cohen, Bernhard Haeupler, Leonard Schulman
Publication: 15th February 2018 23:24
Downloads: 3147
Keywords: 


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 $\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.



ISSN 1433-8092 | Imprint