UC Irvine

We study the capacity of the K-star-graph private information retrieval (PIR) problem introduced by Sadeh et al. The problem is so labeled because the storage graph corresponds to a star-graph with K edges (corresponding to the edges) and K + 1 vertices (corresponding to the servers): K messages are separately (one each) stored in K dedicated servers and meanwhile a universal server stores all K messages. While it is one of the simplest PIR settings to describe, the capacity CK of K-star-graph PIR is open for K ≥ 4. We study the critical K = 4 setting, for which prior work establishes the bounds 2/5 ≤ C4 ≤ 3/7. As our main contribution, we characterize the exact capacity of 4-star-graph PIR as C4 = 5/12, thus improving upon both the prior lower-bound as well as the prior upper-bound. The main technical challenge resides in the new converse bound, whose non-trivial structure is deduced indirectly from the achievable schemes that emerge from the study of a finer tradeoff between the download costs from the dedicated servers versus the universal server. A sharp characterization of this tradeoff is also obtained for K = 4. The connection of the PIR problem to caching and interference alignment indicates that our result may provide insight for these problems as well.