{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T16:05:27Z","timestamp":1750694727474,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":51,"publisher":"ACM","license":[{"start":{"date-parts":[[2016,6,19]],"date-time":"2016-06-19T00:00:00Z","timestamp":1466294400000},"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":[],"published-print":{"date-parts":[[2016,6,19]]},"DOI":"10.1145\/2897518.2897523","type":"proceedings-article","created":{"date-parts":[[2016,6,10]],"date-time":"2016-06-10T13:04:07Z","timestamp":1465563847000},"page":"202-215","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["High-rate locally-correctable and locally-testable codes with sub-polynomial query complexity"],"prefix":"10.1145","author":[{"given":"Swastik","family":"Kopparty","sequence":"first","affiliation":[{"name":"Rutgers University, USA"}]},{"given":"Or","family":"Meir","sequence":"additional","affiliation":[{"name":"Weizmann Institute of Science, Israel"}]},{"given":"Noga","family":"Ron-Zewi","sequence":"additional","affiliation":[{"name":"Institute for Advanced Study at Princeton, USA \/ Rutgers University, USA"}]},{"given":"Shubhangi","family":"Saraf","sequence":"additional","affiliation":[{"name":"Rutgers University, USA"}]}],"member":"320","published-online":{"date-parts":[[2016,6,19]]},"reference":[{"key":"e_1_3_2_1_1_1","first-page":"519","volume-title":"proceedings of the 36th Annual IEEE Symposium on Foundations of Computer Science (FOCS)","author":"Alon N.","unstructured":"N. Alon , J. Edmonds , and M. Luby . Linear time erasure codes with nearly optimal recovery . In proceedings of the 36th Annual IEEE Symposium on Foundations of Computer Science (FOCS) , pages 512\u2013 519 . IEEE Computer Society, 1995. N. Alon, J. Edmonds, and M. Luby. Linear time erasure codes with nearly optimal recovery. In proceedings of the 36th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 512\u2013519. IEEE Computer Society, 1995."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.556669"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/278298.278306"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/273865.273901"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/103418.103428"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01275486"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.v28:4"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/050646445"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2009.v005a012"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-012-0042-8"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/200836.200880"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90044-W"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/293347.293350"},{"key":"e_1_3_2_1_14_1","volume-title":"On the robust testability of tensor products of codes. Electronic Colloquium on Computational Complexity (ECCC), (104)","author":"Coppersmith D.","year":"2005","unstructured":"D. Coppersmith and A. Rudra . On the robust testability of tensor products of codes. Electronic Colloquium on Computational Complexity (ECCC), (104) , 2005 . D. Coppersmith and A. Rudra. On the robust testability of tensor products of codes. Electronic Colloquium on Computational Complexity (ECCC), (104), 2005."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1236457.1236459"},{"key":"e_1_3_2_1_16_1","first-page":"518","volume-title":"proceedings of the 14th International Workshop on Randomization and Computation (RANDOM)","author":"Dinur I.","unstructured":"I. Dinur and T. Kaufman . Dense locally testable codes cannot have constant rate and distance . In proceedings of the 14th International Workshop on Randomization and Computation (RANDOM) , pages 507\u2013 518 . Springer, 2011. I. Dinur and T. Kaufman. Dense locally testable codes cannot have constant rate and distance. In proceedings of the 14th International Workshop on Randomization and Computation (RANDOM), pages 507\u2013518. Springer, 2011."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/11830924_29"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1966.1053873"},{"key":"e_1_3_2_1_19_1","first-page":"198","volume-title":"proceedings of the 3rd Israel Symposium on the Theory of Computing and Systems (ISTCS)","author":"Friedl K.","unstructured":"K. Friedl and M. Sudan . Some improvements to total degree tests . In proceedings of the 3rd Israel Symposium on the Theory of Computing and Systems (ISTCS) , pages 190\u2013 198 . IEEE Computer Society, 1995. K. Friedl and M. Sudan. Some improvements to total degree tests. In proceedings of the 3rd Israel Symposium on the Theory of Computing and Systems (ISTCS), pages 190\u2013198. IEEE Computer Society, 1995."},{"key":"e_1_3_2_1_20_1","volume-title":"Springer","author":"Goldreich O.","year":"2011","unstructured":"O. Goldreich . Bravely, moderately: a common theme in four recent works. In Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, pages 373\u2013389 . Springer , 2011 . O. Goldreich. Bravely, moderately: a common theme in four recent works. In Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, pages 373\u2013389. Springer, 2011."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2012.01.007"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1162349.1162351"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2422436.2422494"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.510023"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.855587"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2007.911222"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2014.12.013"},{"key":"e_1_3_2_1_28_1","first-page":"712","volume-title":"Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP)","author":"Hemenway B.","unstructured":"B. Hemenway and M. Wootters . Linear-time list recovery of high-rate expander codes . In Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP) , pages 701\u2013 712 . Springer, 2015. B. Hemenway and M. Wootters. Linear-time list recovery of high-rate expander codes. In Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP), pages 701\u2013712. Springer, 2015."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-06-01126-8"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335315"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/625\/12497"},{"key":"e_1_3_2_1_32_1","volume-title":"Electronic Colloquium on Computational Complexity (ECCC)","author":"Kopparty S.","year":"2015","unstructured":"S. Kopparty , O. Meir , N. Ron-Zewi , and S. Saraf . High-rate locally-correctable and locally-testable codes with sub-polynomial query complexity . Electronic Colloquium on Computational Complexity (ECCC) , 2015 . S. Kopparty, O. Meir, N. Ron-Zewi, and S. Saraf. High-rate locally-correctable and locally-testable codes with sub-polynomial query complexity. Electronic Colloquium on Computational Complexity (ECCC), 2015."},{"key":"e_1_3_2_1_33_1","volume-title":"Electronic Colloquium on Computational Complexity (ECCC)","author":"Kopparty S.","year":"2015","unstructured":"S. Kopparty , O. Meir , N. Ron-Zewi , and S. Saraf . High-rate locally-testable codes with quasi-polylogarithmic query complexity . Electronic Colloquium on Computational Complexity (ECCC) , 2015 . S. Kopparty, O. Meir, N. Ron-Zewi, and S. Saraf. High-rate locally-testable codes with quasi-polylogarithmic query complexity. Electronic Colloquium on Computational Complexity (ECCC), 2015."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2629416"},{"key":"e_1_3_2_1_35_1","first-page":"215","volume-title":"proceedings of the 7th Annual ACM Symposium on Theoretical Aspects of Computer Science (STACS)","volume":"415","author":"Lipton R. J.","unstructured":"R. J. Lipton . Efficient checking of computations . In proceedings of the 7th Annual ACM Symposium on Theoretical Aspects of Computer Science (STACS) , volume 415 of lncs, pages 207\u2013 215 . Springer, 1990. R. J. Lipton. Efficient checking of computations. In proceedings of the 7th Annual ACM Symposium on Theoretical Aspects of Computer Science (STACS), volume 415 of lncs, pages 207\u2013215. Springer, 1990."},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/080729967"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2011.11.007"},{"key":"e_1_3_2_1_38_1","volume-title":"Locally correctable and testable codes approaching the singleton bound. Electronic Colloquium on Computational Complexity (ECCC), 21:107","author":"Meir O.","year":"2014","unstructured":"O. Meir . Locally correctable and testable codes approaching the singleton bound. Electronic Colloquium on Computational Complexity (ECCC), 21:107 , 2014 . O. Meir. Locally correctable and testable codes approaching the singleton bound. Electronic Colloquium on Computational Complexity (ECCC), 21:107, 2014."},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1391289.1391291"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.2307\/3062153"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793255151"},{"key":"e_1_3_2_1_42_1","volume-title":"Algorithmic introduction to coding theory (lecture notes)","author":"Sudan M.","year":"2001","unstructured":"M. Sudan . Algorithmic introduction to coding theory (lecture notes) , 2001 . M. Sudan. Algorithmic introduction to coding theory (lecture notes), 2001."},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1730"},{"key":"e_1_3_2_1_44_1","first-page":"135","volume-title":"proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS)","author":"Trevisan L.","unstructured":"L. Trevisan . List-decoding using the XOR lemma . In proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS) , pages 126\u2013 135 . IEEE Computer Society, 2003. L. Trevisan. List-decoding using the XOR lemma. In proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 126\u2013135. IEEE Computer Society, 2003."},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/11538462_40"},{"key":"e_1_3_2_1_46_1","volume-title":"A note on high-rate locally testable codes with sublinear query complexity. Electronic Colloquium on Computational Complexity (ECCC), 17:171","author":"Viderman M.","year":"2010","unstructured":"M. Viderman . A note on high-rate locally testable codes with sublinear query complexity. Electronic Colloquium on Computational Complexity (ECCC), 17:171 , 2010 . M. Viderman. A note on high-rate locally testable codes with sublinear query complexity. Electronic Colloquium on Computational Complexity (ECCC), 17:171, 2010."},{"key":"e_1_3_2_1_47_1","volume-title":"Electronic Colloquium on Computational Complexity (ECCC), 19:168","author":"Viderman M.","year":"2012","unstructured":"M. Viderman . Strong LTCs with inverse polylogarithmic rate and soundness. Electronic Colloquium on Computational Complexity (ECCC), 19:168 , 2012 . M. Viderman. Strong LTCs with inverse polylogarithmic rate and soundness. Electronic Colloquium on Computational Complexity (ECCC), 19:168, 2012."},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.43"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20498"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/11523468_115"},{"key":"e_1_3_2_1_51_1","volume-title":"Electronic Colloquium on Computational Complexity (ECCC), 14(006)","author":"Woodruff D. P.","year":"2007","unstructured":"D. P. Woodruff . New lower bounds for general locally decodable codes. Electronic Colloquium on Computational Complexity (ECCC), 14(006) , 2007 . D. P. Woodruff. New lower bounds for general locally decodable codes. Electronic Colloquium on Computational Complexity (ECCC), 14(006), 2007."}],"event":{"name":"STOC '16: Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Cambridge MA USA","acronym":"STOC '16"},"container-title":["Proceedings of the forty-eighth annual ACM symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2897518.2897523","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2897518.2897523","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:39:02Z","timestamp":1750221542000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2897518.2897523"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,6,19]]},"references-count":51,"alternative-id":["10.1145\/2897518.2897523","10.1145\/2897518"],"URL":"https:\/\/doi.org\/10.1145\/2897518.2897523","relation":{},"subject":[],"published":{"date-parts":[[2016,6,19]]},"assertion":[{"value":"2016-06-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}