Prof Tuninetti’s ISIT 2021 tutorial on “Distributed Function Retrieval: a Storage and Privacy Prospective”

Prof. Tuninetti and collaborators Profs M. Ji and H. Sun have been selected to deliver the tutorial on "Distributed Function Retrieval: a Storage and Privacy Prospective" at the upcoming 2021 IEEE International Symposium on Information Theory (ISIT 2021), to be held (virtually) in Melbourne Australia in July 2021. The tutorial is tentatively scheduled for July 17th 2021.

Abstract: Modern algorithms need to efficiently execute complex queries on massive databases in a way that minimizes the use of communication resources while preserving the privacy of the entity that initiated the query. Such queries are functions of the data points that are stored at remote servers. For example, linear and multivariate polynomial operations are widely used fundamental primitives for building the complex queries that support on-line big-data analytics and data mining procedures. In those scenarios, it is too resource-consuming to download locally all the input variables in order to compute the desired output value. Instead, it is desirable to directly download the result of the desired output function, which should also be kept private. This tutorial introduces a principal and holistic framework for the problem of privately retrieving, at distributed cache-aided nodes, the output of functions based on both data that is locally computed and data that is received from multiple servers. This problem is at the intersection of distributed coded caching and private information retrieval. This tutorial has three major parts: (1) design optimal coded caching schemes for user-private general function retrieval; (2) motivated by distributed settings in which a user may also be a sender, devise optimal server-private function retrieval strategies; and (3) overcome complexity bottleneck in practical distributed computing systems with server- and/or user-privacy. The goal of this tutorial is to provide an overview of significant results on the topic, together with a comprehensive list of relevant past contributions for distributed coded caching and private information retrieval, and point to open research directions.