Sivakanth Gopi will present his Generals Monday, April 27, 2015 at 1pm in rm 401. His committee is as follows: Zeev Dvir (advisor), Sanjeev Arora, and Bob Tarjan. Everyone is invited to attend his talk, and those faculty wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below. ============================================ 2-Server PIR with sub-polynomial communication ------ A 2-server Private Information Retrieval (PIR) scheme allows a user to retrieve the i'th bit of an n-bit database replicated among two servers (which do not communicate) while not revealing any information about i to either server. The privacy of the user is information theoretic and does not rely on any cryptographic assumptions. In this work we construct a new 2-server PIR scheme with total communication cost sub polynomial in n. This improves over the currently known 2-server protocols which require n^{1/3} communication and matches the communication cost of known 3-server PIR schemes. Our improvement comes from reducing the number of servers in existing protocols, based on Matching Vector Codes, from 3 or 4 servers to 2. This is achieved by viewing these protocols in an algebraic way (using polynomial interpolation) and extending them using partial derivatives. Reading list: References [1] Sanjeev Arora and Boaz Barak. Computational complexity: a modern approach. Cambridge University Press, 2009. [2] Boaz Barak, Zeev Dvir, Amir Yehudayoff, and Avi Wigderson. Rank bounds for design matrices with applications to combinatorial geometry and locally correctable codes. In Proceedings of the forty-third annual ACM symposium on Theory of computing, pages 519–528. ACM, 2011. [3] Richard Beigel and Jun Tarui. On ACC [circuit complexity]. In Foundations of Computer Science, 1991. Proceedings., 32nd Annual Symposium on, pages 783–792. IEEE, 1991. [4] Benny Chor, Oded Goldreich, Eyal Kushilevitz, and Madhu Sudan. Private information retrieval. In FOCS, pages 41–50, 1995. [5] Zeev Dvir. Incidence theorems and their applications. Foundations and Trends R in Theoretical Computer Science, 6(4):257–393, 2010. [6] Zeev Dvir, Parikshit Gopalan, and Sergey Yekhanin. Matching vector codes. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 705–714. IEEE, 2010. [7] Klim Efremenko. 3-query locally decodable codes of subexponential length. In STOC, pages 39–44, 2009. [8] Jonathan Katz and Luca Trevisan. On the efficiency of local decoding procedures for error-correcting codes. In 32nd ACM Symposium on Theory of Computing (STOC), pages 80–86, 2000. [9] David A Mix Barrington, Richard Beigel, and Steven Rudich. Representing boolean functions as polynomials modulo composite numbers. In Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, pages 455–461. ACM, 1992. [10] Alexander A Razborov and Sergey Yekhanin. An Ω(n 1/3 ) lower bound for bilinear group based private information retrieval. In Foundations of Computer Science, 2006. FOCS’06. 47th Annual IEEE Symposium on, pages 739–748. IEEE, 2006. 1 [11] Gabor Tardos and DA Mix Barrington. A lower bound on the MOD 6 degree of the OR function. Computational Complexity, 7(2):99–108, 1998. [12] Sergey Yekhanin. Towards 3-query locally decodable codes of subexponential length. J. ACM, 55(1), 2008.