2020 IEEE International Symposium
on Information Theory
21-26 June 2020 • Los Angeles, California, USA
| Paper ID | N.4.5 | ||
| Paper Title | Cache-Aided Scalar Linear Function Retrieval | ||
| Authors | Kai Wan, Technische Universität Berlin, Germany; Hua Sun, University of North Texas, United States; Mingyue Ji, University of Utah, Salt Lake City, United States; Daniela Tuninetti, University of Illinois at Chicago, United States; Giuseppe Caire, Technische Universität Berlin, Germany | ||
| Session | N.4: Coded Caching II | ||
| Presentation | Lecture | ||
| Track | Networking and Network Coding | ||
| Manuscript | Click here to download the manuscript | ||
| Virtual Presentation | Click here to watch in the Virtual Symposium | ||
| Abstract | In the shared-link coded caching problem, formulated by Maddah-Ali and Niesen (MAN), each cache-aided user demands one file (i.e., single file retrieval). This paper generalizes the MAN problem so as to allow users to request scalar linear functions of the files. This paper proposes a novel coded delivery scheme, based on MAN uncoded cache placement, that allows for the decoding of arbitrary scalar linear functions of the files (on arbitrary finite fields). Interestingly, and quite surprisingly, it is shown that the load for cache-aided scalar linear function retrieval depends on the number of linearly independent functions that are demanded, akin to the cache-aided single-file retrieval problem where the load depends on the number of distinct file requests. The proposed scheme is proved to be optimal under the constraint of uncoded cache placement, in terms of worst-case load, and within a factor 2 otherwise. | ||
Plan Ahead
2021 IEEE International Symposium on Information Theory
11-16 July 2021 | Melbourne, Victoria, Australia
