{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,21]],"date-time":"2025-12-21T01:36:47Z","timestamp":1766281007062,"version":"3.38.0"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2011,8,4]],"date-time":"2011-08-04T00:00:00Z","timestamp":1312416000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2013,3]]},"DOI":"10.1007\/s00037-011-0017-1","type":"journal-article","created":{"date-parts":[[2011,8,3]],"date-time":"2011-08-03T19:16:17Z","timestamp":1312398977000},"page":"159-189","source":"Crossref","is-referenced-by-count":29,"title":["Query-Efficient Locally Decodable Codes of Subexponential Length"],"prefix":"10.1007","volume":"22","author":[{"given":"Yeow Meng","family":"Chee","sequence":"first","affiliation":[]},{"given":"Tao","family":"Feng","sequence":"additional","affiliation":[]},{"given":"San","family":"Ling","sequence":"additional","affiliation":[]},{"given":"Huaxiong","family":"Wang","sequence":"additional","affiliation":[]},{"given":"Liang Feng","family":"Zhang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2011,8,4]]},"reference":[{"key":"17_CR1","doi-asserted-by":"crossref","unstructured":"A. Ambainis (1997). Upper bound on the communication complexity of private information retrieval. In ICALP \u201997: Proccedings of the 24th International Colloquium on Automata, Languages and Programming, volume 1256 of Lecture Notes in Comput. Sci., 401\u2013407. Springer, Berlin.","DOI":"10.1007\/3-540-63165-8_196"},{"issue":"2","key":"17_CR2","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1016\/j.jcss.2005.03.002","volume":"71","author":"A. Beimel","year":"2005","unstructured":"Beimel A., Ishai Y., Kushilevitz E. (2005) General constructions for information-theoretic private information retrieval. J. Comput. System Sci. 71(2): 213\u2013247","journal-title":"J. Comput. System Sci."},{"key":"17_CR3","doi-asserted-by":"crossref","unstructured":"A. Beimel, Y. Ishai, E. Kushilevitz & J.-F. Raymond (2002) Breaking the $${O(n^\\frac{1}{2k-1})}$$ barrier for information-theoretic private information retrieval. In FOCS \u201902: Proceedings of the 43rd Symposium on Foundations of Computer Science, 261\u2013270. IEEE Computer Society, Washington, DC, USA.","DOI":"10.1109\/SFCS.2002.1181949"},{"issue":"6","key":"17_CR4","doi-asserted-by":"crossref","first-page":"965","DOI":"10.1145\/293347.293350","volume":"45","author":"B. Chor","year":"1998","unstructured":"Chor B., Goldreich O., Kushilevitz E., Sudan M. (1998) Private information retrieval. J. ACM 45(6): 965\u2013982","journal-title":"J. ACM"},{"key":"17_CR5","unstructured":"Curtis C.W. & I. Reiner (2006). Representation Theory of Finite Groups and Associative Algebras. AMS Chelsea Publishing, Providence, RI, xiv+689."},{"key":"17_CR6","unstructured":"A. Deshpande, R. Jain, T. Kavitha, J. Radhakrishnan & S. V. Lokam (2002). Better Lower Bounds for Locally Decodable Codes. In CCC \u201902: Proceedings of the 17th IEEE Annual Conference on Computational Complexity, 184. IEEE Computer Society, Washington, DC, USA."},{"key":"17_CR7","unstructured":"Z. Dvir & A. Shpilka (2005). Locally decodable codes with 2 queries and polynomial identity testing for depth 3 circuits. In STOC \u201905: Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 592\u2013601. ACM, New York."},{"key":"17_CR8","doi-asserted-by":"crossref","unstructured":"K. Efremenko (2009). 3-query locally decodable codes of subexponential length. In STOC \u201909: Proceedings of the 41st annual ACM symposium on Theory of computing, 39\u201344. ACM, New York.","DOI":"10.1145\/1536414.1536422"},{"key":"17_CR9","first-page":"72","volume":"82","author":"W. Gasarch","year":"2004","unstructured":"Gasarch W. (2004) A survey on private information retrieval. Bull. Eur. Assoc. Theor. Comput. Sci. EATCS 82: 72\u2013107","journal-title":"Bull. Eur. Assoc. Theor. Comput. Sci. EATCS"},{"issue":"3","key":"17_CR10","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1007\/s00037-006-0216-3","volume":"15","author":"O. Goldreich","year":"2006","unstructured":"Goldreich O., Karloff H., Schulman L.J., Trevisan L. (2006) Lower bounds for linear locally decodable codes and private information retrieval. Comput. Complexity 15(3): 263\u2013296","journal-title":"Comput. Complexity"},{"key":"17_CR11","unstructured":"P. Gopalan (2009). A note on Efremenko\u2019s locally decodable codes. Electronic Colloquium on Computational Complexity (ECCC) TR09-069."},{"issue":"1","key":"17_CR12","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1007\/s004930070032","volume":"20","author":"V. Grolmusz","year":"2000","unstructured":"Grolmusz V. (2000) Superpolynomial size set-systems with restricted intersections mod 6 and explicit Ramsey graphs. Combinatorica 20(1): 71\u201385","journal-title":"Combinatorica"},{"issue":"A 1","key":"17_CR13","first-page":"11","volume":"82","author":"T. Itoh","year":"1999","unstructured":"Itoh T. (1999) Efficient private information retrieval. IEICE Trans. Fund. Electronics Comm. E 82(A 1): 11\u201320","journal-title":"IEICE Trans. Fund. Electronics Comm. E"},{"issue":"D 2","key":"17_CR14","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1587\/transinf.E93.D.263","volume":"93","author":"Y Itoh","year":"2010","unstructured":"Itoh T., Suzuki Y (2010) New constructions for query-efficient locally decodable codes of subexponential length. IEICE Trans. Inform. Syst. E 93(D 2): 263\u2013270","journal-title":"IEICE Trans. Inform. Syst. E"},{"key":"17_CR15","unstructured":"J. Katz & L. Trevisan (2000). On the efficiency of local decoding procedures for error-correcting codes. In STOC \u201900: Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 80\u201386 (electronic). ACM, New York."},{"issue":"5","key":"17_CR16","doi-asserted-by":"crossref","first-page":"1952","DOI":"10.1137\/070696519","volume":"38","author":"K.S. Kedlaya","year":"2008","unstructured":"Kedlaya K.S., Yekhanin S. (2008) Locally decodable codes from nice subsets of finite fields and prime factors of Mersenne numbers. SIAM J. Comput. 38(5): 1952\u20131969","journal-title":"SIAM J. Comput."},{"issue":"3","key":"17_CR17","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1016\/j.jcss.2004.04.007","volume":"69","author":"I. Kerenidis","year":"2004","unstructured":"Kerenidis I., de Wolf R. (2004) Exponential lower bound for 2-query locally decodable codes via a quantum argument. J. Comput. System Sci. 69(3): 395\u2013420","journal-title":"J. Comput. System Sci."},{"key":"17_CR18","unstructured":"F. J. MacWilliams & N. J. A. Sloane (1977). The Theory of Error-Correcting Codes. North-Holland Publishing Co., Amsterdam."},{"key":"17_CR19","unstructured":"B. R. McDonald (1974). Finite Rings with Identity. Marcel Dekker Inc., New York, ix+429. Pure and Applied Mathematics, Vol. 28."},{"key":"17_CR20","doi-asserted-by":"crossref","unstructured":"K. Obata (2002). Optimal lower bounds for 2-query locally decodable linear codes. In Randomization and Approximation Techniques in Computer Science, volume 2483 of Lecture Notes in Comput. Sci., 39\u201350. Springer, Berlin.","DOI":"10.1007\/3-540-45726-7_4"},{"key":"17_CR21","unstructured":"P. Raghavendra (2007). A note on Yekhanin\u2019s locally decodable codes. Electronic Colloquium on Computational Complexity (ECCC) TR07-016."},{"issue":"6","key":"17_CR22","doi-asserted-by":"crossref","first-page":"244","DOI":"10.1016\/j.ipl.2005.11.009","volume":"97","author":"D. Shiowattana","year":"2006","unstructured":"D. Shiowattana & S. V. Lokam (2006). An optimal lower bound for 2-query locally decodable linear codes. Inform. Process. Lett. 97(6), 244\u2013250.","journal-title":"Inform. Process. Lett."},{"key":"17_CR23","unstructured":"L. Trevisan (2004). Some applications of coding theory in computational complexity. In Complexity of Computations and Proofs, volume 13 of Quad. Mat., 347\u2013424. Dept. Math., Seconda Univ. Napoli, Caserta."},{"key":"17_CR24","unstructured":"L. C. Washington (1997). Introduction to cyclotomic fields, volume 83 of Graduate Texts in Mathematics. Springer-Verlag, New York, 2nd edition, xiv+487."},{"key":"17_CR25","unstructured":"S. Wehner & R. de Wolf (2005). Improved lower bounds for locally decodable codes and private information retrieval. In ICALP \u201905: Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, volume 3580 of Lecture Notes in Comput. Sci., 1424\u20131436. Springer, Berlin."},{"issue":"4","key":"17_CR26","doi-asserted-by":"crossref","first-page":"1046","DOI":"10.1137\/06065773X","volume":"37","author":"D. Woodruff","year":"2007","unstructured":"Woodruff D., Yekhanin S. (2007) A geometric approach to information-theoretic private information retrieval. SIAM J. Comput. 37(4): 1046\u20131056","journal-title":"SIAM J. Comput."},{"key":"17_CR27","unstructured":"D. P. Woodruff (2007). New lower bounds for general locally decodable codes. Electronic Colloquium on Computational Complexity (ECCC) TR07-006."},{"issue":"1","key":"17_CR28","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1326554.1326555","volume":"55","author":"S. Yekhanin","year":"2008","unstructured":"Yekhanin S. (2008) Towards 3-query locally decodable codes of subexponential length. J. ACM 55(1): 1\u201316","journal-title":"J. ACM"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-011-0017-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-011-0017-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-011-0017-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,8]],"date-time":"2025-03-08T03:02:40Z","timestamp":1741402960000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-011-0017-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,8,4]]},"references-count":28,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2013,3]]}},"alternative-id":["17"],"URL":"https:\/\/doi.org\/10.1007\/s00037-011-0017-1","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"type":"print","value":"1016-3328"},{"type":"electronic","value":"1420-8954"}],"subject":[],"published":{"date-parts":[[2011,8,4]]}}}