{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:15:56Z","timestamp":1763468156695,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":75,"publisher":"ACM","license":[{"start":{"date-parts":[[2013,6,1]],"date-time":"2013-06-01T00:00:00Z","timestamp":1370044800000},"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":[[2013,6]]},"DOI":"10.1145\/2488608.2488714","type":"proceedings-article","created":{"date-parts":[[2013,5,28]],"date-time":"2013-05-28T16:35:41Z","timestamp":1369758941000},"page":"833-842","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["A new family of locally correctable codes based on degree-lifted algebraic geometry codes"],"prefix":"10.1145","author":[{"given":"Eli","family":"Ben-Sasson","sequence":"first","affiliation":[{"name":"Technion, Haifa, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ariel","family":"Gabizon","sequence":"additional","affiliation":[{"name":"Technion, Haifa, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yohay","family":"Kaplan","sequence":"additional","affiliation":[{"name":"Technion, Haifa, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Swastik","family":"Kopparty","sequence":"additional","affiliation":[{"name":"Rutgers, New Brunswick, NJ, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shubangi","family":"Saraf","sequence":"additional","affiliation":[{"name":"rutgers, New Brunswick, NJ, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2013,6]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.856958"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/273865.273901"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-003-0025-0"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/103418.103428"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200430"},{"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.5555\/946243.946356"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/646506.694190"},{"key":"e_1_3_2_1_9_1","volume-title":"Local list decoding with a constant number of queries. Electronic Colloquium on Computational Complexity (ECCC), 17:47","author":"Ben-Aroya A.","year":"2010","unstructured":"A. Ben-Aroya , K. Efremenko , and A. Ta-Shma . Local list decoding with a constant number of queries. Electronic Colloquium on Computational Complexity (ECCC), 17:47 , 2010 . A. Ben-Aroya, K. Efremenko, and A. Ta-Shma. Local list decoding with a constant number of queries. Electronic Colloquium on Computational Complexity (ECCC), 17:47, 2010."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.44"},{"key":"e_1_3_2_1_11_1","volume-title":"On sums of locally testable affine invariant properties. Electronic Colloquium on Computational Complexity (ECCC), 18:79","author":"Ben-Sasson E.","year":"2011","unstructured":"E. Ben-Sasson , E. Grigorescu , G. Maatouk , A. Shpilka , and M. Sudan . On sums of locally testable affine invariant properties. Electronic Colloquium on Computational Complexity (ECCC), 18:79 , 2011 . E. Ben-Sasson, E. Grigorescu, G. Maatouk, A. Shpilka, and M. Sudan. On sums of locally testable affine invariant properties. Electronic Colloquium on Computational Complexity (ECCC), 18:79, 2011."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2009.6"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704445445"},{"key":"e_1_3_2_1_14_1","volume-title":"Symmetric LDPC codes are not necessarily locally testable. In preparation","author":"Ben-Sasson E.","year":"2010","unstructured":"E. Ben-Sasson , G. Maatouk , A. Shpilka , and M. Sudan . Symmetric LDPC codes are not necessarily locally testable. In preparation , 2010 . E. Ben-Sasson, G. Maatouk, A. Shpilka, and M. Sudan. Symmetric LDPC codes are not necessarily locally testable. In preparation, 2010."},{"key":"e_1_3_2_1_15_1","volume-title":"Sparse affine-invariant linear codes are locally testable. Electronic Colloquium on Computational Complexity (ECCC), 19:49","author":"Ben-Sasson E.","year":"2012","unstructured":"E. Ben-Sasson , N. Ron-Zewi , and M. Sudan . Sparse affine-invariant linear codes are locally testable. Electronic Colloquium on Computational Complexity (ECCC), 19:49 , 2012 . E. Ben-Sasson, N. Ron-Zewi, and M. Sudan. Sparse affine-invariant linear codes are locally testable. Electronic Colloquium on Computational Complexity (ECCC), 19:49, 2012."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060631"},{"key":"e_1_3_2_1_17_1","volume-title":"Limits on the rate of locally testable affine-invariant codes. Electronic Colloquium on Computational Complexity (ECCC), 17:108","author":"Ben-Sasson E.","year":"2010","unstructured":"E. Ben-Sasson and M. Sudan . Limits on the rate of locally testable affine-invariant codes. Electronic Colloquium on Computational Complexity (ECCC), 17:108 , 2010 . E. Ben-Sasson and M. Sudan. Limits on the rate of locally testable affine-invariant codes. Electronic Colloquium on Computational Complexity (ECCC), 17:108, 2010."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03685-9_29"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2009.v005a012"},{"key":"e_1_3_2_1_20_1","volume-title":"Query-efficient locally decodable codes of subexponential length. CoRR, abs\/1008.1617","author":"Chee Y. M.","year":"2010","unstructured":"Y. M. Chee , T. Feng , S. Ling , H. Wang , and L. F. Zhang . Query-efficient locally decodable codes of subexponential length. CoRR, abs\/1008.1617 , 2010 . Y. M. Chee, T. Feng, S. Ling, H. Wang, and L. F. Zhang. Query-efficient locally decodable codes of subexponential length. CoRR, abs\/1008.1617, 2010."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/293347.293350"},{"key":"e_1_3_2_1_22_1","volume-title":"On the Robust Testability of Product 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 Product of Codes. Electronic Colloquium on Computational Complexity (ECCC), (104) , 2005 . D. Coppersmith and A. Rudra. On the Robust Testability of Product of Codes. Electronic Colloquium on Computational Complexity (ECCC), (104), 2005."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/872747.873182"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/11830924_29"},{"key":"e_1_3_2_1_25_1","volume-title":"Matching vector codes. Electronic Colloquium on Computational Complexity (ECCC), 17:12","author":"Dvir Z.","year":"2010","unstructured":"Z. Dvir , P. Gopalan , and S. Yekhanin . Matching vector codes. Electronic Colloquium on Computational Complexity (ECCC), 17:12 , 2010 . Z. Dvir, P. Gopalan, and S. Yekhanin. Matching vector codes. Electronic Colloquium on Computational Complexity (ECCC), 17:12, 2010."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536422"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214008"},{"key":"e_1_3_2_1_28_1","volume-title":"Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011","author":"Fortnow L.","year":"2011","unstructured":"L. Fortnow and S. P. Vadhan , editors . Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011 , San Jose, CA, USA, 6- -8 June 2011 . ACM, 2011. L. Fortnow and S. P. Vadhan, editors. Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6--8 June 2011. ACM, 2011."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/527073.881419"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1006\/jnth.1996.0147"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/872747.873181"},{"issue":"4","key":"e_1_3_2_1_32_1","first-page":"762","article-title":"Algebraic-geometric codes","volume":"46","author":"Goppa V.","year":"1982","unstructured":"V. Goppa . Algebraic-geometric codes . Izu. Akad. Nauk SSSR Ser. Mat , 46 ( 4 ): 762 -- 781 , 1982 . V. Goppa. Algebraic-geometric codes. Izu. Akad. Nauk SSSR Ser. Mat, 46(4):762--781, 1982.","journal-title":"Izu. Akad. Nauk SSSR Ser. Mat"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-015-6870-8"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03685-9_40"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2422436.2422494"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1950.tb00463.x"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01810849"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1006\/ffta.2001.0313"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258590"},{"key":"e_1_3_2_1_40_1","volume-title":"Improved constructions for query-efficient locally decodable codes of subexponential length. IEICE Transactions, 93-D(2):263--270","author":"Itoh T.","year":"2010","unstructured":"T. Itoh and Y. Suzuki . Improved constructions for query-efficient locally decodable codes of subexponential length. IEICE Transactions, 93-D(2):263--270 , 2010 . T. Itoh and Y. Suzuki. Improved constructions for query-efficient locally decodable codes of subexponential length. IEICE Transactions, 93-D(2):263--270, 2010."},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335315"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214011"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374434"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"crossref","unstructured":"T.\n      Kaufman\n     and \n      M.\n      Viderman\n  . \n  Locally testable vs. locally decodable codes\n  . In M. J. Serna R. Shaltiel K. Jansen and J. D. P. Rolim editors APPROX-RANDOM volume \n  6302\n   of \n  Lecture Notes in Computer Science pages \n  670\n  --\n  682\n  . \n  Springer 2010\n  .   T. Kaufman and M. Viderman. Locally testable vs. locally decodable codes. In M. J. Serna R. Shaltiel K. Jansen and J. D. P. Rolim editors APPROX-RANDOM volume 6302 of Lecture Notes in Computer Science pages 670--682. Springer 2010.","DOI":"10.1007\/978-3-642-15369-3_50"},{"key":"e_1_3_2_1_45_1","first-page":"406","volume-title":"A. C.-C","author":"Kaufman T.","year":"2010","unstructured":"T. Kaufman and A. Wigderson . Symmetric ldpc codes and local testing . In A. C.-C . Yao, editor, ICS, pages 406 -- 421 . Tsinghua University Press , 2010 . T. Kaufman and A. Wigderson. Symmetric ldpc codes and local testing. In A. C.-C. Yao, editor, ICS, pages 406--421. Tsinghua University Press, 2010."},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.04.007"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993660"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpaa.2004.08.015"},{"key":"e_1_3_2_1_49_1","first-page":"77","volume-title":"Geometry and Coding Theory, Proceedings Luminy","author":"Lachaud G.","year":"1993","unstructured":"G. Lachaud . Number of points of plane sections and linear codes defined on algebraic varieties. Arithmetic , Geometry and Coding Theory, Proceedings Luminy , pages 77 -- 104 , 1993 . G. Lachaud. Number of points of plane sections and linear codes defined on algebraic varieties. Arithmetic, Geometry and Coding Theory, Proceedings Luminy, pages 77--104, 1993."},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.5555\/646506.694191"},{"key":"e_1_3_2_1_51_1","volume-title":"Algebraic geometry codes from higher dimensional varieties. CoRR, abs\/0802.2349","author":"Little J. B.","year":"2008","unstructured":"J. B. Little . Algebraic geometry codes from higher dimensional varieties. CoRR, abs\/0802.2349 , 2008 . J. B. Little. Algebraic geometry codes from higher dimensional varieties. CoRR, abs\/0802.2349, 2008."},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146605"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1002\/mana.19821090103"},{"key":"e_1_3_2_1_54_1","volume-title":"North-Holland Amsterdam","author":"MacWilliams F. J.","year":"1978","unstructured":"F. J. MacWilliams and N. J. A. Sloane . The theory of error-correcting codes . North-Holland Amsterdam , 1978 . F. J. MacWilliams and N. J. A. Sloane. The theory of error-correcting codes. North-Holland Amsterdam, 1978."},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"crossref","unstructured":"K.\n      Obata\n    .\n  Optimal lower bounds for 2-query locally decodable linear codes\n  . In J. D. P. Rolim and S. P. Vadhan editors RANDOM volume \n  2483\n   of \n  Lecture Notes in Computer Science pages \n  39\n  --\n  50\n  . \n  Springer 2002\n  .   K. Obata. Optimal lower bounds for 2-query locally decodable linear codes. In J. D. P. Rolim and S. P. Vadhan editors RANDOM volume 2483 of Lecture Notes in Computer Science pages 39--50. Springer 2002.","DOI":"10.1007\/3-540-45726-7_4"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0087997"},{"key":"e_1_3_2_1_57_1","volume-title":"A note on yekhanin's locally decodable codes. Electronic Colloquium on Computational Complexity (ECCC), 14(016)","author":"Raghavendra P.","year":"2007","unstructured":"P. Raghavendra . A note on yekhanin's locally decodable codes. Electronic Colloquium on Computational Complexity (ECCC), 14(016) , 2007 . P. Raghavendra. A note on yekhanin's locally decodable codes. Electronic Colloquium on Computational Complexity (ECCC), 14(016), 2007."},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2007.v003a012"},{"key":"e_1_3_2_1_59_1","article-title":"A class of multiple-error-correcting codes and the decoding scheme","author":"Reed I. S.","year":"1954","unstructured":"I. S. Reed . A class of multiple-error-correcting codes and the decoding scheme . IEEE Transactions on Information Theory, (4):38--49 , 1954 . I. S. Reed. A class of multiple-error-correcting codes and the decoding scheme. IEEE Transactions on Information Theory, (4):38--49, 1954.","journal-title":"IEEE Transactions on Information Theory, (4):38--49"},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-4049(02)00188-3"},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/1059513.1059516"},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146609"},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1948.tb01338.x"},{"key":"e_1_3_2_1_64_1","first-page":"44","article-title":"exposition of fundamentals","volume":"1","author":"Shannon C. E.","year":"1953","unstructured":"C. E. Shannon . Communication theory - exposition of fundamentals . IEEE Transactions on Information Theory , 1 : 44 -- 47 , 1953 . C. E. Shannon. Communication theory - exposition of fundamentals. IEEE Transactions on Information Theory, 1:44--47, 1953.","journal-title":"IEEE Transactions on Information Theory"},{"key":"e_1_3_2_1_65_1","doi-asserted-by":"crossref","unstructured":"H. Stichtenoth. On automorphisms of geometric goppa codes. Journal of Algebra page 113.  H. Stichtenoth. On automorphisms of geometric goppa codes. Journal of Algebra page 113.","DOI":"10.1016\/0021-8693(90)90104-V"},{"key":"e_1_3_2_1_66_1","volume-title":"Universitext. Springer","author":"Stichtenoth H.","year":"1993","unstructured":"H. Stichtenoth . Algebraic function fields and codes . Universitext. Springer , 1993 . H. Stichtenoth. Algebraic function fields and codes. Universitext. Springer, 1993."},{"key":"e_1_3_2_1_67_1","volume-title":"Invariance in property testing. Electronic Colloquium on Computational Complexity (ECCC), (051)","author":"Sudan M.","year":"2010","unstructured":"M. Sudan . Invariance in property testing. Electronic Colloquium on Computational Complexity (ECCC), (051) , 2010 . M. Sudan. Invariance in property testing. Electronic Colloquium on Computational Complexity (ECCC), (051), 2010."},{"key":"e_1_3_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1145\/301250.301397"},{"key":"e_1_3_2_1_69_1","doi-asserted-by":"crossref","DOI":"10.1007\/978-94-011-3810-9","volume-title":"Algebraic-geometric codes","author":"Tsfasman M.","year":"1991","unstructured":"M. Tsfasman and S.G. Vladut . Algebraic-geometric codes . ( Kluwer , Dordrecht , 1991 . M. Tsfasman and S.G.Vladut. Algebraic-geometric codes. (Kluwer, Dordrecht, 1991."},{"key":"e_1_3_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1007\/11538462_40"},{"key":"e_1_3_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1007\/11523468_115"},{"key":"e_1_3_2_1_72_1","volume-title":"New lower bounds for general locally decodable codes. 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."},{"key":"e_1_3_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.476234"},{"key":"e_1_3_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1145\/1326554.1326555"},{"key":"e_1_3_2_1_75_1","doi-asserted-by":"crossref","unstructured":"S.\n      Yekhanin\n    . \n      Locally\n     decodable codes\n  : \n  A brief survey\n  . In Y. M. Chee Z. Guo S. Ling F. Shao Y. Tang H. Wang and C. Xing editors IWCC volume \n  6639\n   of \n  Lecture Notes in Computer Science pages \n  273\n  --\n  282\n  . \n  Springer 2011\n  .   S. Yekhanin. Locally decodable codes: A brief survey. In Y. M. Chee Z. Guo S. Ling F. Shao Y. Tang H. Wang and C. Xing editors IWCC volume 6639 of Lecture Notes in Computer Science pages 273--282. Springer 2011.","DOI":"10.1007\/978-3-642-20901-7_18"}],"event":{"name":"STOC'13: Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Palo Alto California USA","acronym":"STOC'13"},"container-title":["Proceedings of the forty-fifth annual ACM symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2488608.2488714","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2488608.2488714","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:39:21Z","timestamp":1750235961000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2488608.2488714"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,6]]},"references-count":75,"alternative-id":["10.1145\/2488608.2488714","10.1145\/2488608"],"URL":"https:\/\/doi.org\/10.1145\/2488608.2488714","relation":{},"subject":[],"published":{"date-parts":[[2013,6]]},"assertion":[{"value":"2013-06-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}