The Exact Rate Memory Tradeoff for Small Caches with Coded Placement

• Published in: arXiv.org 2021-02
• Main Authors: Vijith Kumar K P, Rai, Brijesh Kumar, Jacob, Tony
• Format: Article
• Language: English
• Subjects: Caching; Lower bounds; Tradeoffs
• ISSN: 2331-8422

The idea of coded caching was introduced by Maddah-Ali and Niesen who demonstrated the advantages of coding in caching problems. To capture the essence of the problem, they introduced the \((N, K)\) canonical cache network in which \(K\) users with independent caches of size \(M\) request files from a server that has \(N\) files. Among other results, the caching scheme and lower bounds proposed by them led to a characterization of the exact rate memory tradeoff when \(M\geq \frac{N}{K}(K-1)\). These lower bounds along with the caching scheme proposed by Chen et al. led to a characterization of the exact rate memory tradeoff when \(M\leq \frac{1}{K}\). In this paper we focus on small caches where \(M\in \left[0,\frac{N}{K}\right]\) and derive new lower bounds. For the case when \(\big\lceil\frac{K+1}{2}\big\rceil\leq N \leq K\) and \(M\in \big[\frac{1}{K},\frac{N}{K(N-1)}\big]\), our lower bounds demonstrate that the caching scheme introduced by G{ó}mez-Vilardeb{ó} is optimal and thus extend the characterization of the exact rate memory tradeoff. For the case \(1\leq N\leq \big\lceil\frac{K+1}{2}\big\rceil\), we show that the new lower bounds improve upon the previously known lower bounds.