{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:53:55Z","timestamp":1781078035326,"version":"3.54.1"},"reference-count":49,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2014,9,8]],"date-time":"2014-09-08T00:00:00Z","timestamp":1410134400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2014,9,8]]},"abstract":"<jats:p>\n            Locally decodable codes are error-correcting codes that admit efficient decoding algorithms; any bit of the original message can be recovered by looking at only a small number of locations of a corrupted codeword. The tradeoff between the rate of a code and the locality\/efficiency of its decoding algorithms has been well studied, and it has widely been suspected that nontrivial locality must come at the price of low rate. A particular setting of potential interest in practice is codes of constant rate. For such codes, decoding algorithms with locality\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>k\u2208<\/jats:italic>\n            ) were known only for codes of rate\n            <jats:italic>\u2208<\/jats:italic>\n            \u03a9(1\/\n            <jats:italic>\u2208<\/jats:italic>\n            ), where\n            <jats:italic>k<\/jats:italic>\n            is the length of the message. Furthermore, for codes of rate &gt; 1\/2, no nontrivial locality had been achieved.\n          <\/jats:p>\n          <jats:p>\n            In this article, we construct a new family of locally decodable codes that have very efficient local decoding algorithms, and at the same time have rate approaching 1. We show that for every\n            <jats:italic>\u2208<\/jats:italic>\n            &gt; 0 and\n            <jats:italic>\u03b1<\/jats:italic>\n            &gt; 0, for infinitely many\n            <jats:italic>k<\/jats:italic>\n            , there exists a code\n            <jats:italic>C<\/jats:italic>\n            which encodes messages of length\n            <jats:italic>k<\/jats:italic>\n            with rate 1 \u2212\n            <jats:italic>\u03b1<\/jats:italic>\n            , and is locally decodable from a constant fraction of errors using\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>k\u2208<\/jats:italic>\n            ) queries and time.\n          <\/jats:p>\n          <jats:p>These codes, which we call multiplicity codes, are based on evaluating multivariate polynomials and their derivatives. Multiplicity codes extend traditional multivariate polynomial codes; they inherit the local-decodability of these codes, and at the same time achieve better tradeoffs and flexibility in the rate and minimum distance.<\/jats:p>","DOI":"10.1145\/2629416","type":"journal-article","created":{"date-parts":[[2014,9,9]],"date-time":"2014-09-09T14:39:29Z","timestamp":1410273569000},"page":"1-20","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":47,"title":["High-rate codes with sublinear-time decoding"],"prefix":"10.1145","volume":"61","author":[{"given":"Swastik","family":"Kopparty","sequence":"first","affiliation":[{"name":"Institute for Advanced Study"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shubhangi","family":"Saraf","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sergey","family":"Yekhanin","sequence":"additional","affiliation":[{"name":"Microsoft Research Silicon Valley"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2014,9,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/278298.278306"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/273865.273901"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-003-0025-0"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/103418.103428"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200056"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01275486"},{"key":"e_1_2_1_7_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the 7th International Symposium on Theoretical Aspects of Computer Science (STACS)","author":"Beaver Donald","unstructured":"Donald Beaver and Joan Feigenbaum . 1990. Hiding instances in multioracle queries . In Proceedings of the 7th International Symposium on Theoretical Aspects of Computer Science (STACS) . Lecture Notes in Computer Science , vol. 415 , Springer , Berlin , 37--48. Donald Beaver and Joan Feigenbaum. 1990. Hiding instances in multioracle queries. In Proceedings of the 7th International Symposium on Theoretical Aspects of Computer Science (STACS). Lecture Notes in Computer Science, vol. 415, Springer, Berlin, 37--48."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.88"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-011-0017-1"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 20th IEEE Computational Complexity Conference (CCC). 184--193","author":"Deshpande A.","unstructured":"A. Deshpande , R. Jain , T. Kavitha , S. Lokam , and J. Radhakrishnan . 2002. Better lower bounds for locally decodable codes . In Proceedings of the 20th IEEE Computational Complexity Conference (CCC). 184--193 . A. Deshpande, R. Jain, T. Kavitha, S. Lokam, and J. Radhakrishnan. 2002. Better lower bounds for locally decodable codes. In Proceedings of the 20th IEEE Computational Complexity Conference (CCC). 184--193."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2010.35"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.73"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.40"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536422"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/872747.873181"},{"key":"e_1_2_1_16_1","volume-title":"Electron. Colloq. Computat. Complex. (ECCC) 20","author":"Guo Alan","year":"2013","unstructured":"Alan Guo . 2013 . High rate locally correctable codes via lifting . Electron. Colloq. Computat. Complex. (ECCC) 20 , 53. Alan Guo. 2013. High rate locally correctable codes via lifting. Electron. Colloq. Computat. Complex. (ECCC) 20, 53."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2422436.2422494"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2007.911222"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/795666.796574"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.782097"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/2033252.2033304"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39206-1_46"},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","unstructured":"J. W. P. Hirschfeld G. Korchmaros and F. Torres. 2008. Algebraic Curves over a Finite Field. Princeton Series in Applied Mathematics Princeton University Press.  J. W. P. Hirschfeld G. Korchmaros and F. Torres. 2008. Algebraic Curves over a Finite Field . Princeton Series in Applied Mathematics Princeton University Press.","DOI":"10.1515\/9781400847419"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258590"},{"key":"e_1_2_1_25_1","article-title":"New constructions for query-efficient locally decodable codes of subexponential length. IEICE","author":"Itoh Toshiya","year":"2010","unstructured":"Toshiya Itoh and Yasuhiro Suzuki . 2010 . New constructions for query-efficient locally decodable codes of subexponential length. IEICE Trans. Inf. Syst. E93-D, 263--270. Toshiya Itoh and Yasuhiro Suzuki. 2010. New constructions for query-efficient locally decodable codes of subexponential length. IEICE Trans. Inf. Syst. E93-D, 263--270.","journal-title":"Trans. Inf. Syst. E93-D, 263--270."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1968.1054127"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335315"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.04.007"},{"key":"e_1_2_1_29_1","volume-title":"Electron. Colloq. Computat. Complex. (TR12-044)","author":"Kopparty Swastik","year":"2012","unstructured":"Swastik Kopparty . 2012 . List-decoding multiplicity codes . Electron. Colloq. Computat. Complex. (TR12-044) . Swastik Kopparty. 2012. List-decoding multiplicity codes. Electron. Colloq. Computat. Complex. (TR12-044)."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/625\/12497"},{"key":"e_1_2_1_31_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the 7th International Symposium on Theoretical Aspects of Computer Science (STACS)","author":"Lipton Richard","unstructured":"Richard Lipton . 1990. Efficient checking of computations . In Proceedings of the 7th International Symposium on Theoretical Aspects of Computer Science (STACS) . Lecture Notes in Computer Science , vol. 415 , Springer , Berlin , 207--215. Richard Lipton. 1990. Efficient checking of computations. In Proceedings of the 7th International Symposium on Theoretical Aspects of Computer Science (STACS). Lecture Notes in Computer Science, vol. 415, Springer, Berlin, 207--215."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146605"},{"key":"e_1_2_1_33_1","volume-title":"The Theory of Error Correcting Codes. North Holland","author":"MacWilliams F. J.","unstructured":"F. J. MacWilliams and N. J. A. Sloane . 1977. The Theory of Error Correcting Codes. North Holland , Amsterdam, The Netherlands . F. J. MacWilliams and N. J. A. Sloane. 1977. The Theory of Error Correcting Codes. North Holland, Amsterdam, The Netherlands."},{"key":"e_1_2_1_34_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the 6th International Workshop on Randomization and Computation (RANDOM)","author":"Obata Kenji","unstructured":"Kenji Obata . 2002. Optimal lower bounds for 2-query locally decodable linear codes . In Proceedings of the 6th International Workshop on Randomization and Computation (RANDOM) , Lecture Notes in Computer Science , vol. 2483 , Springer , Berlin , 39--50. Kenji Obata. 2002. Optimal lower bounds for 2-query locally decodable linear codes. In Proceedings of the 6th International Workshop on Randomization and Computation (RANDOM), Lecture Notes in Computer Science, vol. 2483, Springer, Berlin, 39--50."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.29"},{"key":"e_1_2_1_36_1","volume-title":"Electron. Colloq. Computat. Complex. (TR07-016)","author":"Raghavendra Prasad","year":"2007","unstructured":"Prasad Raghavendra . 2007 . A Note on Yekhanin\u2019s locally decodable codes . Electron. Colloq. Computat. Complex. (TR07-016) . Prasad Raghavendra. 2007. A Note on Yekhanin\u2019s locally decodable codes. Electron. Colloq. Computat. Complex. (TR07-016)."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1954.1057465"},{"key":"e_1_2_1_38_1","doi-asserted-by":"crossref","unstructured":"Shubhangi Saraf and Madhu Sudan. 2008. Improved lower bound on the size of Kakeya sets over finite fields. Analysis and PDE.  Shubhangi Saraf and Madhu Sudan. 2008. Improved lower bound on the size of Kakeya sets over finite fields. Analysis and PDE .","DOI":"10.2140\/apde.2008.1.375"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1059513.1059516"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146609"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.5555\/646032.677525"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/301250.301397"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/11523468_115"},{"key":"e_1_2_1_44_1","first-page":"633","article-title":"Error correction for algebraic block codes","volume":"4","author":"Welch Lloyd R.","year":"1986","unstructured":"Lloyd R. Welch and Elwyn R. Berlekamp . 1986 . Error correction for algebraic block codes . US Patent 4 , 633 ,470. Lloyd R. Welch and Elwyn R. Berlekamp. 1986. Error correction for algebraic block codes. US Patent 4,633,470.","journal-title":"US Patent"},{"key":"e_1_2_1_45_1","volume-title":"Electron. Colloq. Computat. Complex. (TR07-006)","author":"Woodruff David","year":"2007","unstructured":"David Woodruff . 2007 . New lower bounds for general locally decodable codes . Electron. Colloq. Computat. Complex. (TR07-006) . David Woodruff. 2007. New lower bounds for general locally decodable codes. Electron. Colloq. Computat. Complex. (TR07-006)."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2005.2"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2003.813559"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/1326554.1326555"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.5555\/2341141"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2629416","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2629416","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:19:30Z","timestamp":1750231170000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2629416"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,9,8]]},"references-count":49,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2014,9,8]]}},"alternative-id":["10.1145\/2629416"],"URL":"https:\/\/doi.org\/10.1145\/2629416","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,9,8]]},"assertion":[{"value":"2013-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-09-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}