# Private Information Retrieval on Multigraph-Based Replicated Storage

arXiv: https://arxiv.org/abs/2501.17845 · HTML: https://mlsanity.com/paper/2501.17845/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Jan 2025.

## Built on by (most cited first, 1 of 1)

- [What If, But Privately: Private Counterfactual Retrieval](https://mlsanity.com/paper/2508.03681/) (2025)

## Abstract (arXiv)

We consider the private information retrieval (PIR) problem for a multigraph-based replication system, where each set of r files is stored on two of the servers according to an underlying r-multigraph. Our goal is to establish upper and lower bounds on the PIR capacity of the r-multigraph. Specifically, we first propose a construction for multigraph-based PIR systems that leverages the symmetry of the underlying graph-based PIR scheme, deriving a capacity lower bound for such multigraphs. Then, we establish a general upper bound using linear programming, expressed as a function of the underlying graph parameters. Our bounds are demonstrated to be tight for PIR systems on multipaths for even number of vertices.