References & Further Reading

References

1. S. Mukhopadhyay and N. Karamchandani, Online Coded Caching: Regret Bounds for Dynamic Demand, 2022

   Foundational paper for online coded caching. Establishes the $\sqrt{T K \log N}$ and $\log T$ regret bounds.

2. M. A. Maddah-Ali and U. Niesen, Fundamental Limits of Caching, 2014

   MAN baseline; offline reference for regret analysis.

3. D. D. Sleator and R. E. Tarjan, Amortized Efficiency of List Update and Paging Rules, 1985

   Classical LRU competitive analysis. Foundation for §20.3.

4. O. Besbes, Y. Gur, and A. Zeevi, Non-Stationary Stochastic Optimization, 2015

   Dynamic regret bounds for non-stationary environments. Basis for §20.4.

5. A. R. Karlin, M. S. Manasse, L. Rudolph, D. D. Sleator, Competitive Snoopy Caching, 1988

   Classical multi-cache online analysis. Relevant for competitive ratio comparison.

6. L. Breslau, P. Cao, L. Fan, G. Phillips, S. Shenker, Web Caching and Zipf-like Distributions: Evidence and Implications, 1999

   Empirical demonstration that web demand follows Zipf. Relevant for stochastic regret setup.

7. G. Calinescu, V. Chvatal, A Survey of Online Paging, 1998

   Survey of online paging literature.

8. G. Einziger and R. Friedman, TinyLFU: A Highly Efficient Cache Admission Policy, 2017

   TinyLFU policy (used in Caffeine library). Modern LRU variant.

9. N. Cesa-Bianchi and G. Lugosi, Prediction, Learning, and Games, 2006

   Canonical textbook for online learning / FTPL analysis.

10. E. Hazan, Introduction to Online Convex Optimization (2nd ed.), 2022

    Modern reference for online convex optimization. Foundations for §20.2.

11. D. Bhattacharjee and A. Sinha, Online Caching with Optimistic Regret Bounds, 2023

    Recent improvements on online coded caching.

12. E. R. Berlekamp, Algebraic Coding Theory, 1968

    Classical coding theory (Reed-Solomon etc.); relevant for coded-caching coding-theoretic grounding.

Further Reading

• Online coded caching main paper

  Mukhopadhyay, Karamchandani (2022). 'Online Coded Caching: Regret Bounds'

  Core paper for Ch 20. Proofs of all regret bounds.

• Online learning textbook

  Hazan (2022). 'Introduction to Online Convex Optimization (2nd ed.)'

  Underlying theory for FTPL / online algorithms.

• Web caching empirical

  Breslau et al. (1999). 'Web Caching and Zipf-like Distributions'

  Empirical basis for Zipf-popularity assumptions in theory.

• Modern cache replacement

  Einziger, Friedman (2017). 'TinyLFU,' ACM TOS

  State-of-the-art practical cache admission policy.