Skip to main content
eScholarship
Open Access Publications from the University of California

On the Necessity of Non-Shannon Information Inequalities for Storage Overhead Constrained PIR and Network Coding

Abstract

We show that to characterize the capacity of storage overhead constrained private information retrieval (PIR) with only 2 messages, and 2 databases, non-Shannon information inequalities are necessary. As a by-product of this result, we construct the smallest instance, to our knowledge, of a network coding capacity problem that requires non-Shannon inequalities.

Main Content
For improved accessibility of PDF content, download the file to your device.
Current View