Group Complete-$\{s\}$ Pliable Index Coding

Index Coding [1] is a multicast problem where a single server conveys messages to several receivers over a noiseless broadcast channel. The problem is studied under the premise that each receiver has a subset of messages as side information and demands a specific message that is not in its side information. In a flexible variant of the problem called pliable index coding [2] (abbreviated usually as PICOD($t$)), receivers do not demand specific messages. Instead, each receiver is satisfied upon decoding any $t$ messages not in its side information. Both problem formulations seek the shortest normalized broadcast length and a corresponding optimal code.

Finding optimal linear codes for index coding and PICOD($t$) problems is NP-hard [1, 2]. Despite this pessimistic result, index coding remains an active research area with results in two broad clusters: the design of index codes, and establishing fundamental limits on optimal index code length.

An index-coding problem is completely characterized by the side information of the receivers and the message(s) they demand. A problem can thus be captured by a directed graph where the nodes represent the message indices. Using this graph representation, index codes have been designed based on the graph components (cycles [3], cliques [4], partial cliques [4], interlinked cycles [5]) or its coloring [6]. Coloring of confusion graphs, where each node represents a realization of the messages, has also been used to design codes [4, 7]; it must be remarked that the size of confusion graphs grows exponentially with the message size. Besides graph-based approaches, codes based on random-coding arguments have also been devised [8]. In [9], matroid theory was used to show impossibility of optimal linear codes over fields with characteristic three, and optimal non-linear codes for small instances of the problem were explicitly constructed.

The graph representation of an index-coding problem allows us to not only design codes, but also converse results. Specifically, the size of a maximum acyclic induced subgraph (MAIS) is a lower bound to the optimal index code length [1]. Another approach to deriving converse results uses Shannon-type information inequalities, and this is referred to as the polymatroid lower bound [8].

Designing codes for the PICOD problem, on the other hand, took very different approaches: the code construction is mostly algorithmic. Two algorithmic coding schemes with proven bounds are as follows: Brahma and Fragouli [2] proposed a randomized coding scheme which constructs codes of length $O(\min\{t\log^{2}{n},t\log{n}+\log^{3}{n}\})$ if $m=O(n^{\delta})$, where $n$ is the number of receivers and $m$ is the number of messages; Song et al. [10] utilized a greedy approach to construct codes whose length is bounded from above by $O(t\log{n}+\log^{2}{n})$.

Further, algorithmic coding schemes without established theoretical upper bounds have been developed. Such algorithms typically produce codes of shorter average lengths than those produced by the previously mentioned algorithms. For instance, the Greedy Cover algorithm [2] constructs subsets of messages (that are jointly coded) by greedily and sequentially selecting a message that maximizes its utility. An improved variation of this algorithm was recently proposed in [11]. Krishnan et al. [12] used a graph-based method to construct codes for PICOD($t$) problems. Their coding scheme involves a $t$-fold conflict-free coloring of the vertices of a hypergraph associated with the PICOD($t$).

Lower bounds for PICOD(1) were derived based on receivers that are absent in the problems [13]. Although this approach builds on the concept of MAIS lower bound for index coding, the result is expressed in terms of how a side-information set intersects or contains another. The lower bounds are tight for special side-information configurations and for all problems with up to four absent receivers [14].

Other studies focused on devising optimal coding schemes for specific classes of PICOD($t$) problems. Liu and Tuninetti [15] investigated a subset of PICOD($t$) problems known as complete-$S$ problems. In these problems, every size $s$ subset of $m$ messages where $s\in S$ serves as the side information for a receiver. Optimal code length has been found for two classes of complete-$S$ problems: $S=\{s_{\text{min}},\dotsc,s_{\text{max}}\}$ or $S=\{0,\dotsc,s_{\text{min}}-1\}\cup\{s_{\text{max}}+1,\dotsc,m-1\}$, for any $s_{\text{min}}\leq s_{\text{max}}$. For these two classes, an optimal code either conveys messages in an uncoded fashion or is an MDS code (based on partial clique for index coding). The matching converse is mainly based on MAIS.

In this work, we consider a generalization of complete-$S$ PICOD($t$). Our generalization is termed $g$-group complete-$S$ PICOD($t$) problem where there are $m$ groups each of $g$ messages, and every receiver that has $s$ groups where $s\in S$ is present in the problem. In total, there are $\sum_{s\in S}\binom{m}{s}$ receivers. Our work focuses on the singleton $S=\{s\}$ case where $1\leq s\leq m$. We first present a multi-stage coding scheme that uses the ingredients of code design that are optimal in the ungrouped complete-$S$ setting. The scheme is shown to be optimal for $t>(g-1)(m-s)$. For $t\leq(g-1)(m-s)$, we establish that the scheme is optimal among all broadcast codes. Our results builds on and subsumes those of Liu and Tuninetti for the singleton S when we set $g=1$ [15].

This paper is organized as follows. Section II formally presents the group complete PICOD problem, Section III presents the notation used in the problem and discusses the tools and relevant graph-theoretical results used in this work, Section IV presents our achievability, converse, and pertinent ancillary results. Most proofs are relegated to the supplementary appendix document.

The Pliable Index Coding (PICOD($t$)) problem consists of the following components:

• •

  A server possesses $m$ i.i.d messages $X_{1},X_{2},\ldots,X_{m}$ each of which take values in $\mathbbm{F}^{L}$, where $\mathbbm{F}$ is a finite field, and $L$ is the number of symbols of $\mathbbm{F}$ in each message.

• •

  $n$ receivers that each have a subset of $m$ messages (known as side information), and request any additional $t$ messages not in their side information. Without loss of generality, we may assume that each receiver has at most $m-t$ messages in the side information.

The goal of the PICOD($t$) problem is to design strategies for the server to compress the $m$ messages into an index that is broadcast over a noiseless channel to meet the receiver demands. A specific class of PICOD($t$) problems known as complete-$S$ PICOD($t$) problem was introduced in [15]. In this formulation, $S\subseteq\{1,2,\ldots,m-t\}$ defines the receivers and their side information as follows:

• •

  For each $s\in S$, there are $\binom{m}{s}$ receivers each with a distinct subset of size $s$ of messages as side information. We denote the side information of node $r$ as $\mathcal{M}_{r}$.

• •

  In total, there are $\sum_{s\in S}\binom{m}{s}$ receivers.

For example, if $m=3$, $t=1$ and $S=\{1,2\}$, then the complete-$S$ PICOD($t$) problem with $3$ messages consists of $\binom{3}{1}+\binom{3}{2}=6$ receivers $r_{1},\ldots,r_{6}$ with side-information subsets $\mathcal{M}_{r_{1}}=\{X_{1}\}$, $\mathcal{M}_{r_{2}}=\{X_{2}\}$, $\mathcal{M}_{r_{3}}=\{X_{3}\}$, $\mathcal{M}_{r_{4}}=\{X_{1},X_{2}\}$, $\mathcal{M}_{r_{5}}=\{X_{1},X_{3}\}$, and $\mathcal{M}_{r_{6}}=\{X_{2},X_{3}\}$, respectively. Since $t=1$, each receiver wants an additional message that it does not already know.

This work focuses on a generalization of the complete-$S$ PICOD($t$) problem, referred to as $g$-Group Complete-$S$ PICOD($t$) problem with $m$ groups defined as follows:

• •

  There are $mg$ messages partitioned into $m$ groups of $g$ messages each. The groupings are given by $\mathcal{G}_{i}=\{X_{(i-1)g+1},\ldots,X_{ig}\}$, $i=1,\ldots,m$.

• •

  $S\subseteq\{1,\ldots,\lfloor\frac{mg-t}{g}\rfloor\}$ defines the number and side information of the receivers in the problem instance. For every $s\in S$, there are $\binom{m}{s}$ receivers each with $s$ groups as side information. The set of all $\sum_{s\in S}\binom{m}{s}$ receivers in the problem is denoted by $\mathfrak{R}$.

  For example, if $m=3$, $g=2$ $S=\{1,2\}$, then the problem has $\binom{3}{1}+\binom{3}{2}$ receivers. The side information of the six receivers $r_{1},\ldots,r_{6}$ are $\mathcal{M}_{r_{1}}=\mathcal{G}_{1}$, $\mathcal{M}_{r_{2}}=\mathcal{G}_{2}$, $\mathcal{M}_{r_{3}}=\mathcal{G}_{3}$, $\mathcal{M}_{r_{4}}=\mathcal{G}_{1}\cup\mathcal{G}_{2}$, $\mathcal{M}_{r_{5}}=\mathcal{G}_{1}\cup\mathcal{G}_{3}$, and $\mathcal{M}_{r_{6}}=\mathcal{G}_{2}\cup\mathcal{G}_{3}$ respectively. Observe that the receivers either have 2 messages (1 group) or 4 messages (2 groups) in their side information.

• •

  Each receiver requests $t$ extra messages that is not in its side information.

Note that if we choose $g=1$, our $g$-group complete-$S$ formulation reverts back to the complete-$S$ setup of [15]. Even though the receiver demands are pliable, the server has to select which $t$ messages to communicate to which receiver. This is done through decoding choice (function) $\mathcal{D}:\mathfrak{R}\rightarrow 2^{\llbracket mg\rrbracket}$ with $|\mathcal{D}(r)|=t$ for each $r\in\mathfrak{R}$. Throughout this paper, we use the notation that $\llbracket m\rrbracket$ as a shorthand for $\{1,2,\ldots,m\}$ for any natural number $m$, and for a set $X$, $2^{X}$ denotes the power set of $X$.

For the sake of analysis, it is sometimes useful to relax the condition that the decoding choice for each receiver is precisely $t$ messages. It is therefore convenient to define a generalized decoding choice that assigns at least $t$ messages to each receiver. Thus, a generalized decoding choice is a function $\mathcal{D}:\mathfrak{R}\rightarrow 2^{\llbracket mg\rrbracket}$, where $|\mathcal{D}(r)|\geq t$ for each $r\in\mathfrak{R}$.

Given a PICOD problem, the server selects a decoding choice $\mathcal{D}$, and a pliable index code $C$ that works for this choice, whose details are as follows:

• •

  $C$ comprises of an encoding function $\mathbbm{E}:\left(\mathbb{F}^{L}\right)^{mg}\rightarrow\mathbbm{F}^{\ell}$ that the server uses to jointly encode the $mg$ messages and convey $l$ symbols of $\mathbbm{F}$ to each receiver. The encoder transmits $\mathbbm{E}(X_{1},\ldots,X_{mg})$ to all receivers noiselessly. The normalized size $\frac{\ell}{L}$ is termed the rate $R_{C}$ of the code.

• •

  Each receiver $r\in\mathfrak{R}$, $C$ comprises of a decoding function $\mathbbm{D}_{r}:\mathbbm{F}^{\ell}\times\left(\mathbbm{F}^{L}\right)^{\kappa_{r}}\rightarrow\left(\mathbbm{F}^{L}\right)^{t}$, where $\kappa_{r}$ denotes the number of messages in the side information of receiver $r$. Each receiver $r\in\mathfrak{R}$, uses the decoding function $\mathbbm{D}_{r}$ with the broadcast encoded message $\mathbbm{E}(X_{1},\ldots,X_{mg})$ along with its side information to decode the $t$ messages in $\mathcal{D}(r)$, i.e., $\{X_{j}:j\in\mathcal{D}(r)\}$.

In this work, we focus solely on the canonical singleton setting of $g$-group complete-$S$ PICOD($t$) where $S=\{s\}$ for $s\in\llbracket\lfloor\frac{mg-t}{g}\rfloor\rrbracket$. In this problem setting, there are $\binom{m}{s}$ receivers each with $s$ groups of messages in its side information. The goal is to identify the optimal broadcast rate $R^{*}(m,s,g,t)$ that is the least among all pliable index codes, i.e.,

As in previous works, non-achievability (lower bound) results are shown predominantly using graph-theoretic arguments with a heavy use of the maximum acyclic induced subgraph (MAIS) bound [1]. We therefore first describe our notation for the graph representation. Given a $g$-group complete-$\{s\}$ PICOD($t$) problem with $m$ groups, and once a particular decoding choice $\mathcal{D}$ is selected, we can represent the resulting index coding problem as a directed graph $G_{\mathcal{D}}$ with $t\binom{m}{s}$ nodes using the following two rules:

• R1

  A receiver $r$ with side information $\mathcal{M}_{r}=\cup_{\ell=1}^{s}\mathcal{G}_{i_{\ell}}$ that requests messages $\mathcal{D}(r)=\{j_{1},\ldots,j_{t}\}$ is represented by $t$ separate nodes labelled as $(r,j_{1}),(r,j_{2}),\ldots,(r,j_{t})$.

• R2

  A directed edge from node $(r,j)$ to $(r^{\prime},j^{\prime})$ exists in $G_{\mathcal{D}}$ iff $X_{j^{\prime}}\in\mathcal{M}_{r}$, i.e., the node $(r,j)$ represents a receiver whose side information contains $X_{j^{\prime}}$.

In this digraph representation, a node $(r,j)$ is said to have receiver label $r$, and (decoded) message label $j$. Conversely, given a receiver $r$ and a message index $j\in\mathcal{D}(r)$, we view $(r,j)$ as one of the $t$ distinct node representations of $r$.

In the ungrouped ($g=1$) case, a receiver $r=\{i_{1},\ldots,i_{s}\}$ that recovers $t$ messages has the side information of $\binom{t+s}{s}-1$ other receivers, and can therefore emulate them. Here, by emulate, we mean the receiver $r$ can possibly decode more messages by use of the decoding function of any other receiver whose side information it possesses after decoding its $t$ messages. This can be done iteratively until the receiver $r$ can emulate no more receivers. In the grouped case, it is not necessary that a node can emulate another upon decoding its $t$ messages. Instead, a receiver $r$ can emulate another receiver $r^{\prime}$ upon decoding its $t$ messages iff the messages exclusive to the side information of $r^{\prime}$ is decoded by $r$, i.e., $\mathcal{M}_{r^{\prime}}\setminus\mathcal{M}_{r}\in\mathcal{D}(r)$. Therefore, a necessary and sufficient condition for $r$ to emulate another receiver is that $\mathcal{D}(r)$ contain at least another full group.

One of the key benefits of this digraph representation is that it allows us to focus on the sizes of acyclic induced subgraphs of $G_{\mathcal{D}}$ to bound from below the rate for the PICOD$(t)$ problem. In fact, the best such lower bound is given by the size of the maximum acyclic induced subgraph with distinct message labels [1]. In this work, we denote $\texttt{MAIS}(G_{\mathcal{D}})$ to be any one maximum acyclic induced subgraph of $G_{\mathcal{D}}$ with distinct message labels, and let $|\texttt{MAIS}(G_{\mathcal{D}})|$ to be its size. Given a PICOD problem, a decoding choice $\mathcal{D}$, and an MAIS $G$ in $G_{\mathcal{D}}$, we will find it handy to organize $G$ in layers based on the following rules:

• R1^′

  Layer 1, denoted by $\mathcal{L}_{1}$, consists of nodes of $G$ that are sources (i.e., nodes with no incoming edges);

• R2^′

  For $i>1$, Layer $i$, denoted by $\mathcal{L}_{i}$, consists of all nodes whose in-neighbors consists of nodes in Layers $j$ for $j<i$ with at least one in-neighbor in Layer $i-1$; and

• R3^′

  The last layer consists only of sinks (but not necessarily all the sinks).

We say that a group $\mathcal{G}$ of messages is fully present in a layer $\mathcal{L}_{x}$, if $\mathcal{G}\subseteq\{X_{j}:(r,j)\in\mathcal{L}_{x}\}$. We say a group $\mathcal{G}$ of messages is partially present in a layer $\mathcal{L}_{x}$, if $0<|\mathcal{G}\cap\{X_{j}:(r,j)\in\mathcal{L}_{x}\}|<g$. Lastly, we say that a group $\mathcal{G}$ of messages is absent in a layer $\mathcal{L}_{x}$, if $\mathcal{G}\cap\{X_{j}:(r,j)\in\mathcal{L}_{x}\}=\emptyset$. Conversely, a layer $\mathcal{L}_{x}$ is perfectly covered by groups if there exists a collection of groups $\mathcal{G}_{i_{1}},\ldots,\mathcal{G}_{i_{k}}$ whose $kg$ message labels together form the message labels of the nodes in the layer, i.e., $\mathcal{G}_{i_{1}}\cup\ldots\cup\mathcal{G}_{i_{k}}=\{X_{j}:(r,j)\in\mathcal{L}_{x}\}$. We extend the above notions to say a group $\mathcal{G}$ of messages is partially present or fully present in a MAIS $G$ of $G_{\mathcal{D}}$ if it is partially present or fully present in any one layer. Note that from Property P5 below, a group cannot be partially present in more than one layer. Similarly, we say that a group $\mathcal{G}$ of messages is absent from a MAIS $G$ of $G_{\mathcal{D}}$ if it is absent from every layer of $G$.

The last fact that we will need for our non-achievability results characterizes the size of an MAIS for generalized decoding choice obtained by appending to decoding choices messages that a receiver decodes by emulation.

We begin this section with the achievability result, which is an extension of the one proposed in [15].

The following figure presents the plot of the achievable rate offered by Theorem 1. Additionally, the applicable matching non-achievability results for various ranges of $t$ are also indicated therein. Note from the proof of achievability that in the last round, an MDS code will be used if and only if $s\geq m-s$, in which case the achievable rate is given by $\lceil\frac{t}{m-s}\rceil(m-s)$; alternately, the last round will comprise of uncoded messages iff $s<m-s$, which introduces the unity slope portions. In both cases, the achievable rate region is non-convex due to the absence of a time-sharing argument that is usually used to convexify rate regions.

We now present three ancillary results that are needed to derive our non-achievability results. The first two connect the size of MAIS of $G_{\mathcal{D}}$ to the number of messages decoded by a node in $G_{\mathcal{D}}$. The third result argues that under certain conditions if there is a decoding choice whose size of a MAIS is $s+t-i$ for $i>0$, then there must exist another decoding choice whose size of MAIS is $s+t-i+1$. Our non-achievability results prove the non-existence of a decoding choice whose MAIS size is $s+t-1$, and therefore, using the third result, we are guaranteed that the smallest size of any MAIS of any decoding choice is $s+t$.

We are now ready to present our non-achievability results.