Pliable Index Coding: The multiple requests case

Abstract

The Pliable Index Coding problem is a recently proposed new formulation of the Index Coding problem where each client wants any one message that it does not have and the server tries to “satisfy” all the clients using the side information sets of each of the clients by broadcasting coded messages. We present two generalizations of the problem. Firstly, we consider the problem of each client requiring any t messages (t ≥ 1) that it does not have. If the cardinality of their side information sets is the same and there are n messages, then we show that O(min(t log n, t + log <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> n)) coded broadcast messages are sufficient. For t ≥ log n, this shows a linear dependence on t independent of n. We also develop simple approximation algorithms for the problem and evaluate their performance through simulations. Secondly, we consider the problem of the server having incomplete side information. If the server only knows the size s of the side information sets (assumed to be all equal), we show that there exists a linear code using min(s + 1, n - s) coded messages. We also show that this is tight for linear codes by proving a matching lower bound.