Decoding Reed–Muller Codes over Product Sets

by John Y. Kim and Swastik Kopparty

Theory of Computing, Volume 13(21), pp. 1-38, 2017

Bibliography with links to cited articles

[1]   Mikhail Alekhnovich: Linear diophantine equations over polynomials and soft decoding of Reed–Solomon codes. IEEE Trans. Inform. Theory, 51(7):2257–2265, 2005. Preliminary version in FOCS’02. [doi:10.1109/TIT.2005.850097]

[2]   László Babai, Lance Fortnow, Leonid Levin, and Mario Szegedy: Checking computations in polylogarithmic time. In Proc. 23rd STOC, pp. 21–31. ACM Press, 1991. [doi:10.1145/103418.103428]

[3]   Yuval Cassuto and Jehoshua Bruck: A combinatorial bound on the list size. Technical Report ETR 058, Paradise Laboratory, 2004. Avaliable at CalTech Library.

[4]   Parikshit Gopalan, Venkatesan Guruswami, and Prasad Raghavendra: List decoding tensor products and interleaved codes. SIAM J. Comput., 40(5):1432–1462, 2011. Preliminary version in STOC’09. [doi:10.1137/090778274]

[5]   Venkatesan Guruswami and Madhu Sudan: Improved decoding of Reed-Solomon and algebraic-geometric codes. IEEE Trans. Inform. Theory, 45(6):1757–1767, 1999. Preliminary version in FOCS’98. [doi:10.1109/18.782097]

[6]   Venkatesan Guruswami and Madhu Sudan: Decoding concatenated codes using soft information. In Proc. 17th IEEE Conf. on Computational Complexity (CCC’02), pp. 148–157. IEEE Comp. Soc. Press, 2002. [doi:10.1109/CCC.2002.1004350]

[7]   George David Forney Jr.: Generalized minimum distance decoding. IEEE Trans. Inform. Theory, 12(2):125–131, 1966. [doi:10.1109/TIT.1966.1053873]

[8]   Tadao Kasami, Shu Lin, and William Wesley Peterson: Polynomial codes. IEEE Trans. Inform. Theory, 14(6):807–814, 1968. [doi:10.1109/TIT.1968.1054226]

[9]   John Y. Kim and Swastik Kopparty: Decoding Reed-Muller codes over product sets. In Proc. 31st Conf. on Computational Complexity (CCC’16), volume 50 of Leibniz Internat. Proc. in Informatics (LIPIcs), pp. 11:1–28. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2016. [doi:10.4230/LIPIcs.CCC.2016.11]

[10]   Swastik Kopparty: List-decoding multiplicity codes. Theory of Computing, 11(5):149–182, 2015. [doi:10.4086/toc.2015.v011a005]

[11]   Swastik Kopparty, Shubhangi Saraf, and Sergey Yekhanin: High-rate codes with sublinear-time decoding. J. ACM, 61(5):28:1–28:20, 2014. Preliminary version in STOC’11. [doi:10.1145/2629416]

[12]   Florence Jessie MacWilliams and Neil J. A. Sloane: The Theory of Error-Correcting Codes. Elsevier/North-Holland, Amsterdam, New York, 1981.

[13]   James Lee Massey: Shift-register synthesis and BCH decoding. IEEE Trans. Inform. Theory, 15(1):122–127, 1969. [doi:10.1109/TIT.1969.1054260]

[14]   David Eugene Muller: Application of boolean algebra to switching circuit design and to error detection. IEEE Trans. on Computers, EC-3(3):6–12, 1954. [doi:10.1109/IREPGELC.1954.6499441]

[15]   Ruud Pellikaan and Xin-Wen Wu: List decoding of q-ary Reed-Muller codes. IEEE Trans. Inform. Theory, 50(4):679–682, 2004. [doi:10.1109/TIT.2004.825043]

[16]   William Wesley Peterson: Encoding and error-correction procedures for Bose-Chaudhuri codes. IEEE Trans. Inform. Theory, 6(4):459–470, 1960. [doi:10.1109/TIT.1960.1057586]

[17]   Irving Stoy Reed: A class of multiple-error-correcting codes and the decoding scheme. IEEE Trans. Inform. Theory, 4(4):38–49, 1954. [doi:10.1109/TIT.1954.1057465]

[18]   Irving Stoy Reed and Gustav Solomon: Polynomial codes over certain finite fields. J. Soc. Indust. Appl. Math., 8(2):300–304, 1960. [doi:10.1137/0108018]

[19]   Ronny Roth and Gitit Ruckenstein: Efficient decoding of Reed-Solomon codes beyond half the minimum distance. IEEE Trans. Inform. Theory, 46(1):246–257, 2000. Preliminary version in ISIT’98. [doi:10.1109/18.817522]

[20]   Madhu Sudan: Decoding of Reed Solomon codes beyond the error-correction bound. J. Complexity, 13(1):180–193, 1997. Preliminary version in FOCS’96. [doi:10.1006/jcom.1997.0439]

[21]   Lloyd Richard Welch and Elwyn Ralph Berlekamp: Error correction of algebraic block codes. US Patent Number 4,633,470, December 1986. URL: