TCS+ talk: Wednesday, May 23rd — Leonard Schulman, Caltech
The next TCS+ talk will take place this coming Wednesday, May 23rd at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 18:00 UTC). Leonard Schulman from Caltech will speak about “Explicit Binary Tree Codes with Polylogarithmic Size Alphabet” (abstract below).
Please make sure you reserve a spot for your group to join us live by signing up on the online form. As usual, for more information about the TCS+ online seminar series and the upcoming talks, or to suggest a possible topic or speaker, please see the website.
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)