{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,15]],"date-time":"2026-04-15T20:31:10Z","timestamp":1776285070655,"version":"3.50.1"},"reference-count":69,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2017,4,30]],"date-time":"2017-04-30T00:00:00Z","timestamp":1493510400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CCF-1253886, CCF-1412958, CCF-1445755 and CCF-1350572"],"award-info":[{"award-number":["CCF-1253886, CCF-1412958, CCF-1445755 and CCF-1350572"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Sloan Fellowship, Rothschild Fellowship"},{"name":"ERC","award":["239986"],"award-info":[{"award-number":["239986"]}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"crossref","award":["460\/05"],"award-info":[{"award-number":["460\/05"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2017,4,30]]},"abstract":"<jats:p>\n            Locally correctable codes (LCCs) and locally testable codes (LTCs) are error-correcting codes that admit\n            <jats:italic>local<\/jats:italic>\n            algorithms for correction and detection of errors. Those algorithms are local in the sense that they only query a small number of entries of the corrupted codeword. The fundamental question about LCCs and LTCs is to determine the optimal tradeoff among their rate, distance, and query complexity.\n          <\/jats:p>\n          <jats:p>\n            In this work, we construct the first LCCs and LTCs with constant rate, constant relative distance, and sub-polynomial query complexity. Specifically, we show that there exist LCCs and LTCs with block length\n            <jats:italic>n<\/jats:italic>\n            , constant rate (which can even be taken arbitrarily close to 1), and constant relative distance, whose query complexity is exp(\u00d5(\u221alog\n            <jats:italic>n<\/jats:italic>\n            )) (for LCCs) and (log\n            <jats:italic>n<\/jats:italic>\n            )\n            <jats:sup>\n              <jats:italic>O<\/jats:italic>\n              (log log\n              <jats:italic>n<\/jats:italic>\n              )\n            <\/jats:sup>\n            (for LTCs).\n          <\/jats:p>\n          <jats:p>\n            In addition to having small query complexity, our codes also achieve better tradeoffs between the rate and the relative distance than were previously known to be achievable by LCCs or LTCs. Specifically, over large (but constant size) alphabet, our codes approach the Singleton bound, that is, they have almost the best-possible relationship between their rate and distance. Over the binary alphabet, our codes meet the Zyablov bound. Such tradeoffs between the rate and the relative distance were previously not known for any\n            <jats:italic>o<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            ) query complexity. Our results on LCCs also immediately give locally decodable codes with the same parameters.\n          <\/jats:p>","DOI":"10.1145\/3051093","type":"journal-article","created":{"date-parts":[[2017,5,25]],"date-time":"2017-05-25T16:16:45Z","timestamp":1495729005000},"page":"1-42","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":36,"title":["High-Rate Locally Correctable and Locally Testable Codes with Sub-Polynomial Query Complexity"],"prefix":"10.1145","volume":"64","author":[{"given":"Swastik","family":"Kopparty","sequence":"first","affiliation":[{"name":"Department of Mathematics 8 Department of Computer Science, Rutgers University, Piscataway NJ, USA"}]},{"given":"Or","family":"Meir","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Haifa University, Haifa, Israel"}]},{"given":"Noga","family":"Ron-Zewi","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Ben-Gurion University, Be\u2019er Sheva, Israel"}]},{"given":"Shubhangi","family":"Saraf","sequence":"additional","affiliation":[{"name":"Department of Mathematics 8 Department of Computer Science, Rutgers University, Piscataway NJ, USA"}]}],"member":"320","published-online":{"date-parts":[[2017,5,25]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.119713"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(88)90189-6"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/795662.796292"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.556669"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(85)90092-9"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/278298.278306"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/273865.273901"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/103418.103428"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01275486"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/1133618.1133623"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/050646445"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2009.v005a012"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-012-0042-8"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-013-0074-8"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/200836.200880"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90044-W"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/293347.293350"},{"key":"e_1_2_1_18_1","volume-title":"On the robust testability of tensor products of codes. Electronic Colloquium on Computational Complexity (ECCC) 104","author":"Coppersmith Don","year":"2005"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1236457.1236459"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-22935-0_43"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/11830924_29"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1984-0743744-X"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/090772721"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1966.1053873"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISTCS.1995.377032"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(81)90040-4"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1952.tb01393.x"},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","volume-title":"Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation","author":"Goldreich Oded","DOI":"10.1007\/978-3-642-22670-0"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2012.01.007"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1162349.1162351"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2422436.2422494"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.510023"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.855587"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2007.911222"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1950.tb00463.x"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2014.12.013"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47672-7_57"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-06-01126-8"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335315"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1137\/070696519"},{"key":"e_1_2_1_41_1","unstructured":"S. Kopparty. 2012. List-decoding multiplicity codes. In Electronic Colloquium on Computational Complexity (ECCC)(TR12-044).  S. Kopparty. 2012. List-decoding multiplicity codes. In Electronic Colloquium on Computational Complexity (ECCC)(TR12-044)."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/625\/12497"},{"key":"e_1_2_1_43_1","volume-title":"High-rate locally-correctable and locally-testable codes with sub-polynomial query complexity. Electronic Colloquium on Computational Complexity (ECCC)","author":"Kopparty Swastik","year":"2015"},{"key":"e_1_2_1_44_1","volume-title":"High-rate locally-testable codes with quasi-polylogarithmic query complexity. Electronic Colloquium on Computational Complexity (ECCC)","author":"Kopparty Swastik","year":"2015"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2629416"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-52282-4_44"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1137\/080729967"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2011.11.007"},{"key":"e_1_2_1_49_1","first-page":"107","article-title":"Locally correctable and testable codes approaching the Singleton bound","volume":"21","author":"Meir Or","year":"2014","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"e_1_2_1_50_1","volume-title":"A note on Yekhanin\u2019s locally decodable codes. Electronic Colloquium on Computational Complexity (ECCC) 14, 016","author":"Raghavendra Prasad","year":"2007"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1137\/0108018"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/1391289.1391291"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.2307\/3062153"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793255151"},{"key":"e_1_2_1_55_1","volume-title":"Originally appeared in Bell System Tech. J. 27:379--423, 623--656","author":"Shannon Claude E.","year":"1948"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1964.1053661"},{"key":"e_1_2_1_57_1","unstructured":"Madhu Sudan. 2001. Algorithmic introduction to coding theory (Lecture notes). Available at http:\/\/people.csail.mit.edu\/madhu\/FT01\/.  Madhu Sudan. 2001. Algorithmic introduction to coding theory (Lecture notes). Available at http:\/\/people.csail.mit.edu\/madhu\/FT01\/."},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1730"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2003.1238187"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1007\/11538462_40"},{"key":"e_1_2_1_61_1","first-page":"739","article-title":"Estimate of the number of signals in error correcting codes","volume":"117","author":"Varshamov R. R.","year":"1957","journal-title":"Dokl. Akad. Nauk"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.43"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2013.34"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20498"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1007\/11523468_115"},{"key":"e_1_2_1_66_1","volume-title":"New lower bounds for general locally decodable codes. Electronic Colloquium on Computational Complexity (ECCC) 14, 006","author":"Woodruff David P.","year":"2007"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/1326554.1326555"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.5555\/2341141"},{"key":"e_1_2_1_69_1","first-page":"3","article-title":"An estimate on the complexity of constructing binary linear cascade codes","volume":"7","author":"Zyablov Victor V.","year":"1971","journal-title":"Probl. Inf. Trans."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3051093","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3051093","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3051093","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:54:38Z","timestamp":1750222478000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3051093"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,4,30]]},"references-count":69,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,4,30]]}},"alternative-id":["10.1145\/3051093"],"URL":"https:\/\/doi.org\/10.1145\/3051093","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,4,30]]},"assertion":[{"value":"2016-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-05-25","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}