Sennur Ulukus's full lecture at the 2020 European School of Information Theory Stuttgart, Germany
Private information retrieval (PIR) refers to the problem of retrieving a file (a message) out of M messages from N distributed databases in such a way that no individual database can tell which message has been retrieved, hence the name, “private” information retrieval. PIR has originated in the computer science literature in late 1990s and has been revisited by the information theory community recently. Information-theoretic reformulation of the problem defines the “PIR capacity” as the largest number of bits that can be retrieved privately per download, equivalently, the smallest number of downloads needed per bit of privately retrieved information. In this talk, I will describe the problem, summarize break-through results in the history of the problem, and present some recent results. The talk will be self-contained; no prior information is needed.