Explicit binary tree codes with polylogarithmic size alphabet

This paper makes progress on 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 poly (log 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 ). At the core of our construction is the first explicit tree code with constant rate and constant distance, though with non-constant arity - a result of independent interest. This construction adapts the polynomial interpolation framework to the online setting.

Authors

• Gil Cohen
• Bernhard Haeupler
• Leonard J. Schulman

Keywords

• explicit constructions
• sparse polynomials
• tree codes