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.

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

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.