{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,19]],"date-time":"2026-02-19T07:23:42Z","timestamp":1771485822188,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":67,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,6,9]],"date-time":"2022-06-09T00:00:00Z","timestamp":1654732800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,6,9]]},"DOI":"10.1145\/3519935.3520024","type":"proceedings-article","created":{"date-parts":[[2022,6,10]],"date-time":"2022-06-10T15:29:32Z","timestamp":1654874972000},"page":"357-374","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":47,"title":["Locally testable codes with constant rate, distance, and locality"],"prefix":"10.1145","author":[{"given":"Irit","family":"Dinur","sequence":"first","affiliation":[{"name":"Weizmann Institute of Science, Israel"}]},{"given":"Shai","family":"Evra","sequence":"additional","affiliation":[{"name":"Hebrew University of Jerusalem, Israel"}]},{"given":"Ron","family":"Livne","sequence":"additional","affiliation":[{"name":"Hebrew University of Jerusalem, Israel"}]},{"given":"Alexander","family":"Lubotzky","sequence":"additional","affiliation":[{"name":"Weizmann Institute of Science, Israel"}]},{"given":"Shahar","family":"Mozes","sequence":"additional","affiliation":[{"name":"Hebrew University of Jerusalem, Israel"}]}],"member":"320","published-online":{"date-parts":[[2022,6,10]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(88)90189-6"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1995.492581"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316385"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/278298.278306"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/273865.273901"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/103418.103428"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200056"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.851735"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705446810"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/090779875"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704445445"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060631"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20120"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/050646445"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780631"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2009.v005a012"},{"key":"e_1_3_2_1_18_1","volume-title":"Towards lower bounds on locally testable codes via density arguments. computational complexity, 21, 2","author":"Ben-Sasson Eli","year":"2012","unstructured":"Eli Ben-Sasson and Michael Viderman . 2012. Towards lower bounds on locally testable codes via density arguments. computational complexity, 21, 2 ( 2012 ), 267\u2013309. Eli Ben-Sasson and Michael Viderman. 2012. Towards lower bounds on locally testable codes via density arguments. computational complexity, 21, 2 (2012), 267\u2013309."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/100216.100225"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2021.3097347"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02762271"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.APPROX-RANDOM.2018.38"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1236457.1236459"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"crossref","unstructured":"Irit Dinur. 2021. Breakthroughs in computer science: Locally Testable Codes with Constant Rate Distance and Locality. https:\/\/simons.berkeley.edu\/events\/breakthroughs-locally-testable-codes-constant-rate-distance-and-locality.  Irit Dinur. 2021. Breakthroughs in computer science: Locally Testable Codes with Constant Rate Distance and Locality. https:\/\/simons.berkeley.edu\/events\/breakthroughs-locally-testable-codes-constant-rate-distance-and-locality.","DOI":"10.1145\/3519935.3520024"},{"key":"e_1_3_2_1_25_1","unstructured":"Irit Dinur. 2021. Locally Testable Codes with Constant Rate Distance and Locality. Part I: https:\/\/youtu.be\/pz2-bEopa-c Part II: https:\/\/youtu.be\/Ydb2OPQ7eqI.  Irit Dinur. 2021. Locally Testable Codes with Constant Rate Distance and Locality. Part I: https:\/\/youtu.be\/pz2-bEopa-c Part II: https:\/\/youtu.be\/Ydb2OPQ7eqI."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.8"},{"key":"e_1_3_2_1_27_1","volume-title":"APPROX 2011, and 15th International Workshop, RANDOM 2011, Princeton, NJ, USA, August 17-19, 2011. Proceedings. 507\u2013518","author":"Dinur Irit","year":"2011","unstructured":"Irit Dinur and Tali Kaufman . 2011 . Dense Locally Testable Codes Cannot Have Constant Rate and Distance. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 14th International Workshop , APPROX 2011, and 15th International Workshop, RANDOM 2011, Princeton, NJ, USA, August 17-19, 2011. Proceedings. 507\u2013518 . Irit Dinur and Tali Kaufman. 2011. Dense Locally Testable Codes Cannot Have Constant Rate and Distance. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 14th International Workshop, APPROX 2011, and 15th International Workshop, RANDOM 2011, Princeton, NJ, USA, August 17-19, 2011. Proceedings. 507\u2013518."},{"key":"e_1_3_2_1_28_1","unstructured":"Irit Dinur and Tali Kaufman. 2017. Agreement Expansion. Work in progress.  Irit Dinur and Tali Kaufman. 2017. Agreement Expansion. Work in progress."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/11830924_29"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897543"},{"key":"e_1_3_2_1_31_1","volume-title":"Some Improvements to Total Degree Tests. CoRR, abs\/1307.3975","author":"Friedl Katalin","year":"2013","unstructured":"Katalin Friedl and Madhu Sudan . 2013. Some Improvements to Total Degree Tests. CoRR, abs\/1307.3975 ( 2013 ), arxiv:1307.3975 Katalin Friedl and Madhu Sudan. 2013. Some Improvements to Total Degree Tests. CoRR, abs\/1307.3975 (2013), arxiv:1307.3975"},{"key":"e_1_3_2_1_32_1","volume-title":"Low density parity check codes","author":"Gallager Robert G.","unstructured":"Robert G. Gallager . 1963. Low density parity check codes . MIT Press , Cambridge, Massachusetts . Robert G. Gallager. 1963. Low density parity check codes. MIT Press, Cambridge, Massachusetts."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.2307\/1970829"},{"key":"e_1_3_2_1_34_1","volume-title":"A comparison of signalling alphabets. The Bell system technical journal, 31, 3","author":"Gilbert Edgar N","year":"1952","unstructured":"Edgar N Gilbert . 1952. A comparison of signalling alphabets. The Bell system technical journal, 31, 3 ( 1952 ), 504\u2013522. Edgar N Gilbert. 1952. A comparison of signalling alphabets. The Bell system technical journal, 31, 3 (1952), 504\u2013522."},{"key":"e_1_3_2_1_36_1","volume-title":"Springer Berlin Heidelberg","author":"Goldreich Oded","unstructured":"Oded Goldreich . 2010. Springer Berlin Heidelberg , Berlin, Heidelberg . 65\u2013104. Oded Goldreich. 2010. Springer Berlin Heidelberg, Berlin, Heidelberg. 65\u2013104."},{"key":"e_1_3_2_1_37_1","volume-title":"Introduction to Property Testing","author":"Goldreich Oded","unstructured":"Oded Goldreich . 2017. Introduction to Property Testing . Cambridge University Press . Oded Goldreich. 2017. Introduction to Property Testing. Cambridge University Press."},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2012.01.007"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1162349.1162351"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2018.2809788"},{"key":"e_1_3_2_1_41_1","first-page":"85","article-title":"The Ramanujan property for regular cubical complexes","volume":"105","author":"Jordan Bruce","year":"1999","unstructured":"Bruce Jordan and Ron Livne . 1999 . The Ramanujan property for regular cubical complexes . Duke Mathematical Journal , 105 (1999), 85 \u2013 103 . Bruce Jordan and Ron Livne. 1999. The Ramanujan property for regular cubical complexes. Duke Mathematical Journal, 105 (1999), 85\u2013103.","journal-title":"Duke Mathematical Journal"},{"key":"e_1_3_2_1_42_1","volume-title":"Ramanujan Complexes and Bounded Degree Topological Expanders. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014","author":"Kaufman Tali","year":"2014","unstructured":"Tali Kaufman , David Kazhdan , and Alexander Lubotzky . 2014 . Ramanujan Complexes and Bounded Degree Topological Expanders. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014 , Philadelphia, PA, USA , October 18-21, 2014. 484\u2013493. Tali Kaufman, David Kazhdan, and Alexander Lubotzky. 2014. Ramanujan Complexes and Bounded Degree Topological Expanders. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014. 484\u2013493."},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214011"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2554797.2554842"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3051093"},{"key":"e_1_3_2_1_46_1","volume-title":"The Theory of Groups","author":"Kurosh Aleksandr Gennadievich","unstructured":"Aleksandr Gennadievich Kurosh . 1955. The Theory of Groups , vol. 2 . Chelsea publishing company, New York . Aleksandr Gennadievich Kurosh. 1955. The Theory of Groups, vol. 2. Chelsea publishing company, New York."},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-0346-0332-4"},{"key":"e_1_3_2_1_48_1","unstructured":"Alexander Lubotzky. 2021. The C^3 Problem: Locally Testable Codes with Constant Rate and Constant Distance. https:\/\/www.simonsfoundation.org\/event\/2021-mps-conference-on-high-dimensional-expanders\/ MPS Conference on High-Dimensional Expanders.  Alexander Lubotzky. 2021. The C^3 Problem: Locally Testable Codes with Constant Rate and Constant Distance. https:\/\/www.simonsfoundation.org\/event\/2021-mps-conference-on-high-dimensional-expanders\/ MPS Conference on High-Dimensional Expanders."},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1112\/blms\/bdm003"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02126799"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2004.06.007"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02772543"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146605"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374419"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1994.1054"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/135\/1185097"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.2307\/2373947"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-017-9948-x"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"crossref","unstructured":"Pavel Panteleev and Gleb Kalachev. 2021. Asymptotically Good Quantum and Locally Testable Classical LDPC Codes. arxiv:2111.03654.  Pavel Panteleev and Gleb Kalachev. 2021. Asymptotically Good Quantum and Locally Testable Classical LDPC Codes. arxiv:2111.03654.","DOI":"10.1145\/3519935.3520017"},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2021.3119384"},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195132"},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793255151"},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.556667"},{"key":"e_1_3_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.556668"},{"key":"e_1_3_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1981.1056404"},{"key":"e_1_3_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1983.1056765"},{"key":"e_1_3_2_1_67_1","doi-asserted-by":"crossref","unstructured":"Paul Valiant. 2005. The Tensor Product of Two Codes Is Not Necessarily Robustly Testable. In APPROX-RANDOM. 472\u2013481.  Paul Valiant. 2005. The Tensor Product of Two Codes Is Not Necessarily Robustly Testable. In APPROX-RANDOM. 472\u2013481.","DOI":"10.1007\/11538462_40"},{"key":"e_1_3_2_1_68_1","first-page":"739","article-title":"Estimate of the number of signals in error correcting codes","volume":"117","author":"Varshamov Rom Rubenovich","year":"1957","unstructured":"Rom Rubenovich Varshamov . 1957 . Estimate of the number of signals in error correcting codes . Docklady Akad. Nauk, SSSR , 117 (1957), 739 \u2013 741 . Rom Rubenovich Varshamov. 1957. Estimate of the number of signals in error correcting codes. Docklady Akad. Nauk, SSSR, 117 (1957), 739\u2013741.","journal-title":"Docklady Akad. Nauk, SSSR"},{"key":"e_1_3_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02698861"}],"event":{"name":"STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing","location":"Rome Italy","acronym":"STOC '22","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519935.3520024","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3519935.3520024","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:31:15Z","timestamp":1750188675000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519935.3520024"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,9]]},"references-count":67,"alternative-id":["10.1145\/3519935.3520024","10.1145\/3519935"],"URL":"https:\/\/doi.org\/10.1145\/3519935.3520024","relation":{},"subject":[],"published":{"date-parts":[[2022,6,9]]},"assertion":[{"value":"2022-06-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}