An   Ω(n1/3)   Lower Bound for Bilinear Group Based Private Information Retrieval

by Alexander Razborov and Sergey Yekhanin

Theory of Computing, Volume 3(12), pp. 221-238, 2007

Bibliography with links to cited articles

[1]   Andris Ambainis: Upper bound on the communication complexity of private information retrieval. In Proc. 32nd Intern. Colloquium on Automata, Languages and Programming (ICALP’97), volume 1256 of Lecture Notes in Computer Science, pp. 401–407. Springer, 1997. [ICALP:j210805656376051].

[2]   Richard Beigel, Lance Fortnow, and William Gasarch: A tight lower bound for restricted PIR protocols. Computational Complexity, 15:82–91, 2006. [10.1007s00037-006-0208-3].

[3]   Amos Beimel, Yuval Ishai, and Eyal Kushilevitz: General constructions for information-theoretic private information retrieval. J. Computer and System Sciences, 71:213–247, 2005. [JCSS:10.1016/j.jcss.2005.03.002].

[4]   Amos Beimel, Yuval Ishai, Eyal Kushilevitz, and Jean-Francios Raymond: Breaking the O(       )
 n1∕(2k-1) barrier for information-theoretic private information retrieval. In Proc. 43rd FOCS, pp. 261–270. IEEE Computer Society Press, 2002. [FOCS:10.1109/SFCS.2002.1181949].

[5]   Benny Chor, Oded Goldreich, Eyal Kushilevitz, and Madhu Sudan: Private information retrieval. J. ACM, 45:965–981, 1998. [JACM:10.1145/293347.293350].

[6]   William Gasarch: A survey on private information retrieval. The Bulletin of the EATCS, 82:72–107, 2004.

[7]   Oded Goldreich, Howard Karloff, Leonard Schulman, and Luca Trevisan: Lower bounds for linear locally decodable codes and private information retrieval. In Proc. 17th Computational Complexity Conf. (CCC’02), pp. 175–183. IEEE Computer Society Press, 2002. [CCC:10.1109/CCC.2002.1004353].

[8]   I. Martin Isaacs: Character theory of finite groups. Academic Press, 1976.

[9]   Toshiya Itoh: Efficient private information retrieval. IEICE Trans. Fund. of Electronics, Commun. and Comp. Sci., E82-A:11–20, 1999.

[10]   Toshiya Itoh: On lower bounds for the communication complexity of private information retrieval. IEICE Trans. Fund. of Electronics, Commun. and Comp. Sci., E82-A:157–164, 2001.

[11]   Jonathan Katz and Luca Trevisan: On the efficiency of local decoding procedures for error-correcting codes. In Proc. 32nd STOC, pp. 80–86. ACM Press, 2000. [STOC:10.1145/335305.335315].

[12]   Kiran S. Kedlaya and Sergey Yekhanin: Locally decodable codes from nice subsets of finite fields and prime factors of Mersenne numbers. Electronic Colloquium on Computational Complexity (ECCC) TR07-040, 2007. [ECCC:TR07-040].

[13]   Iordanis Kerenidis and Ronald de Wolf: Exponential lower bound for 2-query locally decodable codes via a quantum argument. J. of Computer and System Sciences, 69:395–420, 2004. [JCSS:10.1016/j.jcss.2004.04.007].

[14]   Eran Mann: Private access to distributed information. Master’s thesis, Technion - Israel Institute of Technology, Haifa, 1998.

[15]   Alexander Razborov and Sergey Yekhanin: An Ω(n13) lower bound for bilinear group based private information retrieval. In Proc. 47th FOCS, pp. 739–748. IEEE Computer Society Press, 2006. [FOCS:10.1109/FOCS.2006.10].

[16]   B. L. van der Waerden: Algebra. Springer, 2003.

[17]   Stephanie Wehner and Ronald de Wolf: Improved lower bounds for locally decodable codes and private information retrieval. In Proc. 32nd Intern. Colloquium on Automata, Languages and Programming (ICALP’05), volume 3580 of Lecture Notes in Computer Science, pp. 1424–1436. Springer, 2005. [ICALP:1utwmhj4me3lr582].

[18]   Steven H. Weintraub: Representation theory of finite groups: algebra and arithmetic. volume 59 of Graduate Studies in Mathematics. AMS, 2003.

[19]   David Woodruff and Sergey Yekhanin: A geometric approach to information-theoretic private information retrieval. In Proc. 20th IEEE Computational Complexity Conf. (CCC’05), pp. 275–284. IEEE Computer Society Press, 2005. [CCC:10.1109/CCC.2005.2].

[20]   Sergey Yekhanin: Locally decodable codes and private information retrieval schemes. PhD thesis, Massachusetts Institute of Technology, 2007.

[21]   Sergey Yekhanin: Towards 3-query locally decodable codes of subexponential length. In Proc. 39th STOC, pp. 266–274. ACM Press, 2007. [STOC:10.1145/1250790.1250830].