Explicit Binary Tree Codes with Polylogarithmic Size Alphabet
Tree codes are “real time” or “causal” error-correcting codes. They are
known to exist but explicit construction has been a longstanding open
problem. We report on progress on this problem.
For every constant delta 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.
Joint work with Gil Cohen (Princeton) and Bernhard Haeupler (CMU)