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

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

  • Author(s): Sun, Hua
  • Jafar, Syed
  • et al.

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
Current View