Tree Codes and a Conjecture on Exponential Sums

2013/08/27 by Cristopher Moore, Moore, Cristopher, Leonard J. Schulman +1
Computer Science · Engineering · #Coding theory and cryptography #Computational Complexity (cs.CC) #Error Correcting Code Techniques #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Number Theory (math.NT) #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.1308.6007

openalex publication_date 2013/08/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We propose a new conjecture on some exponential sums. These particular sums have not apparently been considered in the 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.

Related

• A note on the explicit constructions of tree codes over polylogarithmic-sized alphabet
• A New Class of Linear Codes
• On Decoding Cohen-Haeupler-Schulman Tree Codes
• The Rate-Immediacy Barrier in Explicit Tree Code Constructions
• On Some Exponential Sums Related to the Coulter's Polynomial