Pliable Index Coding Problem

The Pliable Index Coding (PICOD) problem is a variant of the Index Coding (IC) problem. The IC consists of one transmitter/server and several users/clients. The transmitter and users are connected by a shared noiseless broadcast channel. Each user has a subset of the messages as its side information set and requests some messages that are not in its side information set. The transmitter has all the messages and knows the side information sets of all users. The transmitter serves all users by sending a codeword through the noiseless broadcast channel. The codeword is encoded by the transmitter based on the message set and the side information sets at all users. The goal for the transmitter is to send a codeword such that all users are able to decode their desired messages. For the IC we seek to determine the minimum number of transmissions needed for the transmitter to achieve this goal. In many practical scenarios, such as network streaming or Internet advertising, the desired messages are not always fixed. The transmitter is thus able to leverage this pliability to reduce the communication cost. The PICOD is a variant of the IC model which captures this idea. In the PICOD users do not request specific messages. Instead, they are satisfied by receiving messages that are not in their side information sets. This pliability provides more encoding opportunities, thus can potentially reduce the number of transmissions. For the general PICOD problem, we show that at least a constant fraction of users can be satisfied by one transmission. We provide a constructive way to find the codeword and the users that can be satisfied by one transmission. This shows that the number of transmissions for any PICOD is upper bounded by $O(\log^2 (n))$, where $n$ is the number of users in the system. We also derive information theoretic converse bounds for some cases of PICOD, shows that these bounds can be achieved by the linear codes. The converse bounds are derived by novel techniques based on combinatorics and are the first non-trivial information theoretical converse results that are tight for a large class of the PICOD problems. We then study the decentralized PICOD problem, where the codewords are generated by the users based on their own side information set. This model is motivated by decentralized networks such as distributed computation system and Internet of Things networks. In these networks communication occurs in a decentralized fashion without a central controller. For the cases with information theoretical optimality in the centralized setting, we surprisingly find that the optimal number of transmissions remains the same in the decentralized, except when the problem loses its pliability. When the problem is no long pliable, we show that the cut-set bound is tight and can be achieved using decentralized vector linear index codes. Lastly, we put the security constraints into the PICOD problem. Security and privacy are some of the major concerns in today's communication networks. Information theoretical security guarantees of security and privacy in the situations where information can be leaked to undesired parties. Different from computational security, which replies on the fact that certain problems are considered hard to solve, information theoretical security is robust against all possible attacks, regardless of the computation capability of the attacker. For the PICOD with security constraint, we look at the problem where all users are allowed to decode one and only one message and the side information structure is a circular-arc hypergraph where all users have the same size of the side information sets. We show that the optimal number of transmissions does not change when the size of side information set is large compared to the number of messages in the system. However, it changes dramatically when the size of side information set is small. Specifically, when $s