Tight Information Theoretic Converse Results for Some Pliable Index Coding Problems

摘要

This paper studies the Pliable Index CODing problem (PICOD), which models content-type distribution networks. In the PICOD ({t}) problem there are {m} messages, {n} users and each user has a distinct message side information set, as in the classical Index Coding problem (IC). Differently from IC, where each user has a pre-specified set of messages to decode, in the PICOD ({t}) a user is "pliable" and is satisfied if it can decode any {t} messages that are not in its side information set. The goal is to find a code with the shortest length that satisfies all the users. This flexibility in determining the desired message sets makes the PICOD ({t}) behave quite differently compared to the IC, and its analysis even more challenging. This paper mainly focuses on the complete- {S} PICOD ({t}) with {m} messages, where the set {S}subset [{m}] contains the sizes of the side information sets, and the number of users is {n}=sum _{sin {S}}inom {m} {s} , with no two users having the same side information set. Capacity results are shown for: (i) the consecutive complete- {S} PICOD ({t}) , where {S}=[{s}_{ext {min}}:{s}_{ext {max}}] for some 0 leqslant {s}_{ext {min}}leqslant {s}_{ext {max}} leqslant {m}-{t} , and (ii) the complement-consecutive complete- {S} PICOD ({t}) , where {S}=[0: {m}-{t}]ackslash [{s}_{ext {min}}:{s}_{ext {max}}] , for some 0 < {s}_{ext {min}}leqslant {s}_{ext {max}} < {m}-{t} . The novel converse proof is inspired by combinatorial design techniques and the key insight is to consider all messages that a user can eventually decode successfully, even those in excess of the {t} required ones. This allows one to circumvent the need to consider all possible desired message set assignments at the users in order to find the one that leads to the shortest code length. The core of the novel proof is to solve the critical complete- {S} PICOD ({t}) with {m} = 2{s}+{t} messages and {S}={{s}} , by showing the existence of a user who can decode {s}+{t} messages regardless of the desired message set assignment. All other tight converse results for the complete- {S} PICOD ({t}) can be deduced from this critical case. The converse results show the information theoretic optimality of simple linear coding schemes. By similar reasoning, all complete- {S} PICOD ({t}) where the number of messages is {m}leqslant 5 can be fully characterized. In addition, tight converse results are also shown for the PICOD(1) with circular-arc network topology hypergraph.