אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

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.