A Binary Randomized Coding Scheme for Pliable Index Coding with Multiple Requests
Linqi Song · 2018
In pliable index coding problem with multiple requests, a server has a set of messages to be transmitted to a set of users via a broadcast channel; each of the users has a subset of messages as side information and requests arbitrary t remaining messages. This problem has promising application prospect, for example, in distributed computing systems and content caching systems. In this paper, we propose a binary randomized coding scheme for this problem, where we first construct a block of transmission and then repeatedly use blocks of transmissions to construct the coding matrix. We show that our proposed randomized coding scheme achieves at most O(t log(n)+log2(n)) number of broadcast transmissions with high probability (i.e., 1-1/n) and thus the number of broadcast transmissions can be upper bounded by O(t log(n) + log2(n)), where n is the number of clients and each client requests t new messages among the unknown ones. This result matches the state-of-the-art upper bound of the deterministic algorithm and is better than the known randomized algorithm in the literature. In addition, we have a new upper bound for the pliable index coding problem with multiple requests case when each of the clients have equal number of side information.