In pliable index coding (PICOD), a number of clients are connected via a noise-free broadcast channel to a server which has a list of messages. Each client has a unique subset of messages at the server as side-information, and requests for any one message not in the side-information. A PICOD scheme of length ℓ is a set of ℓ encoded transmissions broadcast from the server such that all clients are satisfied. Finding the optimal (minimum) length of PICOD and designing PICOD schemes that have small length are the fundamental questions in PICOD. In this paper, we use a hypergraph-based approach to derive new achievability and converse results for PICOD(t), where clients requesttnew messages (for somet≥ 1). We present a simple greedy algorithm for PICOD(1), termed DelGreedy, which gives an achievable linear scheme with length at most Δ(H), where Δ(H) is the maximum degree of any vertex in the hypergraphHthat represents the PICOD problem. We then extend this idea to obtain an achievable scheme for PICOD(t). We also give a lower bound for the optimal PICOD length using a new structural parameter associated with the PICOD hypergraph called the nesting number, denoted by η(H). While the nesting number bound is not stronger than previously known bounds, it can provide some computational advantages over them. Also, using the nesting number bound, we also obtain novel lower bounds for some PICOD problems with special structures, which are tight in some cases. We also characterize the optimal PICOD lengths for problems with Δ(H) ∈ {1, 2, 3}, and for problems with upto three clients. Further, we present a class of PICOD problems to show that the gap between the lower bound η(H) and the achievable PICOD length from DelGreedy algorithm can be arbitrarily large. Finally, we demonstrate the achievable PICOD lengths from our algorithms via simulations on randomly generated PICOD problems, and compare it with existing algorithms. We observe that DelGreedy performs better than some existing algorithms, while being worse than others, in terms of the code length achieved. Specifically, the greedy-cover based algorithm from a prior work of Brahma and Fragouli performs better, achieving lengths 1.5x-2x smaller than DelGreedy. However, the DelGreedy algorithm demonstrates 1.5x-3x faster running times than GRCOV, providing an alternative point in the rate-computation tradeoff of PICOD code design. These results extend to the PICOD(t) scenario also, with the improvements in computation-time over pre-existing algorithms being more dramatic in some cases.

In pliable index coding (PICOD), a number of clients are connected via a noise-free broadcast channel to a server which has a list of messages. Each client has a unique subset of messages at the server as side-information and requests for any one message not in the side-information. A PICOD scheme of length ℓ is a set of ℓ encoded transmissions broadcast from the server such that all clients are satisfied. Finding the optimal (minimum) length of PICOD and designing PICOD schemes that have small length are the fundamental questions in PICOD. In this paper, we use a hypergraph-based approach to derive new achievability and converse results for PICOD. We present an algorithm which gives an achievable scheme for PICOD with length at most $\Delta \left( \mathcal{H} \right)$, where $\Delta \left( \mathcal{H} \right)$ is the maximum degree of any vertex in a hypergraph that represents the PICOD problem. We also give a lower bound for the optimal PICOD length using a new structural parameter associated with the PICOD hypergraph called the nesting number. Finally, we also identify a class of problems for which our converse is tight. The full version of this paper, including additional results, proofs, and examples, is available online [1].