
Improved Private Information Retrieval Schemes from Matching Vectors and Derivatives
Swastik Kopparty, a mathematician at the University of Toronto, presents new results on Private Information Retrieval, a protocol letting a user fetch an entry from a database split across non-colluding servers without revealing which entry was accessed. He traces the line of work from Yekhanin (2007) through Efremenko (2009) and Dvir-Gopi (2014), which showed that PIR with just a few servers can be done with surprisingly small communication using polynomial methods and geometric configurations of vectors over composite moduli. Kopparty then introduces a simpler two-server scheme built on a different viewpoint of these constructions, one that generalizes to give superpolynomial improvements for nearly all numbers of servers. The headline result is a three-server scheme achieving communication cost exp((log n)^(1/3)), beating Efremenko's previous best of exp((log n)^(1/2)). Joint work with Fatemeh Ghasemi and Madhu Sudan, delivered as part of the IAS Computer Science/Discrete Mathematics seminar.