Georgia Institute of Technology College of Sciences

Tree codes are the basic underlying combinatorial object in the interactive coding theorem, much as block error-correcting codes are the underlying object in one-way communication. However, even after two decades, effective (poly-time) constructions of tree codes are not known. In this work we propose a new conjecture on some exponential sums. These particular sums have not apparently previously been considered in the analytic number theory literature. Subject to the conjecture we obtain the first effective construction of asymptotically good tree codes. The available numerical evidence is consistent with the conjecture and is sufficient to certify codes for significant-length communications. (Joint work with Cris Moore.)