caa a22 4500 467909601 CHVBK 20180406152845.0 cr unu---uuuuu 170328e20061001xx s 000 0 eng 10.1007/s00037-006-0216-3 doi (NATIONALLICENCE)springer-10.1007/s00037-006-0216-3 Lower bounds for linear locally decodable codes and private information retrieval [Elektronische Daten] [Oded Goldreich, Howard Karloff, Leonard Schulman, Luca Trevisan] Abstract.: We prove that if a linear error-correcting code C:{0, 1}n→{0, 1}m is such that a bit of the message can be probabilistically reconstructed by looking at two entries of a corrupted codeword, then m=2Ω (n). We also present several extensions of this result. We show a reduction from the complexity of one-round, information-theoretic Private Information Retrieval Systems (with two servers) to Locally Decodable Codes, and conclude that if all the servers' answers are linear combinations of the database content, then t = Ω (n/2a), where t is the length of the user's query and a is the length of the servers' answers. Actually, 2a can be replaced by O(ak), where k is the number of bit locations in the answer that are actually inspected in the reconstruction. Birkhäuser Verlag, Basel, 2006 Error-correcting codes nationallicence lower bounds nationallicence locally decodable codes nationallicence private information retrieval nationallicence 68P30 nationallicence Goldreich Oded Computer Science Department, Weizmann Institute of Science, Rehovot, Israel aut Karloff Howard AT&T Labs-Research, U.S.A. aut Schulman Leonard Caltech, MC256-80, 91125, Pasadena, CA, U.S.A. aut Trevisan Luca Computer Science Division, University of California at Berkeley, 94720, Berkeley, CA, U.S.A. aut computational complexity Birkhäuser-Verlag; www.birkhäuser.ch 15/3(2006-10-01), 263-296 1016-3328 15:3<263 2006 15 37 https://doi.org/10.1007/s00037-006-0216-3 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00037-006-0216-3 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Goldreich Oded Computer Science Department, Weizmann Institute of Science, Rehovot, Israel aut NATIONALLICENCE 700 1- Karloff Howard AT&T Labs-Research, U.S.A aut NATIONALLICENCE 700 1- Schulman Leonard Caltech, MC256-80, 91125, Pasadena, CA, U.S.A aut NATIONALLICENCE 700 1- Trevisan Luca Computer Science Division, University of California at Berkeley, 94720, Berkeley, CA, U.S.A aut NATIONALLICENCE 773 0- computational complexity Birkhäuser-Verlag; www.birkhäuser.ch 15/3(2006-10-01), 263-296 1016-3328 15:3<263 2006 15 37 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer