2015/11/23 by John Kim, Swastik Kopparty, Kim, John +1
Computer Science · Engineering · #Cellular Automata and Applications #Coding theory and cryptography #Combinatorics (math.CO) #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1511.07488
openalex publication_date 2015/11/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
We give a polynomial time algorithm to decode multivariate polynomial codes of degree d up to half their minimum distance, when the evaluation points are an arbitrary product set Sm, for every d < |S|. Previously known algorithms can achieve this only if the set S has some very special algebraic structure, or if the degree d is significantly smaller than |S|. We also give a near-linear time randomized algorithm, which is based on tools from list-decoding, to decode these codes from nearly half their minimum distance, provided d < (1-ε)|S| for constant ε> 0. Our result gives an m-dimensional generalization of the well known decoding algorithms for Reed-Solomon codes, and can be viewed as giving an algorithmic version of the Schwartz-Zippel lemma.