[talks] Sivakanth Gopi will present his Generals Monday, April 27, 2015 at 1pm in rm 401

[Nicki Gotsis]

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.