2015/07/07 by Matt Keti, Daqing Wan, Keti, Matt +1 · 1 citation
Computer Science · Engineering · #Cellular Automata and Applications #Coding theory and cryptography #FOS: Mathematics #Number Theory (math.NT) #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1507.01653
openalex publication_date 2015/07/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
For an [n,k] Reed-Solomon code C, it can be shown that any received word r lies a distance at most n-k from C, denoted d(r,C)≤ n-k. Any word r meeting the equality is called a deep hole. Guruswami and Vardy (2005) showed that for a specific class of codes, determining whether or not a word is a deep hole is NP-hard. They suggested passingly that it may be easier when the evaluation set of C is large or structured. Following this idea, we study the case where the evaluation set is the image of a Dickson polynomial, whose values appear with a special uniformity. To find families of received words that are not deep holes, we reduce to a subset sum problem (or equivalently, a Dickson polynomial-variation of Waring's problem) and find solution conditions by applying an argument using estimates on character sums indexed over the evaluation set.