References & Further Reading

References

1. R. Tajeddine and S. El Rouayheb, Private Information Retrieval from MDS Coded Data in Distributed Storage Systems, 2018

   Coded-storage PIR capacity. The headline result of §14.1.

2. H. Sun and S. A. Jafar, The Capacity of Private Information Retrieval with Colluding Databases, 2018

   $T$-colluding PIR capacity. The headline result of §14.2.

3. H. Sun and S. A. Jafar, The Capacity of Symmetric Private Information Retrieval, 2018

   SPIR capacity result ($1 - 1/N$). The headline result of §14.3.

4. Q. Wang and M. Skoglund, Symmetric Private Information Retrieval from MDS Coded Distributed Storage, 2019

   SPIR with coded storage. Used in §14.4.

5. R. Freij-Hollanti, O. W. Gnilke, C. Hollanti, and D. Karpuk, Private Information Retrieval from Coded Databases with Colluding Servers, 2017

   Joint coded-storage + $T$-colluding PIR. The headline result of §14.4.

6. H. Sun and S. A. Jafar, The Capacity of Private Information Retrieval, 2017

   Foundational classical PIR capacity result (Chapter 13). Reference for the $T = 1$ special case.

7. Y. Gertner, Y. Ishai, E. Kushilevitz, and T. Malkin, Protecting Data Privacy in Private Information Retrieval Schemes, 1998

   Original SPIR formulation. Historical reference; capacity was settled later by Sun-Jafar 2018c.

8. K. Banawan and S. Ulukus, The Capacity of Private Information Retrieval from Coded Databases, 2018

   Alternative converse for coded-storage PIR. Useful complement to Tajeddine-El Rouayheb.

9. Z. Jia, H. Sun, and S. A. Jafar, Cross Subspace Alignment and the Capacity of Coded Distributed Computing, 2019

   New techniques for joint coded-storage + $T$-colluding PIR. Narrows the open gap for §14.4.

10. C. Tian, H. Sun, and J. Chen, Capacity-Achieving Private Information Retrieval Codes with Optimal Message Size and Upload Cost, 2019

    Reduced upload cost for capacity-achieving PIR. Practical refinements.

11. Y.-P. Wei, K. Banawan, and S. Ulukus, Private Information Retrieval With Side Information, 2019

    PIR with side information at the user. Forward reference to Chapter 15.

12. N. Raviv and I. Tamo, Private Information Retrieval is Graph-Based Replication Systems, 2018

    Graph-theoretic perspective on partial replication PIR.

Further Reading

• Coded-storage PIR — full treatment

  Tajeddine & El Rouayheb, IEEE T-IT 2018

  Full proof of the coded-storage PIR capacity. Includes the achievability scheme construction.

• $T$-colluding PIR — full treatment

  Sun & Jafar, IEEE T-IT 2018

  Full proof of the $T$-colluding PIR capacity. Includes the Shamir-based achievability.

• Joint coded-$T$ PIR — open problems

  Freij-Hollanti et al., SIAM J. AAG 2017; Banawan & Ulukus, IEEE T-IT 2018

  Two perspectives on the joint capacity: achievability via novel codes (Freij-Hollanti) and an alternative converse (Banawan-Ulukus). Both useful for understanding the gap.

• SPIR foundations and history

  Gertner et al., STOC 1998; Sun & Jafar, IEEE T-IT 2018c

  SPIR's origin and modern capacity. The $1 - 1/N$ formula is non-obvious and the proof is instructive.

• PIR survey of variants

  Banawan & Ulukus, *Private Information Retrieval and Beyond*, Foundations and Trends in Comm. and Inf. Theory, 2023

  Comprehensive treatment of all PIR variants in the post-Sun-Jafar era. Organizing reference for Chapters 13-15.