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: www.google.com/patents/US4633470.