New Capacity Bounds for PIR on Graph and Multigraph-Based Replicated Storage

In this paper, we study the problem of private information retrieval PIR in both graph-based and multigraph-based replication systems, where each file is stored on exactly two servers, and any pair of servers shares at most $r$ files. We derive upper bounds on the PIR capacity for such systems an...