{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,15]],"date-time":"2026-04-15T20:28:32Z","timestamp":1776284912956,"version":"3.50.1"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2008,2,1]],"date-time":"2008-02-01T00:00:00Z","timestamp":1201824000000},"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":["J. ACM"],"published-print":{"date-parts":[[2008,2]]},"abstract":"<jats:p>\n            A\n            <jats:italic>q<\/jats:italic>\n            -query Locally Decodable Code (LDC) encodes an\n            <jats:italic>n<\/jats:italic>\n            -bit message\n            <jats:italic>x<\/jats:italic>\n            as an\n            <jats:italic>N<\/jats:italic>\n            -bit codeword\n            <jats:italic>C<\/jats:italic>\n            (\n            <jats:italic>x<\/jats:italic>\n            ), such that one can probabilistically recover any bit\n            <jats:italic>\n              x\n              <jats:sub>i<\/jats:sub>\n            <\/jats:italic>\n            of the message by querying only\n            <jats:italic>q<\/jats:italic>\n            bits of the codeword\n            <jats:italic>C<\/jats:italic>\n            (\n            <jats:italic>x<\/jats:italic>\n            ), even after some constant fraction of codeword bits has been corrupted.\n          <\/jats:p>\n          <jats:p>\n            We give new constructions of three query LDCs of vastly shorter length than that of previous constructions. Specifically, given any Mersenne prime\n            <jats:italic>p<\/jats:italic>\n            = 2\n            <jats:sup>\n              <jats:italic>t<\/jats:italic>\n            <\/jats:sup>\n            \u2212 1, we design three query LDCs of length\n            <jats:italic>N<\/jats:italic>\n            = exp(\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              1\/\n              <jats:italic>t<\/jats:italic>\n            <\/jats:sup>\n            )), for every\n            <jats:italic>n<\/jats:italic>\n            . Based on the largest known Mersenne prime, this translates to a length of less than exp(\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              10\n              <jats:sup>\u2212 7<\/jats:sup>\n            <\/jats:sup>\n            )) compared to exp(\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>1\/2<\/jats:sup>\n            )) in the previous constructions. It has often been conjectured that there are infinitely many Mersenne primes. Under this conjecture, our constructions yield three query locally decodable codes of length\n            <jats:italic>N<\/jats:italic>\n            = exp(\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              <jats:italic>O<\/jats:italic>\n              (1\/log log\n              <jats:italic>n<\/jats:italic>\n              )\n            <\/jats:sup>\n            ) for infinitely many\n            <jats:italic>n<\/jats:italic>\n            .\n          <\/jats:p>\n          <jats:p>\n            We also obtain analogous improvements for Private Information Retrieval (PIR) schemes. We give 3-server PIR schemes with communication complexity of\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              10\n              <jats:sup>\u2212 7<\/jats:sup>\n            <\/jats:sup>\n            ) to access an\n            <jats:italic>n<\/jats:italic>\n            -bit database, compared to the previous best scheme with complexity\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>1\/5.25<\/jats:sup>\n            ). Assuming again that there are infinitely many Mersenne primes, we get 3-server PIR schemes of communication complexity\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              <jats:italic>O<\/jats:italic>\n              (1\/log log\n              <jats:italic>n<\/jats:italic>\n              )\n            <\/jats:sup>\n            ) for infinitely many\n            <jats:italic>n<\/jats:italic>\n            .\n          <\/jats:p>\n          <jats:p>Previous families of LDCs and PIR schemes were based on the properties of low-degree multivariate polynomials over finite fields. Our constructions are completely different and are obtained by constructing a large number of vectors in a small dimensional vector space whose inner products are restricted to lie in an algebraically nice set.<\/jats:p>","DOI":"10.1145\/1326554.1326555","type":"journal-article","created":{"date-parts":[[2008,2,28]],"date-time":"2008-02-28T14:02:33Z","timestamp":1204207353000},"page":"1-16","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":149,"title":["Towards 3-query locally decodable codes of subexponential length"],"prefix":"10.1145","volume":"55","author":[{"given":"Sergey","family":"Yekhanin","sequence":"first","affiliation":[{"name":"MIT, Cambridge, Massachusetts"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2008,2,22]]},"reference":[{"key":"e_1_2_1_1_1","series-title":"Lecture Notes in Computer Science","first-page":"401","volume-title":"Proceedings of the 32nd Annual International Colloquium on Antomata, Languages and Programming","author":"Ambainis A.","unstructured":"Ambainis , A. 1997. Upper bound on the communication complexity of private information retrieval . In Proceedings of the 32nd Annual International Colloquium on Antomata, Languages and Programming . Lecture Notes in Computer Science , vol. 1256 , Springer-Verlag , New York , pp. 401 -- 407 . Ambainis, A. 1997. Upper bound on the communication complexity of private information retrieval. In Proceedings of the 32nd Annual International Colloquium on Antomata, Languages and Programming. Lecture Notes in Computer Science, vol. 1256, Springer-Verlag, New York, pp. 401--407."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/103418.103428"},{"key":"e_1_2_1_3_1","unstructured":"Babai L. and Frankl P. 1998. Linear algebra methods in combinatorics.  Babai L. and Frankl P. 1998. Linear algebra methods in combinatorics."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-006-0208-3"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2005.03.002"},{"key":"e_1_2_1_6_1","first-page":"261","volume-title":"Proceedings of the 43rd IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press","author":"Beimel A.","unstructured":"Beimel , A. , Ishai , Y. , Kushilevitz , E. , and Raymond , J. F . 2002. Breaking the O(n 1\/(2k &minus; 1)) barrier for information-theoretic private information retrieval . In Proceedings of the 43rd IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press , Los Alamitos, CA , pp. 261 -- 270 . Beimel, A., Ishai, Y., Kushilevitz, E., and Raymond, J. F. 2002. Breaking the O(n 1\/(2k &minus; 1)) barrier for information-theoretic private information retrieval. In Proceedings of the 43rd IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press, Los Alamitos, CA, pp. 261--270."},{"key":"e_1_2_1_7_1","first-page":"41","volume-title":"Proceedings of the 36rd IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press","author":"Chor B.","year":"1998","unstructured":"Chor , B. , Goldreich , O. , Kushilevitz , E. , and Sudan , M . 1995. Private information retrieval . In Proceedings of the 36rd IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press , Los Alamitos, CA , pp. 41 -- 50 . (Also, in J. ACM 45, 1998 ). Chor, B., Goldreich, O., Kushilevitz, E., and Sudan, M. 1995. Private information retrieval. In Proceedings of the 36rd IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press, Los Alamitos, CA, pp. 41--50. (Also, in J. ACM 45, 1998)."},{"key":"e_1_2_1_8_1","first-page":"184","volume-title":"Proceedings of the 20th IEEE Computational Complexity Conference (CCC). IEEE Computer Society Press","author":"Deshpande A.","unstructured":"Deshpande , A. , Jain , R. , Kavitha , T. , Lokam , S. , and Radhakrishnan , J . 2002. Better lower bounds for locally decodable codes . In Proceedings of the 20th IEEE Computational Complexity Conference (CCC). IEEE Computer Society Press , Los Alamitos, CA , pp. 184 -- 193 . Deshpande, A., Jain, R., Kavitha, T., Lokam, S., and Radhakrishnan, J. 2002. Better lower bounds for locally decodable codes. In Proceedings of the 20th IEEE Computational Complexity Conference (CCC). IEEE Computer Society Press, Los Alamitos, CA, pp. 184--193."},{"key":"e_1_2_1_9_1","unstructured":"Cooper C. and Boone S. 2006. http:\/\/www.mersenne.org\/32582657.htm.  Cooper C. and Boone S. 2006. http:\/\/www.mersenne.org\/32582657.htm."},{"key":"e_1_2_1_10_1","first-page":"72","article-title":"A survey on private information retrieval","volume":"82","author":"Gasarch W.","year":"2004","unstructured":"Gasarch , W. 2004 . A survey on private information retrieval . Bull. EATCS 82 , 72 -- 107 . Gasarch, W. 2004. A survey on private information retrieval. Bull. EATCS 82, 72--107.","journal-title":"Bull. EATCS"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the Electronic Colloquim on Computational Complexity (ECCC).","author":"Goldreich O.","year":"2005","unstructured":"Goldreich , O. 2005 . Short locally testable codes and proofs. Tech. Rep. TR05-014 . In Proceedings of the Electronic Colloquim on Computational Complexity (ECCC). Goldreich, O. 2005. Short locally testable codes and proofs. Tech. Rep. TR05-014. In Proceedings of the Electronic Colloquim on Computational Complexity (ECCC)."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-006-0216-3"},{"key":"e_1_2_1_13_1","first-page":"11","article-title":"Efficient private information retrieval. IEICE","volume":"1","author":"Itoh T.","year":"1999","unstructured":"Itoh , T. 1999 . Efficient private information retrieval. IEICE Trans. Fund. Electron. Commun. Comput. Sci. E82-A , 1 , 11 -- 20 . Itoh, T. 1999. Efficient private information retrieval. IEICE Trans. Fund. Electron. Commun. Comput. Sci. E82-A, 1, 11--20.","journal-title":"Trans. Fund. Electron. Commun. Comput. Sci. E82-A"},{"key":"e_1_2_1_14_1","article-title":"On lower bounds for the communication complexity of private information retrieval. IEICE","author":"Itoh T.","year":"2001","unstructured":"Itoh , T. 2001 . On lower bounds for the communication complexity of private information retrieval. IEICE Trans. Fund. Electron. Commun. Comput. Sci. E84-A1, 157--164. Itoh, T. 2001. On lower bounds for the communication complexity of private information retrieval. IEICE Trans. Fund. Electron. Commun. Comput. Sci. E84-A1, 157--164.","journal-title":"Trans. Fund. Electron. Commun. Comput. Sci. E84-A1, 157--164."},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the Electronic Colloquium on Computational Complexity, Tech. rep. TR07-040","author":"Kedlaya K.","unstructured":"Kedlaya , K. , and Yekhanin , S . 2007. Locally decodable codes from nice subsets of finite fields and prime factors of Mersenne numbers . In Proceedings of the Electronic Colloquium on Computational Complexity, Tech. rep. TR07-040 . Kedlaya, K., and Yekhanin, S. 2007. Locally decodable codes from nice subsets of finite fields and prime factors of Mersenne numbers. In Proceedings of the Electronic Colloquium on Computational Complexity, Tech. rep. TR07-040."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335315"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.04.007"},{"key":"e_1_2_1_18_1","volume-title":"Studieweek Getaltheorie en Computers (Sept. 1--5). Stichting Math., Centrum","author":"Lenstra Jr., H. W.","unstructured":"Lenstra , Jr., H. W. 1980. Primarlity testing . In Studieweek Getaltheorie en Computers (Sept. 1--5). Stichting Math., Centrum , Amsterdam, The Netherlands . Lenstra, Jr., H. W. 1980. Primarlity testing. In Studieweek Getaltheorie en Computers (Sept. 1--5). Stichting Math., Centrum, Amsterdam, The Netherlands."},{"key":"e_1_2_1_19_1","unstructured":"Lidl R. and Niederreiter H. 1983. Finite Fields. Cambridge University Press Cambridge MA.  Lidl R. and Niederreiter H. 1983. Finite Fields. Cambridge University Press Cambridge MA."},{"key":"e_1_2_1_20_1","unstructured":"Mann E. 1998. Private access to distributed information. Master's thesis Technion - Israel Institute of Technology Haifa Israel.  Mann E. 1998. Private access to distributed information. Master's thesis Technion - Israel Institute of Technology Haifa Israel."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/646978.711825"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195132"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF03022861"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.10"},{"key":"e_1_2_1_26_1","first-page":"347","article-title":"Some applications of coding theory in computational complexity","volume":"13","author":"Trevisan L.","year":"2004","unstructured":"Trevisan , L. 2004 . Some applications of coding theory in computational complexity . Quad. Matemat. 13 , 347 -- 424 . Trevisan, L. 2004. Some applications of coding theory in computational complexity. Quad. Matemat. 13, 347--424.","journal-title":"Quad. Matemat."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/11523468_115"},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","unstructured":"Wagstaff S. 1983. Divisors of Mersenne numbers. Math. Comput. 40 161 385--397.  Wagstaff S. 1983. Divisors of Mersenne numbers. Math. Comput. 40 161 385--397.","DOI":"10.1090\/S0025-5718-1983-0679454-X"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the Electronic Colloquium on Computational Complexity, Tech. rep. TR07-006","author":"Woodruff D.","year":"2007","unstructured":"Woodruff , D. 2007 . New lower bounds for general locally decodable codes . In Proceedings of the Electronic Colloquium on Computational Complexity, Tech. rep. TR07-006 . Woodruff, D. 2007. New lower bounds for general locally decodable codes. In Proceedings of the Electronic Colloquium on Computational Complexity, Tech. rep. TR07-006."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/06065773X"},{"key":"e_1_2_1_31_1","unstructured":"Yekhanin S. 2006. New locally decodable codes and private infromation retrieval schemes. In Electronic Colloquium on Computational Complexity Tech. rep. TR06-127.  Yekhanin S. 2006. New locally decodable codes and private infromation retrieval schemes. In Electronic Colloquium on Computational Complexity Tech. rep. TR06-127."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1326554.1326555","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1326554.1326555","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:56:25Z","timestamp":1750254985000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1326554.1326555"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,2]]},"references-count":30,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2008,2]]}},"alternative-id":["10.1145\/1326554.1326555"],"URL":"https:\/\/doi.org\/10.1145\/1326554.1326555","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,2]]},"assertion":[{"value":"2007-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2007-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-02-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}