DIMACS Theory of Computing Seminar

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


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