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.