Pliable Index Coding

We formulate a new variant of the index coding problem, where instead of demanding a specific message, clients are pliable, and are interested in receiving any t messages that they do not have. We term this problem pliable index coding or PICOD(t). We prove that, with this formulation, although some instances of the problem become simple, in general, the problem of finding the optimal linear code remains NP-hard. However, we show that it is possible to construct pliable index codes that are substantially smaller than index codes in many cases. If there are n clients, the server has m messages, and each client has a side information set of cardinality s ≤ m - t; 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}) broadcast transmissions are sufficient to satisfy all the clients. For t = 1, this is an exponential improvement over the n messages required in index coding in the worst case (for m = n). In addition, for t ≫ log <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> n, the number of broadcast transmissions required is only linearly dependent on t. We generalize the results to instances where the side information sets are not necessarily of equal cardinality. When m = O(n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">δ</sup> ), for some constant δ > 0, we show that the codes of size O(min{t log <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> n, t log n + log <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">3</sup> n}) are sufficient in general. We also consider the scenario when the server only knows the cardinality of the side information sets of the clients and each client is interested in receiving any t messages that it does not have. We term this formulation oblivious pliable index coding or OB-PICOD(t). If the cardinalities of side information sets of all the clients is s (with s ≤ m - t), then we show that min{s + t, m - s} messages are both sufficient and necessary for linear codes. Finally, we develop efficient heuristic approximation algorithms for PICOD(t) and show through simulations on the random instances of PICOD(t) that they perform well in practice.