Seminars & Colloquia Calendar
Explicit Binary Tree Codes with Polylogarithmic Size Alphabet
Location: CoRE 301
Date & time: Wednesday, 14 February 2018 at 11:00AM - 12:00PM
Abstract: In this talk, we consider the problem of explicitly constructing a binary tree code with constant distance and constant alphabet size. We give an explicit binary tree code with constant distance and alphabet size polylog(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). For analyzing our construction, we prove a bound on the number of integral roots a real polynomial can have in terms of its sparsity with respect to a suitable basis--a result of independent interest.
Joint work with Bernhard Haeupler and Leonard Schulman.