Congratulations to Dr Tang Liu

Tang Liu defended his PhD thesis "Pliable Index Coding" on Nov 19, 2019. Congratulations Dr Liu!

Abstract: The Pliable Index Coding (PICOD) problem is a variant of the Index Coding (IC) problem. The IC asks what is the minimum number of transmissions needed for a central server/transmitter to achieve the goal of communicated specific messages to each user/receiver who is equipped with message side information. In PICOD, users do not request specific messages, but instead are satisfied if they can decode any message that is not in their side information set. Our main results are as follows:

1. For the general PICOD, we show that at least a constant fraction of unsatisfied users can be satisfied by a single 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.
2. We derive tight information theoretic converse bounds for some classes of PICOD and show that linear codes are optimal. The converse bounds are derived by a novel technique rooted in combinatorics.
3. For the decentralized PICOD, where users exchange information among themselves (rather than being served by a central server, as in the points above), we show that for most cases the optimal number of transmissions is the same as in the centralized setting. The difference occurs only when the problem loses its pliability and reduces to the `data exchange problem'; in this case, we show that the cut-set bound is tight and can be achieved using decentralized vector linear index code.
4. We also introduce `individual message security' into PICOD, i.e., users are allowed to decode one and only one message outside their side information set. For the PICOD with circular-arc network hyper graph structure we show that some feasible centralized PICODs become unfeasible when security is introduced; when the size of the side information set is large, the optimal number of transmission is not affected by security (and is less than 2 transmissions), while when it is small the number of transmission scales with m/s (s is the size of side information and m the number of messages) which is essentially optimal under the constraints of linear codes.