On the Computational Aspect of Coded Caching With Uncoded Prefetching

Coded caching is the distribution of content across a communication system using techniques from coding theory in order to create multicasting opportunities among the users receiving the content. This enables a multiplicative improvement over the classic uncoded caching with respect to the transmission rates required in the delivery phase of the content. Since its introduction, coded caching has eliceted significant research interest as a result of which several different schemes have been proposed over the last few years. This work focuses on the fundamental case of coded caching with uncoded prefetching. In this case, the users' caches are filled with uncoded content during a prefetching phase in order to best serve the request made by each user during a subsequent delivery phase. This important case has recently received a complete information-theoretic characterization. However, reaching the information-theoretic optimality imposes a significant computational imbalance among the users. To mitigate this imbalance, we perform a complete computational analysis of the two major forms of coded caching with uncoded prefetching, namely centralized and decentralized. Furthermore, we propose a new information-theoretically optimal method for the delivery phase that achieves a significant computational improvement compared to the state of the art.

Automated summary

Coded caching is a method of distributing content across a communication system using coding theory to enable multicasting opportunities among users. This work focuses on the fundamental case of coded caching with uncoded prefetching and proposes a new information-theoretically optimal method for the delivery phase, achieving significant computational improvement. It also performs a complete computational analysis of centralized and decentralized forms of coded caching with uncoded prefetching.