{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,19]],"date-time":"2026-02-19T07:22:47Z","timestamp":1771485767743,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540734192","type":"print"},{"value":"9783540734208","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-73420-8_35","type":"book-chapter","created":{"date-parts":[[2007,8,25]],"date-time":"2007-08-25T14:58:43Z","timestamp":1188053923000},"page":"387-398","source":"Crossref","is-referenced-by-count":19,"title":["Private Locally Decodable Codes"],"prefix":"10.1007","author":[{"given":"Rafail","family":"Ostrovsky","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Omkant","family":"Pandey","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Amit","family":"Sahai","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"35_CR1","doi-asserted-by":"crossref","unstructured":"Babai, L., Fortnow, L., Levin, L.A., Szegedy, M.: Checking computations in polylogarithmic time. In: STOC, pp. 21\u201331 (1991)","DOI":"10.1145\/103418.103428"},{"key":"35_CR2","doi-asserted-by":"crossref","unstructured":"Beimel, A., Ishai, Y.: Information-theoretic private information retrieval: A unified construction. In: ICALP, pp. 912\u2013926 (2001)","DOI":"10.1007\/3-540-48224-5_74"},{"key":"35_CR3","doi-asserted-by":"crossref","unstructured":"Beimel, A., Ishai, Y., Kushilevitz, E., Raymond, J.-F.: Breaking the o(n1\/(2k-1)) barrier for information-theoretic private information retrieval. In: FOCS, pp. 261\u2013270 (2002)","DOI":"10.1109\/SFCS.2002.1181949"},{"issue":"6","key":"35_CR4","doi-asserted-by":"publisher","first-page":"965","DOI":"10.1145\/293347.293350","volume":"45","author":"B. Chor","year":"1998","unstructured":"Chor, B., Kushilevitz, E., Goldreich, O., Sudan, M.: Private information retrieval. J. ACM\u00a045(6), 965\u2013981 (1998)","journal-title":"J. ACM"},{"key":"35_CR5","first-page":"184","volume-title":"IEEE Conference on Computational Complexity","author":"A. Deshpande","year":"2002","unstructured":"Deshpande, A., Jain, R., Kavitha, T., Radhakrishnan, J., Lokam, S.V.: Better lower bounds for locally decodable codes. In: IEEE Conference on Computational Complexity, pp. 184\u2013193. IEEE Computer Society Press, Los Alamitos (2002)"},{"key":"35_CR6","doi-asserted-by":"crossref","unstructured":"Gemmell, P., Lipton, R.J., Rubinfeld, R., Sudan, M., Wigderson, A.: Self-testing\/correcting for polynomials and for approximate functions. In: STOC, pp. 32\u201342 (1991)","DOI":"10.1145\/103418.103429"},{"issue":"4","key":"35_CR7","doi-asserted-by":"publisher","first-page":"792","DOI":"10.1145\/6490.6503","volume":"33","author":"O. Goldreich","year":"1986","unstructured":"Goldreich, O., Goldwasser, S., Micali, S.: How to construct random functions. J. ACM\u00a033(4), 792\u2013807 (1986)","journal-title":"J. ACM"},{"key":"35_CR8","first-page":"175","volume-title":"IEEE Conference on Computational Complexity","author":"O. Goldreich","year":"2002","unstructured":"Goldreich, O., Karloff, H.J., Schulman, L.J., Trevisan, L.: Lower bounds for linear locally decodable codes and private information retrieval. In: IEEE Conference on Computational Complexity, pp. 175\u2013183. IEEE Computer Society Press, Los Alamitos (2002)"},{"key":"35_CR9","unstructured":"Gopalana, P., Lipton, R.J., Ding, Y.Z.: Error correction against computationally bounded adversaries. In Manuscript (2004)"},{"key":"35_CR10","doi-asserted-by":"publisher","first-page":"652","DOI":"10.1109\/TIT.1972.1054893","volume":"18","author":"J. Justesen","year":"1972","unstructured":"Justesen, J.: A class of constructive asymptotically good algebraic codes. IEEE Transactions on Information Theory\u00a018, 652\u2013656 (1972)","journal-title":"IEEE Transactions on Information Theory"},{"key":"35_CR11","doi-asserted-by":"crossref","unstructured":"Katz, J., Trevisan, L.: On the efficiency of local decoding procedures for error-correcting codes. In: STOC, pp. 80\u201386 (2000)","DOI":"10.1145\/335305.335315"},{"key":"35_CR12","doi-asserted-by":"crossref","unstructured":"Kerenidis, I., de Wolf, R.: Exponential lower bound for 2-query locally decodable codes via a quantum argument. In: STOC, pp. 106\u2013115 (2003)","DOI":"10.1145\/780559.780560"},{"key":"35_CR13","doi-asserted-by":"crossref","unstructured":"Kushilevitz, E., Ostrovsky, R.: Replication is not needed: Single database, computationally-private information retrieval. In: FOCS, pp. 364\u2013373 (1997)","DOI":"10.1109\/SFCS.1997.646125"},{"key":"35_CR14","doi-asserted-by":"crossref","unstructured":"Langberg, M.: Private codes or succinct random codes that are (almost) perfect. In: FOCS, pp. 325\u2013334 (2004)","DOI":"10.1109\/FOCS.2004.51"},{"key":"35_CR15","doi-asserted-by":"crossref","unstructured":"Lipton, R.J.: A new approach to information theory. In: STACS, pp. 699\u2013708 (1994)","DOI":"10.1007\/3-540-57785-8_183"},{"key":"35_CR16","series-title":"Lecture Notes in Computer Science","volume-title":"Theory of Cryptography","author":"S. Micali","year":"2006","unstructured":"Micali, S., Peikert, C., Sudan, M., Wilson, D.A.: Optimal Error Correction Against Computationally Bounded Noise. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol.\u00a03876, Springer, Heidelberg (2006)"},{"key":"35_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/3-540-45726-7_4","volume-title":"Randomization and Approximation Techniques in Computer Science","author":"K. Obata","year":"2002","unstructured":"Obata, K.: Optimal lower bounds for 2-query locally decodable linear codes. In: Rolim, J.D.P., Vadhan, S.P. (eds.) RANDOM 2002. LNCS, vol.\u00a02483, pp. 39\u201350. Springer, Heidelberg (2002)"},{"key":"35_CR18","unstructured":"Ostrovsky, R., Pandey, O., Sahai, A.: Private Locally Decodable Codes. available at http:\/\/eprint.iacr.org\/2007\/025\/"},{"issue":"6","key":"35_CR19","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1016\/j.ipl.2005.11.009","volume":"97","author":"D. Shiowattana","year":"2006","unstructured":"Shiowattana, D., Lokam, S.V.: An optimal lower bound for 2-query locally decodable linear codes. Inf. Process. Lett.\u00a097(6), 244\u2013250 (2006)","journal-title":"Inf. Process. Lett."},{"key":"35_CR20","doi-asserted-by":"crossref","unstructured":"Sipser, M., Spielman, D.A.: Expander codes. In: FOCS, pp. 566\u2013576 (1994)","DOI":"10.1109\/SFCS.1994.365734"},{"key":"35_CR21","unstructured":"Smith, A.: Scrambling adversarial errors using few random bits. In: SODA (2007)"},{"key":"35_CR22","unstructured":"Sudan, M.: Efficient Checking of Polynomials and Proofs and the Hardness of Approximation Problems, PhD Thesis, University of California at Berkley (1992)"},{"key":"35_CR23","doi-asserted-by":"crossref","unstructured":"Wehner, S., de Wolf, R.: Improved lower bounds for locally decodable codes and private information retrieval. In: ICALP, pp. 1424\u20131436 (2005)","DOI":"10.1007\/11523468_115"},{"key":"35_CR24","unstructured":"Woodruff, D.: New lower bounds for general locally decodable codes. In: ECCC TR07-006 (2007)"},{"key":"35_CR25","doi-asserted-by":"crossref","unstructured":"Yekhanin, S.: Towards 3-query locally decodable codes of subexponential length. In: STOC (2007) Also appears on ECCC as TR06-127 under a different title.","DOI":"10.1145\/1250790.1250830"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-73420-8_35.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,20]],"date-time":"2025-01-20T17:16:06Z","timestamp":1737393366000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-73420-8_35"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540734192","9783540734208"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-73420-8_35","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[]}}