Caltech Logo

TCS+ Talk

Wednesday, May 23, 2018
10:00am to 11:00am
Add to Cal
Annenberg 205
Explicit Binary Tree Codes with Polylogarithmic Size Alphabet
Leonard Schulman, Caltech,

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)

For more information, please contact Bonnie Leung by email at [email protected].