Pliable Index Coding
Sponsors:
Problem Statement and Motivation
- Index coding problem is a simplified version of broadcasting with side information at each receiver.
- Broadcasting with side information is a common scenario of transmission in today’s internet. Due to the rapidly decreasing cost of data storage, the side information at receivers becomes more relevant in the performance.
- Pliable index coding, where receivers request a type of information instead of a specific desired message, is a variant of index coding.
- Motivated by the observation that in some services the user does not ask for a specific message, but any message satisfying certain properties.
- Transmitter has some freedom to choose the desired messages. Thus there are more network coding opportunities.
Technical Approach
- Directed bipartite graph model for (linear) achievability analysis.
- Graph theoretical \ Combinatorial approach.
- Converse based on submodularity property of entropy function.
- Classical information theoretical approach.
Key Achievements and Future Goals
- For the case where the side information sets at each user are almost the same, the best linear scheme satisfies a constraint fraction of the existing users at each new transmission.
- Tang Liu, Daniela Tuninetti, “Pliable Index Coding: Novel Lower bound on the Fraction of Satisfied Clients with a Single Transmission and its Application,” ITW 2016.
-
For the same where users with all also possible side information sets with cardinality from a given set S are present in the system, linear codes are information theoretically optimal.
- Tang Liu and Daniela Tuninetti, “An Information Theoretic Converse for the Consecutive Complete–S PICOD Problem,” ITW 2018.
- Tang Liu and Daniela Tuninetti, “Information Theoretic Converse Proofs for some PICOD Problems,”ITW 2017.
-
Tang Liu, and Daniela Tuninetti, “Tight Information Theoretic Converse Results for some Pliable Index Coding Problems,” Preprint available at arXiv:1810.02451. Submitted October 2018 to IEEE Transactions on Information Theory (IT-18-0693).
- We have extended our tight converse results in arXiv:1810.02451 to the case where communication is decentralized / peer-to-peer (as opposed to the case where communication is from a central server).
- Tang Liu, and Daniela Tuninetti, “Decentralized Pliable Index Coding,” ISIT 2019.
- We have extended some of our tight converse results in arXiv:1810.02451 to the case where each user must decode one and only one file non in its side information, in other words, every file that is neither desired nor in the side information set must be kept private.
-
Tang Liu, and Daniela Tuninetti, “Private Pliable Index Coding,” ITW 2019. SUBMITTED.
-
