Research

My research interests are in the area of information theory and coding, with a particular focus on coded caching. We looked into several aspects of optimal coded caching schemes as part of my doctoral thesis.

The idea of coded caching for content distribution networks was introduced by Maddah-Ali and Niesen, who considered an (N, K) cache network in which a server with N files, each of size F bits, is connected via a shared link with K users, each equipped with an isolated cache of size M F bits.

The network operates in two phases. In the first phase of coded caching, called the placement phase, the server fills the users’ caches with functions of its files, without any knowledge of the files that will be required by each user. In the second phase, called the delivery phase, after knowing the demands of all the users, the server broadcasts a set of packets over the shared link. Each user recovers the file it has requested from the broadcast packets, aided by its cache contents. The problem of coded caching is to determine how to fill each user’s cache in the placement phase so that the rate required in the delivery phase is minimized.

Maddah-Ali and Niesen, in their seminal work, considered a collection of demands where each file in the server is requested by at least one user. For this set of demands, they introduced a caching scheme in which each user’s cache is filled with uncoded file fragments and use multicast coding in the delivery phase. Though several new schemes were proposed to improve the achievable rates, the optimal rate memory tradeoff for this situation was not known except when M ≤ ¹⁄_K and M ≥ ^N⁄_K(K-1) . For the case ⌈^K+1⁄₂⌉ ≤ N ≤ K, we derive new lower bounds and propose a new coded caching scheme which leads to a characterizations of the optimal rate memory tradeoff when M ≤ ¹⁄_K + ¹⁄_K(N-1) and M ≥ ^N⁄_K(K-1) - ^N-1⁄_K(K-1) . For the case 1 ≤ N ≤ ⌈ ^K+1⁄₂⌉ , we derive new lower bounds which leads to a characterization of the optimal rate memory tradeoff for M ≥ ^N ⁄ _K (K-2)^[1-5].

The problem of coded caching is fundamentally a multi-objective optimization problem, as noted by Tian, who initiated a study of the optimal rate memory tradeoff for each demand type. In a surprising result, Yu, Maddah-Ali, and Avestimehr proposed a coding scheme that was simultaneously optimal for all demand types among caching schemes where the placement phase is restricted to be uncoded. In the broader scenario, where coding is also permitted during the placement phase, we analyze the feasibility of such a universal scheme. We developed new lower bounds that characterized the constraints among various demand types and used them to demonstrate the non-existence of a universal scheme. We began a study of Pareto optimal schemes in coded caching as a result of this conclusion, and we established the Pareto optimality of some of the known caching schemes ^[6,7].

References

1. K. P. Vijith Kumar, B. K. Rai, and T. Jacob, “Towards the exact rate memory tradeoff in coded caching,” in National Conference on Communications, IEEE, 2019, pp. 1–6.
2. K. P. Vijith Kumar, B. K. Rai, and T. Jacob, “Fundamental limits ofcoded caching: The memory rate pair (K-1-1/K, 1/(K-1)),” in Interna-tional Symposium on Information Theory, IEEE, 2019, pp. 2624–2628
3. K. P. Vijith Kumar, B. K. Rai, and T. Jacob, “Towards the exact memory rate tradeoff for the (4, 5) cache network,” in International Conference on Signal Processing and Communications, IEEE, 2020, pp. 1-5.
4. K. P. Vijith Kumar, B. K. Rai, and T. Jacob, “The exact rate memory tradeoff for small caches with coded placement,” arXiv preprint arXiv:2102.04797, 2021.
5. K. P. Vijith Kumar, B. K. Rai, and T. Jacob, “The exact rate memory tradeoff for large caches with coded placement,” arXiv preprint arXiv:2101.09785, 2021.
6. K. P. Vijith Kumar, B. K. Rai, and T. Jacob, “Pareto optimal schemesin coded caching,” in International Symposium on Information Theory, IEEE, 2019, pp. 2629–2633.
7. K. P. Vijith Kumar, B. K. Rai, and T. Jacob, “Pareto optimal schemes in coded caching: Uncoded prefetching,” in International Symposium on Information Theory, IEEE, 2021, pp. 2537-2541.