List-Decoding Multiplicity Codes

by Swastik Kopparty

Theory of Computing, Volume 11(5), pp. 149-182, 2015

Bibliography with links to cited articles

[1]   Sanjeev Arora and Madhu Sudan: Improved low-degree testing and its applications. Combinatorica, 23(3):365–426, 2003. Preliminary version in STOC’97. See also at ECCC. [doi:10.1007/s00493-003-0025-0]

[2]   Kristian Brander and Swastik Kopparty: List-decoding Reed-Muller over large fields upto the Johnson radius. Manuscript, 2009.

[3]   Zeev Dvir, Swastik Kopparty, Shubhangi Saraf, and Madhu Sudan: Extensions to the method of multiplicities, with applications to Kakeya sets and mergers. SIAM J. Comput., 42(6):2305–2328, 2013. Preliminary version in FOCS’09. See also at ECCC. [doi:10.1137/100783704]

[4]   Zeev Dvir and Shachar Lovett: Subspace evasive sets. In Proc. 44th STOC, pp. 351–358. ACM Press, 2012. See also at arXiv. [doi:10.1145/2213977.2214010]

[5]   Gerald B. Folland: Introduction to Partial Differential Equations. Princeton University Press, 1995.

[6]   Alan Guo: High rate locally correctable codes via lifting. Electron. Colloq. on Comput. Complexity (ECCC), 20:53, 2013. See also at arXiv.

[7]   Alan Guo and Swastik Kopparty: List-decoding algorithms for lifted codes. CoRR, abs/1412.0305, 2014. [arXiv:1412.0305]

[8]   Alan Guo, Swastik Kopparty, and Madhu Sudan: New affine-invariant codes from lifting. In Robert D. Kleinberg, editor, Proc. 4th Conf. on Innovations in Theoretical Computer Science (ITCS’13), pp. 529–540. ACM Press, 2013. See also at arXiv and ECCC. [doi:10.1145/2422436.2422494]

[9]   Venkatesan Guruswami and Swastik Kopparty: Explicit subspace designs. Combinatorica, pp. 1–25, 2014. Preliminary version in FOCS’13. See also ECCC. [doi:10.1007/s00493-014-3169-1]

[10]   Venkatesan Guruswami and Atri Rudra: Explicit codes achieving list decoding capacity: Error-correction with optimal redundancy. IEEE Trans. Inform. Theory, 54(1):135–150, 2008. Preliminary version in STOC’06. [doi:10.1109/TIT.2007.911222]

[11]   Venkatesan Guruswami, Amit Sahai, and Madhu Sudan: “Soft-decision” decoding of Chinese Remainder Codes. In Proc. 41st FOCS, pp. 159–168. IEEE Comp. Soc. Press, 2000. [doi:10.1109/SFCS.2000.892076]

[12]   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. See also at ECCC. [doi:10.1109/18.782097]

[13]   Venkatesan Guruswami and Carol Wang: Linear-algebraic list decoding for variants of Reed-Solomon codes. IEEE Trans. Inform. Theory, 59(6):3257–3268, 2013. See also at ECCC. [doi:10.1109/TIT.2013.2246813]

[14]   Venkatesan Guruswami and Chaoping Xing: Folded codes from function field towers and improved optimal rate list decoding. In Proc. 44th STOC, pp. 339–350. ACM Press, 2012. See also at ECCC and arXiv. [doi:10.1145/2213977.2214009]

[15]    Venkatesan Guruswami and Chaoping Xing: List decoding Reed-Solomon, Algebraic-Geometric, and Gabidulin subcodes up to the Singleton bound. In Proc. 45th STOC, pp. 843–852. ACM Press, 2013. See also at ECCC. [doi:10.1145/2488608.2488715]

[16]   Venkatesan Guruswami and Chaoping Xing: Optimal rate algebraic list decoding using narrow ray class fields. J. Combin. Theory Ser. A, 129:160–183, 2015. Partial preliminary version in SODA’14. See also at arXiv and ECCC. [doi:10.1016/j.jcta.2014.09.003]

[17]   Brett Hemenway, Rafail Ostrovsky, and Mary Wootters: Local correctability of expander codes. In Fedor V. Fomin, Rusins Freivalds, Marta Z. Kwiatkowska, and David Peleg, editors, Proc. 40th Internat. Colloq. on Automata, Languages and Programming (ICALP’13), volume 7965 of Lecture Notes in Computer Science, pp. 540–551. Springer, 2013. See also at arXiv. [doi:10.1007/978-3-642-39206-1_46]

[18]   James W. P. Hirschfeld, Gábor Korchmáros, and Fernando Torres: Algebraic Curves over a Finite Field (Princeton Series in Applied Mathematics). Princeton University Press, 2008.

[19]   Swastik Kopparty: Algebraic methods in randomness and pseudorandomness. Ph. D. thesis, Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2010. DSpace@MIT.

[20]   Swastik Kopparty: List-decoding multiplicity codes. Electron. Colloq. on Comput. Complexity (ECCC), 12:44, 2012.

[21]   Swastik Kopparty: Some remarks on multiplicity codes. In Alexander Barg and Oleg R. Musin, editors, Discrete Geometry and Algebraic Combinatorics: AMS Spec. Session, volume 625 of Contemporary Mathematics, pp. 155–176. Amer. Math. Soc., 2014. [doi:10.1090/conm/625, arXiv:1505.07547]

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

[23]   Farzad Parvaresh and Alexander Vardy: Correcting errors beyond the Guruswami-Sudan radius in polynomial time. In Proc. 46th FOCS, pp. 285–294. IEEE Comp. Soc. Press, 2005. [doi:10.1109/SFCS.2005.29]

[24]   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]

[25]   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]

[26]   Madhu Sudan: Ideal error-correcting codes: Unifying algebraic and number-theoretic algorithms. In Serdar Boztas and Igor Shparlinski, editors, Proc. 14th Internat. Symp. Applied Algebra, Algebraic Algorithms and Error-Correcting Codes (AAECC’01), volume 2227 of Lecture Notes in Computer Science, pp. 36–45. Springer, 2001. [doi:10.1007/3-540-45624-4_4]

[27]   Madhu Sudan, Luca Trevisan, and Salil P. Vadhan: Pseudorandom generators without the XOR lemma. J. Comput. System Sci., 62(2):236–266, 2001. Preliminary version in CCC’99 and STOC’99. See also at ECCC. [doi:10.1006/jcss.2000.1730]

[28]   Salil P. Vadhan: Pseudorandomness. Foundations and Trends in Theoretical Computer Science, 7(1-3):1–336, 2012. [doi:10.1561/0400000010]