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 > log(2) 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(delta)), for some constant delta > 0, we show that the codes of size O(min{t log(2) n, t log n + log(3) 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