Tree Codes and a Conjecture on Exponential Sums

ACO Colloquium
Thursday, January 9, 2014 - 4:30pm for 1 hour (actually 50 minutes)
Skiles 005
Leonard J. Schulman – Professor, CalTech
Prasad Tetali
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.)