Decoding Reed-Muller Codes over Product Sets

作     者：Kim, John Y. Kopparty, Swastik 

作者机构：Virtu Financial Austin TX 78746 USA Rutgers State Univ Dept Math New Brunswick NJ USA Rutgers State Univ Dept Comp Sci New Brunswick NJ USA 

出 版 物：《THEORY OF COMPUTING》 (Theory Comput.)

年 卷 期：2017年第13卷

页      面：1-38页

核心收录：

基　　金：National Science Foundation Graduate Research Fellowship [DGE-1433187] Sloan Fellowship NSF [CCF-1253886, CCF-1540634] 

主　　题：error-correcting codes Reed-Muller codes algebraic algorithms Schwartz-Zippel lemma 

摘      要：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 S-m, for every d 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.