LECTURES A GRATIS GLOBAL SERVICE
⌕ SEARCH GRATIS GLOBAL ↗
LECTURES
Improved Private Information Retrieval Schemes from Matching Vectors and Derivatives
SOURCE: YOUTUBE · NO TRACKING UNTIL YOU PRESS PLAY · TROUBLE PLAYING? WATCH AT THE SOURCE ↗

Improved Private Information Retrieval Schemes from Matching Vectors and Derivatives

79 MIN · EN · STATUS: [ STREAMING ]
RATE THIS
IAS

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.

At a glance

Lecture facts

Runtime compared with the other 734 Mathematics lectures
Runtime1 h 19 m
Compared with MathematicsLonger than 75%
Source channelInstitute for Advanced Study (YouTube)