{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:56:31Z","timestamp":1781078191218,"version":"3.54.1"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2009,1,27]],"date-time":"2009-01-27T00:00:00Z","timestamp":1233014400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2010,12]]},"DOI":"10.1007\/s00453-008-9272-1","type":"journal-article","created":{"date-parts":[[2009,1,26]],"date-time":"2009-01-26T16:41:38Z","timestamp":1232988098000},"page":"831-859","source":"Crossref","is-referenced-by-count":12,"title":["On Locally Decodable Codes, Self-Correctable Codes, and t-Private PIR"],"prefix":"10.1007","volume":"58","author":[{"given":"Omer","family":"Barkol","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yuval","family":"Ishai","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Enav","family":"Weinreb","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2009,1,27]]},"reference":[{"key":"9272_CR1","unstructured":"Akers, S., Robbins, T.: Logical design with three-input majority gates. Comput. Des. 12\u201327 (1963)"},{"key":"9272_CR2","doi-asserted-by":"crossref","unstructured":"Ambainis, A.: Upper bound on the communication complexity of private information retrieval. In: Proc. of the 24th International Colloquium on Automata Languages and Programing (ICALP), pp.\u00a0401\u2013407 (1997)","DOI":"10.1007\/3-540-63165-8_196"},{"issue":"1","key":"9272_CR3","first-page":"70","volume":"45","author":"S. Arora","year":"1998","unstructured":"Arora, S., Safra, S.: Probabilistic checking of proofs: a new characterization of NP. J.\u00a0ACM 45(1), 70\u2013122 (1998). Preliminary version in FOCS \u201992","journal-title":"J.\u00a0ACM"},{"issue":"3","key":"9272_CR4","first-page":"501","volume":"45","author":"S. Arora","year":"1998","unstructured":"Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M.: Proof verification and the hardness of approximation problems. J.\u00a0ACM 45(3), 501\u2013555 (1998). Preliminary version in FOCS \u201992","journal-title":"J.\u00a0ACM"},{"key":"9272_CR5","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9781316529836","volume-title":"Designs and Their Codes","author":"E. Assmus","year":"1992","unstructured":"Assmus, E., Key, J.: Designs and Their Codes. Cambridge University Press, Cambridge (1992)"},{"issue":"1","key":"9272_CR6","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1023\/A:1027359905521","volume":"9","author":"E.F. Assmus","year":"1996","unstructured":"Assmus, E.F., Key, J.D.: Designs and codes: An update. Des. Codes Cryptogr. 9(1), 7\u201327 (1996)","journal-title":"Des. Codes Cryptogr."},{"key":"9272_CR7","doi-asserted-by":"crossref","unstructured":"Babai, L., Fortnow, L., Levin, L.A., Szegedy, M.: Checking computations in polylogarithmic time. In: Proc. of the 23rd Annual ACM Symposium on the Theory of Computing (STOC), pp.\u00a021\u201331 (1991)","DOI":"10.1145\/103418.103428"},{"key":"9272_CR8","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1007\/BF01275486","volume":"3","author":"L. Babai","year":"1993","unstructured":"Babai, L., Fortnow, L., Nisan, N., Wigderson, A.: BPP Has subexponential time simulations unless EXPTIME has publishable proofs. Comput. Complex. 3, 307\u2013318 (1993)","journal-title":"Comput. Complex."},{"key":"9272_CR9","doi-asserted-by":"crossref","unstructured":"Beaver, D., Feigenbaum, J.: Hiding instances in multioracle queries. In: 7th Ann. Symposium on Theoretical Aspects of Computer Science (STACS), pp.\u00a037\u201348 (1990)","DOI":"10.1007\/3-540-52282-4_30"},{"key":"9272_CR10","doi-asserted-by":"crossref","unstructured":"Beimel, A., Ishai, Y.: Information-theoretic private information retrieval: a unified construction. In: Proc. of the 28th International Colloquium on Automata Languages and Programing (ICALP), pp.\u00a0912\u2013926 (2001)","DOI":"10.1007\/3-540-48224-5_74"},{"issue":"2","key":"9272_CR11","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.: General constructions for information-theoretic private information retrieval. J.\u00a0Comput. Syst. Sci. 71(2), 213\u2013247 (2005)","journal-title":"J.\u00a0Comput. Syst. Sci."},{"key":"9272_CR12","doi-asserted-by":"crossref","unstructured":"Beimel, A., Ishai, Y., Kushilevitz, E., Raymond, J.F.: Breaking the $O(n^{\\frac{1}{(2k-1)}})$ barrier for information-theoretic private information retrieval. In: Proc. of the 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp.\u00a0261\u2013270 (2002)","DOI":"10.1109\/SFCS.2002.1181949"},{"key":"9272_CR13","volume-title":"Design Theory","author":"T. Beth","year":"1999","unstructured":"Beth, T., Jungnickel, D., Lenz, H.: Design Theory, vol.\u00a01, 2nd edn. Cambridge University Press, Cambridge (1999)","edition":"2"},{"issue":"1","key":"9272_CR14","first-page":"269","volume":"42","author":"M. Blum","year":"1995","unstructured":"Blum, M., Kannan, S.: Designing programs that check their work. J.\u00a0ACM 42(1), 269\u2013291 (1995)","journal-title":"J.\u00a0ACM"},{"key":"9272_CR15","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1023\/A:1008362706649","volume":"17","author":"N.J. Calkin","year":"1999","unstructured":"Calkin, N.J., Key, J.D., De Resmini, M.J.: Minimum weight and dimension formulas for some geometric codes. Des. Codes Cryptogr. 17, 105\u2013120 (1999)","journal-title":"Des. Codes Cryptogr."},{"key":"9272_CR16","doi-asserted-by":"crossref","unstructured":"Chor, B., Gilboa, N.: Computationally private information retrieval. In: Proc. of the 29th Annual ACM Symposium on the Theory of Computing (STOC), pp.\u00a0304\u2013313 (1997)","DOI":"10.1145\/258533.258609"},{"key":"9272_CR17","doi-asserted-by":"crossref","unstructured":"Chor, B., Goldreich, O., Kushilevitz, E., Sudan, M.: Private information retrieval. In: Proc. of the 36th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp.\u00a041\u201350 (1995)","DOI":"10.1109\/SFCS.1995.492461"},{"key":"9272_CR18","unstructured":"Chung, K., Trevisan, L., Vadhan, S.: Private communication (2007)"},{"issue":"1","key":"9272_CR19","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1007\/s001450010008","volume":"14","author":"G. Di-Crescenzo","year":"2001","unstructured":"Di-Crescenzo, G., Ishai, Y., Ostrovsky, R.: Universal service-providers for private information retrieval. J.\u00a0Cryptol. 14(1), 37\u201374 (2001). Preliminary version in PODC\u201998","journal-title":"J.\u00a0Cryptol."},{"key":"9272_CR20","doi-asserted-by":"crossref","first-page":"2152","DOI":"10.1109\/18.868484","volume":"46","author":"P. Ding","year":"2000","unstructured":"Ding, P., Key, J.: Minimum-weight codewords as generators of generalized Reed-Muller codes. IEEE Trans. Inf. Theory 46, 2152\u20132158 (2000)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"2","key":"9272_CR21","first-page":"268","volume":"43","author":"U. Feige","year":"1996","unstructured":"Feige, U., Goldwasser, S., Lovasz, L., Safra, S., Szegedy, M.: Interactive proofs and the hardness of approximating cliques. J.\u00a0ACM 43(2), 268\u2013292 (1996). Preliminary version in FOCS \u201991","journal-title":"J.\u00a0ACM"},{"key":"9272_CR22","first-page":"72","volume":"82","author":"W. Gasarch","year":"2004","unstructured":"Gasarch, W.: A survey on private information retrieval. Bull. Eur. Assoc. Theor. Comput. Sci. 82, 72\u2013107 (2004). See http:\/\/www.cs.umd.edu\/~gasarch\/pir\/pir.html for updates","journal-title":"Bull. Eur. Assoc. Theor. Comput. Sci."},{"key":"9272_CR23","doi-asserted-by":"crossref","first-page":"153","DOI":"10.32917\/hmj\/1206137446","volume":"3","author":"N. Hamada","year":"1973","unstructured":"Hamada, N.: On the p-rank of the incidence matrix of a balanced or partially balanced incomplete block design and its application to error-correcting codes. Hiroshima Math. J. 3, 153\u2013226 (1973)","journal-title":"Hiroshima Math. J."},{"issue":"3","key":"9272_CR24","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1016\/0097-3165(81)90024-8","volume":"30","author":"N. Hamada","year":"1981","unstructured":"Hamada, N.: The geometric structure and the p-rank of an affine triple system derived from a nonassociative moufang loop with the maximum associative center. J.\u00a0Comb. Theory Ser. A 30(3), 285\u2013297 (1981)","journal-title":"J.\u00a0Comb. Theory Ser. A"},{"issue":"1","key":"9272_CR25","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1007\/s001459910003","volume":"13","author":"M. \u00a0Hirt","year":"2000","unstructured":"\u00a0Hirt, M., Maurer, U.M.: Player simulation and general adversary structures in perfect multiparty computation. J.\u00a0Cryptol. 13(1), 31\u201360 (2000)","journal-title":"J.\u00a0Cryptol."},{"key":"9272_CR26","doi-asserted-by":"crossref","unstructured":"Ishai, Y., Kushilevitz, E.: Improved upper bounds on information-theoretic private information retrieval. In: Proc. of the 31st Annual ACM Symposium on the Theory of Computing (STOC), pp.\u00a079\u201388 (1999)","DOI":"10.1145\/301250.301275"},{"key":"9272_CR27","doi-asserted-by":"crossref","unstructured":"Ishai, Y., Kushilevitz, E.: On the hardness of information-theoretic multiparty computation. In: Proc. EUROCRYPT, pp.\u00a0439\u2013455 (2004)","DOI":"10.1007\/978-3-540-24676-3_26"},{"key":"9272_CR28","doi-asserted-by":"crossref","unstructured":"Katz, J., Trevisan, L.: On the efficiency of local decoding procedures for error-correcting codes. In: Proc. of the 32th Annual ACM Symposium on the Theory of Computing (STOC), pp.\u00a080\u201386 (2000)","DOI":"10.1145\/335305.335315"},{"key":"9272_CR29","doi-asserted-by":"crossref","unstructured":"Kerenidis, I., de Wolf, R.: Exponential lower bound for 2-query locally decodable codes. J.\u00a0Comput. Syst. Sci. 395\u2013420 (2004). Preliminary version in STOC \u201903","DOI":"10.1016\/j.jcss.2004.04.007"},{"key":"9272_CR30","doi-asserted-by":"crossref","unstructured":"Kushilevitz, E., Ostrovsky, R.: Replication is not needed: single database, computationally-private information retrieval. In: Proc. of the 38th IEEE Symp. on Foundations of Computer Science (FOCS), pp.\u00a0364\u2013373 (1997)","DOI":"10.1109\/SFCS.1997.646125"},{"key":"9272_CR31","doi-asserted-by":"crossref","unstructured":"Lipton, R.: Efficient checking of computations. In: 7th Ann. Symposium on Theoretical Aspects of Computer Science (STACS), pp.\u00a0207\u2013215 (1990)","DOI":"10.1007\/3-540-52282-4_44"},{"key":"9272_CR32","doi-asserted-by":"crossref","unstructured":"Lu, C.-J., Reingold, O., Vadhan, S.P., Wigderson, A.: Extractors: optimal up to constant factors. In: Proc. of the 35th Annual ACM Symposium on the Theory of Computing (STOC), pp.\u00a0602\u2013611 (2003)","DOI":"10.1145\/780542.780630"},{"key":"9272_CR33","unstructured":"Raghavendra, P.: A note on Yekhanin\u2019s locally decodable codes. In: Electronic Colloquium on Computational Complexity (ECCC) (2007)"},{"key":"9272_CR34","doi-asserted-by":"crossref","unstructured":"Razborov, A.A., Yekhanin, S.: An \u03a9(n 1\/3) lower bound for bilinear group based Private Information Retrieval. In: Proc. of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp.\u00a0739\u2013748 (2006)","DOI":"10.1109\/FOCS.2006.10"},{"key":"9272_CR35","doi-asserted-by":"crossref","first-page":"612","DOI":"10.1145\/359168.359176","volume":"22","author":"A. Shamir","year":"1979","unstructured":"Shamir, A.: How to share a secret. Commun. ACM 22, 612\u2013613 (1979)","journal-title":"Commun. ACM"},{"issue":"2","key":"9272_CR36","doi-asserted-by":"crossref","first-page":"236","DOI":"10.1006\/jcss.2000.1730","volume":"62","author":"M. Sudan","year":"2001","unstructured":"Sudan, M., Trevisan, L., Vadhan, S.P.: Pseudorandom generators without the XOR lemma. J.\u00a0Comput. Syst. Sci. 62(2), 236\u2013266 (2001). Preliminary version in STOC \u201999","journal-title":"J.\u00a0Comput. Syst. Sci."},{"key":"9272_CR37","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1023\/A:1008314923487","volume":"17","author":"V.D. Tonchev","year":"1999","unstructured":"Tonchev, V.D.: Linear perfert codes and a characterization of the classical designs. Des. Codes Cryptogr. 17, 121\u2013128 (1999)","journal-title":"Des. Codes Cryptogr."},{"key":"9272_CR38","first-page":"347","volume":"13","author":"L. Trevisan","year":"2004","unstructured":"Trevisan, L.: Some applications of coding theory in computational complexity. Quad. Mat. 13, 347\u2013424 (2004). Also available as ECCC Report No.\u00a043 (2004)","journal-title":"Quad. Mat."},{"key":"9272_CR39","doi-asserted-by":"crossref","unstructured":"Wehner, S., de Wolf, R.: Improved lower bounds for locally decodable codes and private information retrieval. In: Proc. of the 32nd International Colloquium on Automata Languages and Programing (ICALP), pp.\u00a01424\u20131436 (2005)","DOI":"10.1007\/11523468_115"},{"key":"9272_CR40","unstructured":"Woodruff, D.: New lower bounds for general locally decodable codes. In: Electronic Colloquium on Computational Complexity (ECCC), Report No.\u00a06 (2007)"},{"key":"9272_CR41","doi-asserted-by":"crossref","unstructured":"Woodruff, D., Yekhanin, S.: A geometric approach to information-theoretic private information retrieval. In: Proc. of the 20th Annual IEEE Conference on Computational Complexity (CCC), pp.\u00a0275\u2013284 (2005)","DOI":"10.1109\/CCC.2005.2"},{"key":"9272_CR42","doi-asserted-by":"crossref","unstructured":"Yekhanin, S.: Towards 3-query locally decodable codes of subexponential length. In: Proc. of the 39th Annual ACM Symposium on the Theory of Computing (STOC) (2007)","DOI":"10.1145\/1250790.1250830"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-008-9272-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-008-9272-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-008-9272-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,7]],"date-time":"2025-02-07T06:44:17Z","timestamp":1738910657000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-008-9272-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,1,27]]},"references-count":42,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2010,12]]}},"alternative-id":["9272"],"URL":"https:\/\/doi.org\/10.1007\/s00453-008-9272-1","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,1,27]]}}}