Technical Program

Paper Detail

Paper IDN.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

Visit Website!