Technical Program

Paper Detail

Paper Title Pareto Optimal Schemes in Coded Caching
Paper IdentifierFR2.R1.3
Authors Vijith Kumar K P, Brijesh Kumar Rai, Tony Jacob, Indian Institute of Technology, Guwahati, India
Session Coded Caching IV
Location Le Théatre (Parterre), Level -1
Session Time Friday, 12 July, 11:40 - 13:00
Presentation Time Friday, 12 July, 12:20 - 12:40
Manuscript  Click here to download the manuscript
Abstract Maddah-Ali and Niesen, in a seminal work, initiated the study of rate memory tradeoff for a canonical cache network which operates via a placement phase and a delivery phase. While considering the case of placement phase being uncoded, Yu et al. proved the surprising result of the existence of a universal code, a code which is simultaneously optimal for all demand types. In this paper, we prove that universal codes do not exist when coding is permitted in the placement phase. As part of our proof, we introduce new kinds of lower bounds. In these lower bounds, instead of considering one demand type at a time, we consider several demand types simultaneously. These bounds give us better insight into how the performance for one demand type affects the performance for the other demand types. The non-existence of a universal scheme motivates us to introduce the notion of Pareto optimal schemes, and we prove that Chen’s scheme is Pareto optimal.