{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:32:20Z","timestamp":1750221140049,"version":"3.41.0"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2019,4,26]],"date-time":"2019-04-26T00:00:00Z","timestamp":1556236800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"crossref","award":["671\/13"],"award-info":[{"award-number":["671\/13"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Packard Foundation Fellowship and by an AFOSR","award":["FA9550-15-1-0262"],"award-info":[{"award-number":["FA9550-15-1-0262"]}]},{"name":"I-CORE Program of the Planning and Budgeting Committee, the Israel Science Foundation, and the Citi Foundation"},{"name":"Centre for Discrete Mathematics and its Applications (DIMAP), EPSRC","award":["EP\/D063191\/1. I. K."],"award-info":[{"award-number":["EP\/D063191\/1. I. K."]}]},{"name":"Minerva Foundation with funds from the Federal German Ministry for Education and Research"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2019,9,30]]},"abstract":"<jats:p>\n            Locally testable codes (LTCs) are\n            <jats:italic>error-correcting codes<\/jats:italic>\n            that admit very efficient codeword tests. An LTC is said to be strong if it has a\n            <jats:italic>proximity-oblivious<\/jats:italic>\n            tester, that is, a tester that makes only a\n            <jats:italic>constant number<\/jats:italic>\n            of queries and rejects non-codewords with a probability that depends solely on their distance from the code.\n          <\/jats:p>\n          <jats:p>Locally decodable codes (LDCs) are complementary to LTCs. While the latter allow for highly efficient rejection of strings that are far from being codewords, LDCs allow for highly efficient recovery of individual bits of the information that is encoded in strings that are close to being codewords.<\/jats:p>\n          <jats:p>\n            Constructions of strong-LTCs with nearly-linear length are known, but the existence of a constant-query LDC with\n            <jats:italic>polynomial<\/jats:italic>\n            length is a major open problem. In an attempt to bypass this barrier, Ben-Sasson et al. (SICOMP 2006) introduced a natural relaxation of local decodability, called relaxed-LDCs. This notion requires local recovery of nearly all individual information-bits, yet allows for recovery-failure (but not error) on the rest. Ben-Sasson et al. constructed a constant-query relaxed-LDC with nearly-linear length (i.e., length\n            <jats:italic>k<\/jats:italic>\n            <jats:sup>1+\u03b1<\/jats:sup>\n            for an arbitrarily small constant \u03b1 &gt; 0, where\n            <jats:italic>k<\/jats:italic>\n            is the dimension of the code).\n          <\/jats:p>\n          <jats:p>\n            This work focuses on obtaining strong testability and relaxed decodability\n            <jats:italic>simultaneously<\/jats:italic>\n            . We construct a family of binary linear codes of nearly-linear length that are both strong-LTCs (with one-sided error) and constant-query relaxed-LDCs. This improves upon the previously known constructions, which either obtain only weak LTCs or require polynomial length.\n          <\/jats:p>\n          <jats:p>\n            Our construction heavily relies on\n            <jats:italic>tensor codes<\/jats:italic>\n            and PCPs. In particular, we provide\n            <jats:italic>strong canonical<\/jats:italic>\n            PCPs\n            <jats:italic>of proximity<\/jats:italic>\n            for membership in any linear code with constant rate and relative distance. Loosely speaking, these are PCPs\n            <jats:italic>of proximity<\/jats:italic>\n            wherein the verifier is proximity oblivious (similarly to strong-LTCs) and every valid statement has a unique\n            <jats:italic>canonical<\/jats:italic>\n            proof. Furthermore, the verifier is required to reject non-canonical proofs (even for valid statements).\n          <\/jats:p>\n          <jats:p>\n            As an application, we improve the best known separation result between the complexity of\n            <jats:italic>decision<\/jats:italic>\n            and\n            <jats:italic>verification<\/jats:italic>\n            in the setting of property testing.\n          <\/jats:p>","DOI":"10.1145\/3319907","type":"journal-article","created":{"date-parts":[[2019,4,29]],"date-time":"2019-04-29T17:12:14Z","timestamp":1556557934000},"page":"1-38","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Strong Locally Testable Codes with Relaxed Local Decoders"],"prefix":"10.1145","volume":"11","author":[{"given":"Oded","family":"Goldreich","sequence":"first","affiliation":[{"name":"Weizmann Institute of Science, Rehovot, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tom","family":"Gur","sequence":"additional","affiliation":[{"name":"University of Warwick, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ilan","family":"Komargodski","sequence":"additional","affiliation":[{"name":"Cornell Tech, New York, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,4,26]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705446810"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/1133618.1133623"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-012-0042-8"},{"volume-title":"Proceedings of the 32nd Computational Complexity Conference (CCC\u201917)","author":"Cl\u00e9ment","key":"e_1_2_1_4_1"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/293347.293350"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Irit Dinur and Tali Kaufman. 2011. Dense locally testable codes cannot have constant rate and distance. In APPROX-RANDOM. 507--518.   Irit Dinur and Tali Kaufman. 2011. Dense locally testable codes cannot have constant rate and distance. In APPROX-RANDOM. 507--518.","DOI":"10.1007\/978-3-642-22935-0_43"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705446962"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/090772721"},{"key":"e_1_2_1_9_1","unstructured":"Katalin Friedl and Madhu Sudan. 1995. Some improvements to total degree tests. In ISTCS. 190--198.   Katalin Friedl and Madhu Sudan. 1995. Some improvements to total degree tests. In ISTCS. 190--198."},{"key":"e_1_2_1_10_1","first-page":"72","article-title":"A survey on private information retrieval (Column: Computational Complexity)","volume":"82","author":"Gasarch William I.","year":"2004","journal-title":"Bulletin of the EATCS"},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","unstructured":"Oded Goldreich. 2010. Short locally testable codes and proofs: A survey in two parts. In Property Testing. 65--104.  Oded Goldreich. 2010. Short locally testable codes and proofs: A survey in two parts. In Property Testing. 65--104.","DOI":"10.1007\/978-3-642-16367-8_6"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285060"},{"key":"e_1_2_1_13_1","first-page":"192","article-title":"Universal locally verifiable codes and 3-round interactive proofs of proximity for CSP","volume":"23","author":"Goldreich Oded","year":"2016","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"e_1_2_1_14_1","unstructured":"Oded Goldreich and Tom Gur. 2018. Universal locally testable codes. Chicago J. Theor. Comput. Sci. (2018).  Oded Goldreich and Tom Gur. 2018. Universal locally testable codes. Chicago J. Theor. Comput. Sci. (2018)."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536436"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1162349.1162351"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2422436.2422494"},{"volume-title":"9th Innovations in Theoretical Computer Science Conference, ITCS 2018","year":"2018","author":"Gur Tom","key":"e_1_2_1_18_1"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2688073.2688079"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/11538462_26"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335315"},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","unstructured":"Tali Kaufman and Michael Viderman. 2010. Locally testable vs. locally decodable codes. In APPROX-RANDOM. 670--682.   Tali Kaufman and Michael Viderman. 2010. Locally testable vs. locally decodable codes. In APPROX-RANDOM. 670--682.","DOI":"10.1007\/978-3-642-15369-3_50"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.04.007"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.03.002"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195132"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793255151"},{"volume-title":"Some applications of coding theory in computational complexity. Electronic Colloquium on Computational Complexity (ECCC)","year":"2004","author":"Trevisan Luca","key":"e_1_2_1_27_1"},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","unstructured":"Michael Viderman. 2012. A combination of testability and decodability by tensor products. In APPROX-RANDOM. 651--662.  Michael Viderman. 2012. A combination of testability and decodability by tensor products. In APPROX-RANDOM. 651--662.","DOI":"10.1007\/978-3-642-32512-0_55"},{"key":"e_1_2_1_29_1","first-page":"22","article-title":"Strong LTCs with inverse poly-log rate and constant soundness","volume":"20","author":"Viderman Michael","year":"2013","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11390-012-1254-8"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1326554.1326555"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/2341141"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3319907","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3319907","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:08:06Z","timestamp":1750208886000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3319907"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,4,26]]},"references-count":32,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,9,30]]}},"alternative-id":["10.1145\/3319907"],"URL":"https:\/\/doi.org\/10.1145\/3319907","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2019,4,26]]},"assertion":[{"value":"2017-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-04-26","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}