{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T23:14:07Z","timestamp":1763507647257,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":36,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540742074"},{"type":"electronic","value":"9783540742081"}],"license":[{"start":{"date-parts":[[2007,1,1]],"date-time":"2007-01-01T00:00:00Z","timestamp":1167609600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2007]]},"DOI":"10.1007\/978-3-540-74208-1_23","type":"book-chapter","created":{"date-parts":[[2007,8,27]],"date-time":"2007-08-27T14:52:26Z","timestamp":1188226346000},"page":"311-325","source":"Crossref","is-referenced-by-count":14,"title":["On Locally Decodable Codes, Self-correctable Codes, and t-Private PIR"],"prefix":"10.1007","author":[{"given":"Omer","family":"Barkol","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuval","family":"Ishai","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Enav","family":"Weinreb","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"23_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1007\/3-540-63165-8_196","volume-title":"Automata, Languages and Programming","author":"A. Ambainis","year":"1997","unstructured":"Ambainis, A.: Upper bound on the communication complexity of private information retrieval. In: Degano, P., Gorrieri, R., Marchetti-Spaccamela, A. (eds.) ICALP 1997. LNCS, vol.\u00a01256, pp. 401\u2013407. Springer, Heidelberg (1997)"},{"issue":"1","key":"23_CR2","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1145\/273865.273901","volume":"45","author":"S. Arora","year":"1998","unstructured":"Arora, S., Safra, S.: Probabilistic checking of proofs: a new characterization of NP. J. of the ACM\u00a045(1), 70\u2013122 (1998)","journal-title":"J. of the ACM"},{"issue":"3","key":"23_CR3","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1145\/278298.278306","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. of the ACM\u00a045(3), 501\u2013555 (1998)","journal-title":"J. of the ACM"},{"issue":"1","key":"23_CR4","doi-asserted-by":"publisher","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. Designs, Codes and Cryptography\u00a09(1), 7\u201327 (1996)","journal-title":"Designs, Codes and Cryptography"},{"key":"23_CR5","doi-asserted-by":"crossref","unstructured":"Babai, L., Fortnow, L., Levin, L.A., Szegedy, M.: Checking Computations in Polylogarithmic Time. In: Proc. STOC 1991, pp. 21\u201331 (1991)","DOI":"10.1145\/103418.103428"},{"key":"23_CR6","doi-asserted-by":"publisher","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. Computational Complexity\u00a03, 307\u2013318 (1993)","journal-title":"Computational Complexity"},{"key":"23_CR7","doi-asserted-by":"crossref","unstructured":"Beaver, D., Feigenbaum, J.: Hiding instances in multioracle queries. In: Proc. of STACS 1990, pp. 37\u201348 (1990)","DOI":"10.1007\/3-540-52282-4_30"},{"key":"23_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"912","DOI":"10.1007\/3-540-48224-5_74","volume-title":"Automata, Languages and Programming","author":"A. Beimel","year":"2001","unstructured":"Beimel, A., Ishai, Y.: Information-theoretic private information retrieval: A unified construction. In: Orejas, F., Spirakis, P.G., van Leeuwen, J. (eds.) ICALP 2001. LNCS, vol.\u00a02076, pp. 912\u2013926. Springer, Heidelberg (2001)"},{"issue":"2","key":"23_CR9","doi-asserted-by":"publisher","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. of Computer and Systems Sciences\u00a071(2), 213\u2013247 (2005)","journal-title":"J. of Computer and Systems Sciences"},{"key":"23_CR10","first-page":"261","volume-title":"FOCS","author":"A. Beimel","year":"2002","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: FOCS. Proc. of the 43rd Annual IEEE Symposium on Foundations of Computer Science 2002, pp. 261\u2013270. IEEE Computer Society Press, Los Alamitos (2002)"},{"key":"23_CR11","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139507660","volume-title":"Design Theory","author":"T. Beth","year":"1999","unstructured":"Beth, T., Jungnickel, D., Lenz, H.: Design Theory, 2nd edn., vol.\u00a01. Cambridge University Press, Cambridge (1999)","edition":"2"},{"issue":"1","key":"23_CR12","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1145\/200836.200880","volume":"42","author":"M. Blum","year":"1995","unstructured":"Blum, M., Kannan, S.: Designing programs that check their work. J. of the ACM\u00a042(1), 269\u2013291 (1995)","journal-title":"J. of the ACM"},{"key":"23_CR13","doi-asserted-by":"crossref","unstructured":"Chor, B., Gilboa, N.: Computationally private information retrieval. In: Proc. of STOC 1997, pp. 304\u2013313 (1997)","DOI":"10.1145\/258533.258609"},{"key":"23_CR14","first-page":"41","volume-title":"FOCS 1995","author":"B. Chor","year":"1995","unstructured":"Chor, B., Goldreich, O., Kushilevitz, E., Sudan, M.: Private information retrieval. In: FOCS 1995. Proc. of the 36th Annual IEEE Symposium on Foundations of Computer Science, pp. 41\u201350. IEEE Computer Society Press, Los Alamitos (1995)"},{"issue":"1","key":"23_CR15","doi-asserted-by":"publisher","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. of Cryptology\u00a014(1), 37\u201374 (2001)","journal-title":"J. of Cryptology"},{"issue":"2","key":"23_CR16","doi-asserted-by":"publisher","first-page":"268","DOI":"10.1145\/226643.226652","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. of the ACM\u00a043(2), 268\u2013292 (1996)","journal-title":"J. of the ACM"},{"key":"23_CR17","first-page":"72","volume":"82","author":"W. Gasarch","year":"2004","unstructured":"Gasarch, W.: A survey on private information retrieval. Bulletin of the European Association for Theoretical Computer Science\u00a082, 72\u2013107 (2004)","journal-title":"Bulletin of the European Association for Theoretical Computer Science"},{"key":"23_CR18","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.\u00a03, 153\u2013226 (1973)","journal-title":"Hiroshima Math J."},{"issue":"3","key":"23_CR19","doi-asserted-by":"publisher","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. Comb. Theory, Ser. A\u00a030(3), 285\u2013297 (1981)","journal-title":"J. Comb. Theory, Ser. A"},{"issue":"1","key":"23_CR20","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1007\/s001459910003","volume":"13","author":"M. Hirt","year":"2000","unstructured":"Hirt, M., Maurer, U.M.: Player simulation and general adversary structures in perfect multiparty computation. J. of Cryptology\u00a013(1), 31\u201360 (2000)","journal-title":"J. of Cryptology"},{"key":"23_CR21","doi-asserted-by":"crossref","unstructured":"Ishai, Y., Kushilevitz, E.: Improved upper bounds on information-theoretic private information retrieval. In: Proc. STOC 1999, pp. 79\u201388 (1999)","DOI":"10.1145\/301250.301275"},{"key":"23_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1007\/978-3-540-24676-3_26","volume-title":"Advances in Cryptology - EUROCRYPT 2004","author":"Y. Ishai","year":"2004","unstructured":"Ishai, Y., Kushilevitz, E.: On the Hardness of Information-Theoretic Multiparty Computation. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol.\u00a03027, pp. 439\u2013455. Springer, Heidelberg (2004)"},{"key":"23_CR23","doi-asserted-by":"crossref","unstructured":"Katz, J., Trevisan, L.: On the efficiency of local decoding procedures for error-correcting codes. In: STOC 2000, pp. 80\u201386 (2000)","DOI":"10.1145\/335305.335315"},{"key":"23_CR24","doi-asserted-by":"crossref","unstructured":"Kerenidis, I., de Wolf, R.: Exponential lower bound for 2-query locally decodable codes. J. of Computer and Systems Sciences, 395\u2013420 (2004)","DOI":"10.1016\/j.jcss.2004.04.007"},{"key":"23_CR25","doi-asserted-by":"crossref","unstructured":"Kushilevitz, E., Ostrovsky, R.: Replication is not needed: Single database, computationally-private information retrieval. In: FOCS 1997, pp. 364\u2013373 (1997)","DOI":"10.1109\/SFCS.1997.646125"},{"key":"23_CR26","doi-asserted-by":"crossref","unstructured":"Lipton, R.: Efficient checking of computations. In: STACS 1990, pp. 207\u2013215 (1990)","DOI":"10.1007\/3-540-52282-4_44"},{"key":"23_CR27","doi-asserted-by":"crossref","unstructured":"Lu, C.-J., Reingold, O., Vadhan, S.P., Wigderson, A.: Extractors: optimal up to constant factors. In: Proc.STOC 2003, pp. 602\u2013611 (2003)","DOI":"10.1145\/780542.780630"},{"key":"23_CR28","unstructured":"Raghavendra, P.: A note on Yekhanin\u2019s locally decodable codes. In: Electronic Colloquium on Computational Complexity (ECCC) (2007)"},{"key":"23_CR29","doi-asserted-by":"publisher","first-page":"612","DOI":"10.1145\/359168.359176","volume":"22","author":"A. Shamir","year":"1979","unstructured":"Shamir, A.: How to share a secret. Communications of the ACM\u00a022, 612\u2013613 (1979)","journal-title":"Communications of the ACM"},{"issue":"2","key":"23_CR30","doi-asserted-by":"publisher","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. of Computer and Systems Sciences\u00a062(2), 236\u2013266 (2001)","journal-title":"J. of Computer and Systems Sciences"},{"key":"23_CR31","doi-asserted-by":"publisher","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. Designs, Codes and Cryptography\u00a017, 121\u2013128 (1999)","journal-title":"Designs, Codes and Cryptography"},{"key":"23_CR32","first-page":"347","volume":"13","author":"L. Trevisan","year":"2004","unstructured":"Trevisan, L.: Some applications of coding theory in computational complexity. Quaderni di Matematica\u00a013, 347\u2013424 (2004)","journal-title":"Quaderni di Matematica"},{"key":"23_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1424","DOI":"10.1007\/11523468_115","volume-title":"Automata, Languages and Programming","author":"S. Wehner","year":"2005","unstructured":"Wehner, S., de Wolf, R.: Improved lower bounds for locally decodable codes and private information retrieval. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol.\u00a03580, pp. 1424\u20131436. Springer, Heidelberg (2005)"},{"key":"23_CR34","unstructured":"Woodruff, D.: New lower bounds for general locally decodable codes. In: ECCC, Report No.\u00a06 (2007)"},{"key":"23_CR35","doi-asserted-by":"crossref","unstructured":"Woodruff, D., Yekhanin, S.: A geometric approach to information-theoretic private information retrieval. In: proc. of CCC 2005, pp. 275\u2013284 (2005)","DOI":"10.1109\/CCC.2005.2"},{"key":"23_CR36","doi-asserted-by":"crossref","unstructured":"Yekhanin, S.: Towards 3-Query Locally Decodable Codes of Subexponential Length. In: Proc. STOC 2007 (2007)","DOI":"10.1145\/1250790.1250830"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-74208-1_23","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,20]],"date-time":"2025-01-20T17:37:03Z","timestamp":1737394623000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-74208-1_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007]]},"ISBN":["9783540742074","9783540742081"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-74208-1_23","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2007]]}}}