A General Coded Caching Scheme for Scalar Linear Function Retrieval
Yinbin Ma, Daniela Tuninetti · IEEE Journal on Selected Areas in Information Theory · 2022
Coded caching aims to minimize the network’s peak-time communication load by leveraging the information pre-stored in the local caches at the users. The original setting by Maddah-Ali and Niesen, which considered single file retrieval, has been recently extended to general Scalar Linear Function Retrieval (SLFR) by Wanet al., who proposed a linear scheme that surprisingly achieves the same optimal load under the constraint of uncoded cache placement as in single file retrieval. This paper’s goal is to characterize the conditions under which a general SLFR linear scheme is optimal and gain insights into why the specific choices made by Wanet al.work. This paper shows that the optimal decoding coefficients are necessarily the product of two terms, one only involving the encoding coefficients and the other only the demands of the users. In addition, the algebraic relationships among the encoding coefficients of an optimal code are shown to be captured by the cycles of auniversal graph. Thus, a general linear scheme for the SLFR problem can be found by solving a spanning tree problem for the universal graph. The proposed framework readily extends to caching-like problems, such as the problem of finding a general linear scheme for Sunet al.’s private function computation.