October 4:  Leonard J. Schulman (Caltech)

Title: Explicit Binary Tree Codes with Polylogarithmic Size Alphabet

Abstract:
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)

Explicit Binary Tree Codes with Polylogarithmic Size Alphabet