Technical Program

Paper Detail

Paper Title Decentralized Pliable Index Coding
Paper IdentifierMO4.R2.4
Authors Tang Liu, Daniela Tuninetti, University of Illinois at Chicago, United States
Session Index Coding I
Location Saint Germain, Level 3
Session Time Monday, 08 July, 16:40 - 18:00
Presentation Time Monday, 08 July, 17:40 - 18:00
Manuscript  Click here to download the manuscript
Abstract This paper introduces the {\it decentralized} Pliable Index CODing (PICOD) problem: a variant of the Index Coding (IC) problem, where a central transmitter serves {\it pliable} users with message side information; here, pliable refers to the fact that a user is satisfied by decoding {\it any} $t$ messages that are not in its side information set. In the decentralized PICOD, a central transmitter with knowledge of all messages is not present, and instead users share among themselves massages that can only depend on their local side information set. This paper characterizes the capacity of two classes of decentralized \emph{complete--$S$} PICOD$(t)$ problems 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_{s\in S}\binom{m}{s}$, with no two users having the same side information set): (i) the \emph{consecutive case} $S=[\smin:\smax]$ for some $0 \leq \smin \leq \smax \leq m-\cardi$, and (ii) the \emph{complement-consecutive case} $S=[0:m-t]\backslash[\smin:\smax]$, for some $0 < \smin \leq \smax < m-\cardi$. Interestingly, the optimal code-length for the decentralized PICOD in those cases is the same as for the classical (centralized) PICOD counterpart, except when the problem is no longer pliable, that is, it reduces to an IC problem where every user needs to decode all messages not in its side information set. Although the optimal code-length may be the same in both centralized and decentralized settings, the actual optimal codes are not. For the decentralized PICOD, sparse Maximum Distance Separable (MDS) codes and vector linear index codes are required (as opposed to scalar linear codes).