On an Equivalence Between Single-Server PIR with Side Information and Locally Recoverable Codes

Understand

Private Information Retrieval (PIR) problem has recently attracted a significant interest in the information-theory community.

• In this problem, a user wants to privately download one or more messages belonging to a database with copies stored on a single or multiple remote servers.
• In the single server scenario, the user must have prior side information, i.e., a subset of messages unknown to the server, to be able to privately retrieve the required messages in an efficient way.
• In the last decade, there has also been a significant interest in Locally Recoverable Codes (LRC), a class of storage codes in which each symbol can be recovered from a limited number of other symbols.