Title: Explicit Binary Tree Codes with Polylogarithmic Size Alphabet
Speaker: Gil Cohen, Princeton University
Date: Wednesday, February 14, 2018 11:00am-12:00pm
Location: CoRE Bldg, Room 301, Rutgers University, Busch Campus, Piscataway, NJ
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.
See: https://sites.google.com/view/dimacs-theory-seminar/home