Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People
Events

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: Explicit Binary Tree Codes with Polylogarithmic Size Alphabet
event speaker icon
Gil Cohen
event date icon
Wednesday, 23.10.2019, 12:30
event location icon
Taub 201 Taub Bld.
A tree code is a combinatorial object introduced by Schulman in the early 90s as a key ingredient in interactive coding. Schulman proved the existence of tree codes with constant alphabet size, but the problem of explicitly constructing a tree code remained elusive. We present an explicit binary tree code with constant distance and alphabet size polylog(n), where n is the depth of the tree. This improves over the (Evans-Klugerman-Schulman 1994) construction that requires 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 the Newton basis.

Joint work with Bernhard Haeupler and Leonard J. Schulman.