  Tree codes, introduced by Schulman, are combinatorial structures essential to
coding for interactive communication. An infinite family of tree codes with
both rate and distance bounded by positive constants is called asymptotically
good. Rate being constant is equivalent to the alphabet size being constant.
Schulman proved that there are asymptotically good tree code families using the
Lovasz local lemma, yet their explicit construction remains an outstanding open
problem. In a major breakthrough, Cohen, Haeupler and Schulman constructed
explicit tree code families with constant distance, but over an alphabet
polylogarithmic in the length. Our main result is a randomized polynomial time
decoding algorithm for these codes making novel use of the polynomial method.
The number of errors corrected scales roughly as the block length to the
three-fourths power, falling short of the constant fraction error correction
guaranteed by the constant distance. We further present number theoretic
variants of Cohen-Haeupler-Schulman codes, all correcting a constant fraction
of errors with polylogarithmic alphabet size. Towards efficiently correcting
close to a constant fraction of errors, we propose a speculative convex
optimization approach inspired by compressed sensing.
