# Optimal Zero-Error Coding for Computing under Pairwise Shared Side Information

Nicolas Charpenay, Maël Le Treust, Aline Roumy

<figure><img src="image_1.png" /></figure>

## To cite this version:

Nicolas Charpenay, Maël Le Treust, Aline Roumy. Optimal Zero-Error Coding for Computing under Pairwise Shared Side Information. ITW 2023 - Information Theory Workshop, Apr 2023, Saint Malo, France. pp.1-5. hal-03901563v2

HAL Id: hal-03901563

https://hal.science/hal-03901563v2

Submitted on 19 Jun 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Optimal Zero-Error Coding for Computing under
Pairwise Shared Side Information

Nicolas Charpenay

Maël le Treust

Aline Roumy

Institut de Recherche en Informatique
et Systèmes Aléatoires (IRISA)

Institut de Recherche en Informatique
et Systèmes Aléatoires (IRISA)

Institut National de Recherche
en Informatique et en Automatique (INRIA)

Rennes, FRANCE

Rennes, FRANCE

Rennes, FRANCE

nicolas.charpenay@irisa.fr

mael.le-treust@irisa.fr

aline.roumy@inria.fr

*Abstract*—We study the zero-error source coding problem in which an encoder with Side Information (SI) $g(Y)$ transmits source symbols $X$ to a decoder. The decoder has SI $Y$ and wants to recover $f(X, Y)$ where $f, g$ are deterministic. We exhibit a condition on the source distribution and $g$ that we call “pairwise shared side information”, such that the optimal rate has a single-letter expression. This condition is satisfied if every pair of source symbols “share” at least one SI symbol for all output of $g$; in the case $f(X, Y) = X$, the $P_{X,Y}$ and $g$ that satisfy it, induce the worst optimal rate. More generally for all $f$, it has a practical interpretation, as $Y$ models a request made by the encoder on an image $X$, and $g(Y)$ corresponds to the type of request. It also has a graph-theoretical interpretation: under “pairwise shared side information” the characteristic graph can be written as a disjoint union of OR products. In the case where the source distribution is full-support, we provide an analytic expression for the optimal rate. We develop an example under “pairwise shared side information”, and we show that the optimal coding scheme outperforms several strategies from the literature.

# I. INTRODUCTION

Consider the source coding scenario depicted in Figure 1 where two correlated sequences $(X^n, Y^n)$ of discrete i.i.d. random source symbols are drawn with a distribution $P_{X,Y}^n$. The encoder knows $X^n$, has $(g(Y_t))_{t \le n}$ as side information, and transmits information to the decoder through a perfect channel of capacity $R$. The decoder has the side information $Y^n$ and wants to reconstruct $(f(X_t, Y_t))_{t \le n}$, where $f, g$ are deterministic. What is the minimal $R$ such that $(f(X_t, Y_t))_{t \le n}$ can be retrieved by the decoder with probability of error 0?

This coding problem appears in video compression [1], [2], where $X^n$ models a set of images known at the encoder. The decoder does not always want to retrieve each image, but has instead a sequence $Y^n$ of particular requests for each image, e.g. detection: cat, dog, car, bike; or scene recognition: street/city/mountain, etc... The encoder does not know the decoder's exact request but has prior information about it (e.g. type of request), which is modeled by $(g(Y_t))_{t \le n}$.

The problem of Figure 1 relates to the “restricted inputs” zero-error problem of Alon and Orlitsky [3], as it is obtained as a special case by taking $g$ constant and $f(X, Y) = X$. The optimal rate in “restricted inputs” is given by asymptotic chromatic entropies of graph products. Koulgi et al. show in [4] that this optimal rate is equal to the complementary graph

<figure><img src="image_3.png" /><figcaption>Fig. 1: Zero-error coding for computing with side information at the encoder.</figcaption></figure>

entropy, introduced in [5] by Körner and Longo. No single-letter expression for these quantities is known. In [6], Marton shows that these quantities are closely related to the Shannon capacity of a graph (see [7]), which is a wide open problem.

The similar “unrestricted inputs” zero-error setting of [3] has a single-letter formula for the optimal rate, but its zero-error constraint is much stronger than “restricted inputs” as $(X^n, Y^n)$ can take values out of the support of $P_{X,Y}^n$.

Now the scheme of Figure 1 has been studied with different coding constraints than zero-error “restricted inputs”, and the optimal rate has been characterized in each case: the lossless case by Orlitsky and Roche in [8], the lossy case by Yamamoto in [9], and the zero-error “unrestricted inputs” case by Shayevitz in [10]. These results can only be used as bounds here: the zero-error “restricted inputs” problem depicted in Figure 1 does not have a characterization of the optimal rate.

Numerous extensions of this problem have been studied recently. The distributed context, for instance, has an additional encoder which encodes $Y$ before transmitting it to the decoder. Achievability schemes have been proposed for this setting by Krithivasan and Pradhan in [11] using abelian groups; by Basu et al. in [12] using hypergraphs for the case with maximum distortion criterion; and by Malak and Médard in [13] using hyperplane separations for the continuous lossless case.

Another related context is the network setting, where the function of source random variables from source nodes has to be retrieved at the sink node of a given network. For tree networks, the feasible rate region is characterized by Feizi and Médard in [14] for networks of depth one; and by Sefidgaran and Tchamkerten in [15] under a Markov source distribution hypothesis. In [16], Ravi and Dey consider a bidirectional relay with zero-error “unrestricted inputs” and characterize the rate region for a specific class of functions. In [17], Guang et
al. study zero-error function computation on acyclic networks with limited capacities, and give an inner bound based on network cut-sets. For both distributed and network settings, the “restricted inputs” zero-error problem remains open.

In this paper, we formulate an hypothesis on $P_{X,Y}$ and $g$ that we call “pairwise shared side information” that allows us to derive a single-letter characterization of the optimal rate. This hypothesis is satisfied if every pair of source symbols “share” at least one side information symbol for all output of $g$. It has graph-theoretic interpretations, as the single-letter formula stems from the particular structure of the characteristic graph of the problem: a disjoint union of OR products. Moreover, this result is of practical interest as it covers the cases with $P_{X,Y}$ full-support, without any assumption on $f,g$.

In Section II, we present formally the problem of Figure 1. In Section III, we build the characteristic graphs and give an asymptotic formula for the general case. In Section IV, we make the “pairwise shared side information” assumption and give a single-letter characterization of the optimal rate, along with a refinement for $P_{X,Y}$ full-support. We prove it in Section VI and illustrate it in Section V with an example.

## II. PROBLEM STATEMENT

We denote sequences by $x^n = (x_1, ..., x_n)$. The set of probability distributions over $\mathcal{X}$ is denoted by $\Delta(\mathcal{X})$. The distribution of $X$ is denoted by $P_X \in \Delta(\mathcal{X})$, its support is denoted by supp $P_X$. Given the sequence length $n \in \mathbb{N}^*$, we denote by $\Delta_n(\mathcal{X}) \subset \Delta(\mathcal{X})$ the set of empirical distributions of sequences from $\mathcal{X}^n$. We denote by $\{0, 1\}^*$ the set of binary words. The setting of Fig. 1 is described by:

- Four finite sets $\mathcal{X}, \mathcal{Y}, \mathcal{U}, \mathcal{Z}$, a couple of random variables $(X, Y) \in \mathcal{X} \times \mathcal{Y}$ drawn with the distribution $P_{X,Y}$ (with $P_X$ and $P_Y$ full-support), and deterministic functions

$$f: \mathcal{X} \times \mathcal{Y} \to \mathcal{U}, \qquad (1)$$

$$g: \mathcal{Y} \to \mathcal{Z}. \qquad (2)$$

For $n$ iterated source uses, we denote by $(X^n, Y^n)$ the sequence of $n$ independent copies of $(X, Y)$, with probability distribution $P_{X,Y}^n \in \Delta(\mathcal{X}^n \times \mathcal{Y}^n)$.

- The encoder observes the realizations of $X^n, (g(Y_t))_{t \le n}$ and sends information to the decoder over a noiseless channel of capacity $R \ge 0$.

- The decoder has to recover $(f(X_t, Y_t))_{t \le n}$ based on the encoder message and the side information $Y^n$.

### Definition II.1 (Zero-error source code, achievable rates)

Given $n \in \mathbb{N}^*$, a $(n, R_n)$-zero-error source code consists of an encoding function $\phi_e: \mathcal{X}^n \times \mathcal{Z}^n \to \{0, 1\}^*$ and a decoding function $\phi_d: \mathcal{Y}^n \times \{0, 1\}^* \to \mathcal{U}^n$ such that:

1) the set $\phi_e(\mathcal{X}^n \times \mathcal{Z}^n)$ is prefix-free,

2) $R_n = \frac{1}{n} \mathbb{E}[l \circ \phi_e(X^n, (g(Y_t))_{t \le n})]$, where $l(\cdot)$ denotes the length of a binary word,

3) the “restricted inputs” zero-error property is satisfied:

$$\begin{gathered} \forall (x^n, y^n) \in \text{supp } P_{X,Y}^n, \\ \phi_d\left(y^n, \phi_e\left(x^n, (g(y_t))_{t \le n}\right)\right) = (f(x_t, y_t))_{t \le n}. \quad (3) \end{gathered}$$

A rate $R$ is achievable if there exists a sequence of $(n, R_n)$-zero-error source codes such that $\lim_n R_n = R$. The optimal rate is denoted by $R^* = \inf\{R \ge 0 \mid R \text{ is achievable}\}$.

The prefix-free hypothesis guarantees that the decoder knows when the encoder's message stops. A relaxation of this hypothesis is considered in [3, Theorem 3], without influence on the asymptotic optimal rate. Satisfying all three conditions imply a correct decoding with probability one.

## III. GENERAL SETTING

A probabilistic graph $G$ is a tuple $(\mathcal{V}, \mathcal{E}, P_V)$, where $\mathcal{V}$ is the set of vertices, $\mathcal{E}$ is the set of edges, and $P_V \in \Delta(\mathcal{V})$ is an underlying probability distribution on the vertices.

We first build the characteristic graph $G_{[n]}$, which is a probabilistic graph that captures the zero-error encoding constraints on a given number $n$ of source uses. It differs from the graphs used in [10], as we do not need a cartesian representation of these graphs to study the optimal rates. Furthermore, it has a vertex for each possible realization of $(X^n, (g(Y_t))_{t \le n})$ known at the encoder, instead of $\mathcal{X}^n$, as in [18] and [3].

**Definition III.1 (Characteristic graph $G_{[n]}$)** The characteristic graph $G_{[n]}$ is defined by:

- $\mathcal{X}^n \times \mathcal{Z}^n$ as set of vertices with distribution $P_{X,g(Y)}^n$,

- $(x^n, z^n)(x'^n, z'^n)$ are adjacent if $z^n = z'^n$ and there exists $y^n \in g^{-1}(z^n)$ such that:

$$\forall t \le n, P_{X,Y}(x_t, y_t) P_{X,Y}(x'_t, y_t) > 0, \quad (4)$$

$$\text{and } \exists t \le n, f(x_t, y_t) \ne f(x'_t, y_t); \quad (5)$$

$$\text{where } g^{-1}(z^n) = \{y^n \in \mathcal{Y}^n \mid (g(y_t))_{t \le n} = z^n\}.$$

The characteristic graph $G_{[n]}$ is designed with the same core idea as in [18]: $(x^n, z^n)$ and $(x'^n, z'^n)$ are adjacent if there exists a side-information symbol $y^n$ compatible with the observation of the encoder (i.e. $z^n = z'^n$ and $y^n \in g^{-1}(z^n)$), such that $f(x^n, y^n) \ne f(x'^n, y^n)$. In order to prevent erroneous decodings, the encoder must map adjacent pairs of sequences to different codewords; hence the use of graph colorings.

**Definition III.2 (Coloring, independent subset)** Let $G = (\mathcal{V}, \mathcal{E}, P_V)$ be a probabilistic graph. A subset $S \subseteq \mathcal{V}$ is independent if $xx' \notin \mathcal{E}$ for all $x, x' \in S$. Let $C$ be a finite set (the set of colors), a mapping $c: \mathcal{V} \to C$ is a coloring if $c^{-1}(i)$ is an independent subset for all $i \in C$.

The chromatic entropy of $G_{[n]}$ gives the best rate of $n$-shot zero-error encoding functions, as in [3].

**Definition III.3 (Chromatic entropy $H_X$)** The chromatic entropy of a probabilistic graph $G = (\mathcal{V}, \mathcal{E}, P_V)$ is defined by

$$H_X(G) = \inf \{ H(c(V)) \mid c \text{ is a coloring of } G \}. \quad (6)$$

**Theorem III.4 (Optimal rate)** The optimal rate writes:

$$R^* = \lim_{n \to \infty} \frac{1}{n} H_X(G_{[n]}). \quad (7)$$
*Proof Outline.* An encoding function $\phi_e$ is a coloring of $G_{[n]}$ if and only if it satisfies (3) with some decoding function $\phi_d$. Thus the best achievable rate writes

$$R^* = \inf_n \inf_{\phi_e \text{ coloring of } G_{[n]}} H\left(\phi_e\left(X^n, (g(Y_t))_{t \le n}\right)\right) \quad (8)$$

$$= \lim_{n \to \infty} \frac{1}{n} H_{\chi}(G_{[n]}). \quad (9)$$

where (9) comes from Fekete's lemma and (6). □

A general single-letter expression for $R^*$ is missing, due to the lack of intrinsic structure of $G_{[n]}$. In Section IV, we introduce a hypothesis that gives structure to $G_{[n]}$ and allows us to derive a single-letter expression for $R^*$.

## IV. PAIRWISE SHARED SIDE INFORMATION

**Definition IV.1** The distribution $P_{X,Y}$ and the function $g$ satisfy the “pairwise shared side information” condition if

$$\forall z \in \mathcal{Z}, \forall x, x' \in \mathcal{X}, \exists y \in g^{-1}(z), P_{XY}(x, y)P_{XY}(x', y) > 0. \quad (10)$$

This means that for all $z$ output of $g$, every pair $(x, x')$ “shares” at least one side information symbol $y \in g^{-1}(z)$.

This condition is of great interest, because the pairs $(P_{X,Y}, g)$ that satisfy the “pairwise shared side information” hypothesis are the ones that induce the worst optimal rate $H(X|g(Y))$ in the case $f(X,Y) = X$. For instance, any full-support distribution $P_{X,Y}$ satisfies the “pairwise shared side information” hypothesis.

**Definition IV.2 (AND, OR product)** Let $G_1 = (V_1, \mathcal{E}_1, P_{V_1})$, $G_2 = (V_2, \mathcal{E}_2, P_{V_2})$ be two probabilistic graphs; their AND (resp. OR) product denoted by $G_1 \wedge G_2$ (resp. $G_1 \vee G_2$) is defined by: $V_1 \times V_2$ as set of vertices, $P_{V_1}P_{V_2}$ as probability distribution on the vertices, and $(v_1v_2), (v'_1v'_2)$ are adjacent if

$$v_1v'_1 \in \mathcal{E}_1 \text{ AND } v_2v'_2 \in \mathcal{E}_2, \quad (11)$$

resp. $(v_1v'_1 \in \mathcal{E}_1$ and $v_1 \ne v'_1$) OR $(v_2v'_2 \in \mathcal{E}_2$ and $v_2 \ne v'_2$); with the convention that all vertices are self-adjacent. We denote by $G_1^{\wedge n}$ (resp. $G_1^{\vee n}$) the n-th AND (resp. OR) power.

For the “restricted inputs” source coding problem in [3], the n-shot characteristic graph is the n-th AND product of the one-shot characteristic graph, and the optimal rate in this problem $\lim_{n \to \infty} \frac{1}{n} H_{\chi}(G^{\wedge n})$ does not have a single-letter expression. However, for the “unrestricted inputs” setting there exists such a formula: the Körner graph entropy introduced in [19], which relates to the OR product as shown in Proposition IV.4.

**Definition IV.3 (Körner graph entropy $H_\kappa$)** For all $G = (\mathcal{V}, \mathcal{E}, P_V)$, let $\Gamma(G)$ be the collection of independent sets of vertices in $G$. The Körner graph entropy of $G$ is defined by

$$H_{\kappa}(G) = \min_{V \in W \in \Gamma(G)} I(W; V), \quad (12)$$

where the minimum is taken over all distributions $P_{W|V} \in \Delta(W)^V$, with $W = \Gamma(G)$ and the constraint that the random vertex $V$ belongs to the random set $W$ with probability one.

**Proposition IV.4 (Properties of $H_\kappa$)** [3, Theorem 5] For all probabilistic graphs $G$ and $G'$,

$$H_{\kappa}(G) = \lim_{n \to \infty} \frac{1}{n} H_{\chi}(G^{\vee n}), \quad (13)$$

$$H_{\kappa}(G \vee G') = H_{\kappa}(G) + H_{\kappa}(G'). \quad (14)$$

By using a convex combination of Körner graph entropies, we provide a single-letter expression for the optimal rate $R^*$.

**Definition IV.5 (Auxiliary graph $G_z^f$)** For all $z \in \mathcal{Z}$, we define the auxiliary graph $G_z^f$ by

- $\mathcal{X}$ as set of vertices with distribution $P_{X|g(Y)=z}$,

- $xx'$ are adjacent if $f(x, y) \ne f(x', y)$ for some $y \in g^{-1}(z) \cap \text{supp } P_{Y|X=x} \cap \text{supp } P_{Y|X=x'}$.

**Theorem IV.6 (Pairwise shared side information)** If $P_{X,Y}$ and $g$ satisfy (10), the optimal rate writes:

$$R^* = \sum_{z \in \mathcal{Z}} P_{g(Y)}(z) H_{\kappa}(G_z^f). \quad (15)$$

The proof is in Section VI, the keypoint is the particular structure of $G_{[n]}$: a disjoint union of OR products.

**Remark IV.7** The “pairwise shared side information” assumption (10) implies that the adjacency condition (4) is satisfied, which makes $G_{[n]}$ a disjoint union of OR products. Moreover, Körner graph entropies appear in the final expression for $R^*$, even if $G_{[n]}$ is not an n-th OR power.

Now consider the case where $P_{X,Y}$ is full-support. This is a sufficient condition to have (10). The optimal rate in this setting is derived from Theorem IV.6, which leads to the analytic expression in Theorem IV.8.

**Theorem IV.8 (Optimal rate when $P_{X,Y}$ is full-support)**

When $P_{X,Y}$ is full-support, the optimal rate writes:

$$R^* = H(j(X, g(Y))|g(Y)), \quad (16)$$

where the function $j$ returns a word in $\mathcal{U}^*$, defined by

$$j: \mathcal{X} \times \mathcal{Z} \to \mathcal{U}^* \\ (x, z) \mapsto (f(x, y'))_{y' \in g^{-1}(z)}. \quad (17)$$

*Proof Outline.* By Theorem IV.6, $R^* = \sum_{z \in \mathcal{Z}} P_{g(Y)}(z) H_{\kappa}(G_z^f)$. It can be shown that $G_z^f$ is complete multipartite for all $z$ as $P_{X,Y}$ is full support; and it satisfies $H_{\kappa}(G_z^f) = H(j(X, g(Y))|g(Y) = z)$.

## V. EXAMPLE

In this example, the “pairwise shared side information” assumption is satisfied and $R^*$ is strictly less than a conditional Huffman coding of $X$ knowing $g(Y)$; and also strictly less than the optimal rate without exploiting $g(Y)$ at the encoder.

Consider the probability distribution and function outcomes depicted in Figure 2, with $\mathcal{U} = \{a, b, c\}$, $\mathcal{X} = \{0, ..., 3\}$, $\mathcal{Y} = \{0, ..., 7\}$, and $\mathcal{Z} = \{0, 1\}$. Let us show that the “pairwise shared side information” assumption is satisfied. The source
<table><thead><tr><th></th><th colspan="8">Y</th></tr><tr><th></th><th>0</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th></tr><tr><th></th><th colspan="8">g(Y) = 0</th></tr></thead><tbody><tr><th>0</th><td>0.1</td><td>0.05</td><td>*</td><td>*</td><td>0.05</td><td>0.05</td><td>*</td><td>*</td></tr><tr><th>1</th><td>0.1</td><td>*</td><td>0.05</td><td>*</td><td>0.05</td><td>0.05</td><td>0.05</td><td>*</td></tr><tr><th>2</th><td>0.1</td><td>*</td><td>*</td><td>0.05</td><td>*</td><td>0.05</td><td>*</td><td>*</td></tr><tr><th>3</th><td>*</td><td>0.05</td><td>0.05</td><td>0.05</td><td>*</td><td>0.05</td><td>*</td><td>0.05</td></tr></tbody></table>

<table><caption>Fig. 2: An example of $P_{X,Y}$ and $g$ that satisfy (10); along with the outcomes $f(X, Y)$. The elements outside supp $P_{X,Y}$ are denoted by *.</caption><thead><tr><th></th><th colspan="8">Y</th></tr><tr><th></th><th>0</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th></tr><tr><th></th><th colspan="8">g(Y) = 0</th></tr></thead><tbody><tr><th>0</th><td>a</td><td>b</td><td>*</td><td>*</td><td>b</td><td>a</td><td>*</td><td>*</td></tr><tr><th>1</th><td>a</td><td>*</td><td>b</td><td>*</td><td>a</td><td>a</td><td>b</td><td>*</td></tr><tr><th>2</th><td>b</td><td>*</td><td>*</td><td>c</td><td>*</td><td>b</td><td>*</td><td>*</td></tr><tr><th>3</th><td>*</td><td>c</td><td>c</td><td>c</td><td>*</td><td>c</td><td>*</td><td>c</td></tr></tbody></table>

<figure><img src="image_4.png" /><figcaption>Fig. 3: The graph $G$ depicted here with its underlying probability distribution satisfies $G = (C_4, \text{Unif}(\{1, ..., 4\})) \sqcup (K_4, \text{Unif}(\{1, ..., 4\}))$; where $C_4$ (resp. $K_4$) is the cycle (resp. complete) graph with 4 vertices.</figcaption></figure>

symbols $0, 1, 2 \in \mathcal{X}$ share the SI symbol 0 (resp. 5) when $g(Y) = 0$ (resp. $g(Y) = 1$). The source symbol $3 \in \mathcal{X}$ shares the SI symbols $1, 2, 3$ with the source symbols $0, 1, 2$, respectively, when $g(Y) = 0$; and the source symbol 3 shares the SI symbol 5 with all other source symbols when $g(Y) = 1$.

Since the “pairwise shared side information” assumption is satisfied, we can use Theorem IV.6; the optimal rate writes

$$R^* = P_{g(Y)}(0)H_{\kappa}(G_0^f) + P_{g(Y)}(1)H_{\kappa}(G_1^f). \quad (18)$$

First we need to determine the probabilistic graphs $G_0^f$ and $G_1^f$. In $G_0^f$, the vertex 0 is adjacent to 2 and 3, as $f(0, 0) \neq f(2, 0)$ and $f(0, 1) \neq f(3, 1)$. The vertex 1 is also adjacent to 2 and 3 as $f(1, 0) \neq f(2, 0)$ and $f(1, 2) \neq f(3, 2)$. Furthermore $P_{X|g(Y)=0}$ is uniform, hence $G_0^f = (C_4, \text{Unif}(\mathcal{X}))$ where $C_4$ is the cycle graph with 4 vertices.

In $G_1^f$, the vertices 1, 2, 3 are pairwise adjacent as $f(1, 5)$, $f(2, 5)$ and $f(3, 5)$ are pairwise different; and 0 is adjacent to 1, 2 and 3 because of the different function outputs generated by $Y=4$ and $Y=5$. Thus, $G_1^f = (K_4, P_{X|g(Y)=1})$ with $P_{X|g(Y)=1} = (\frac{1}{4}, \frac{3}{8}, \frac{1}{8}, \frac{1}{4})$ and $K_4$ is the complete graph with 4 vertices. An illustration of $C_4$ and $K_4$ is given in Figure 3.

Now let us determine $H_{\kappa}(G_0^f)$ and $H_{\kappa}(G_1^f)$. On one hand,

$$ 
\begin{aligned}
H_{\kappa}(G_0^f) &= H(V_0) - \max_{V_0 \in W \in \Gamma(G_0^f)} H(V_0|W) \quad (19) \\
&= 2 - 1 = 1, \quad (20)
\end{aligned}
$$

with $V_0 \sim P_{X|g(Y)=0} = \text{Unif}(\mathcal{X})$; and where $H(V_0|W)$ in (19) is maximized by taking $W = \{0, 1\}$ when $V \in \{0, 1\}$, and $W = \{2, 3\}$ otherwise.

On the other hand,

$$ 
\begin{aligned}
H_{\kappa}(G_1^f) &= \min_{V_1 \in W \in \Gamma(G_1^f)} I(W; V_1) \quad (21) \\
&= H(V_1) \approx 1.906, \quad (22)
\end{aligned}
$$

with $V_1 \sim P_{X|g(Y)=1}$; where (22) follows from $\Gamma(G_1^f) = \{\{0\}, ..., \{3\}\}$, as $G_1^f$ is complete. Hence $R^* \approx 1.362$.

The rate that we would obtain by transmitting $X$ knowing $g(Y)$ at both encoder and decoder with a conditional Huffman algorithm writes: $R_{\text{Huff}} = H(X|g(Y)) \approx 1.962$.

The rate that we would obtain without exploiting $g(Y)$ at the encoder is $R_{\text{No } g} = H(X) \approx 1.985$, because of the different function outputs generated by $Y=4$ and $Y=5$.

Finally, $H(f(X, Y)|Y) \approx 0.875$.

In this example we have

$$H(X) = R_{\text{No } g} > R_{\text{Huff}} > R^* > H(f(X, Y)|Y). \quad (23)$$

This illustrates the impact of the side information at the encoder in this setting, as we can observe a large gap between the optimal rate $R^*$ and $R_{\text{No } g}$.

## VI. PROOF OF THEOREM IV.6

### A. Definitions

We will use the disjoint union of probabilistic graphs, which generalizes the existing concept of a disjoint union of graphs without underlying probability distribution [20, Section 1.4]. An example of disjoint union is depicted in Figure 3. We also need to formalize the concept of isomorphic probabilistic graphs, i.e. same structure and underlying distribution.

#### Definition VI.1 (Disjoint union of probabilistic graphs)

Let $N \in \mathbb{N}^*$; let $G = (V, \mathcal{E}, P_V)$ and for all $i \le N$, let $\tilde{G}_i = (V_i, \mathcal{E}_i, P_{V_i})$. We say that $G$ is the disjoint union of the $(\tilde{G}_i)$, denoted by $G = \bigsqcup_{i \le N} \tilde{G}_i$, if the following is satisfied:

- $V$ is the disjoint union of the sets $(V_i)_{i \le N}$, i.e. $V = \bigsqcup_i V_i$ and $V_i \cap V_{i'} = \emptyset$ for all $i \neq i'$;

- For all $v, v' \in V$, let $i, i'$ be the unique indexes such that $v \in V_i$ and $v' \in V_{i'}$. Then if $i = i'$, $vv' \in \mathcal{E} \iff vv' \in \mathcal{E}_i$; if $i \neq i'$, $vv' \notin \mathcal{E}$;

- For all $i \le n$, $P_{V|V \in V_i} = P_{V_i}$.

#### Definition VI.2 (Isomorphic probabilistic graphs)

Let $G_1 = (V_1, \mathcal{E}_1, P_{V_1})$ and $G_2 = (V_2, \mathcal{E}_2, P_{V_2})$. We say that $G_1$ is isomorphic to $G_2$ (denoted by $G_1 \simeq G_2$) if there exists an isomorphism between them, i.e. a bijection $\psi: V_1 \to V_2$ such that:

- For all $v_1, v'_1 \in V_1$, $v_1v'_1 \in \mathcal{E}_1 \iff \psi(v_1)\psi(v'_1) \in \mathcal{E}_2$,

- For all $v_1 \in V_1$, $P_{V_1}(v_1) = P_{V_2}(\psi(v_1))$.
## B. Main proof

Let us specify the adjacency condition in $G_{[n]}$ under the assumption (10). Two vertices are adjacent if they satisfy (4) and (5); however (4) is always satisfied under (10). Thus $(x^n, z^n)(x'^n, z^n)$ are adjacent if $z^n = z'^n$ and

$$ \exists y^n \in g^{-1}(z^n), \exists t \le n, f(x_t, y_t) \ne f(x'_t, y_t). \quad (24) $$

It can be observed that the condition (24) is the adjacency condition of an OR product of adequate graphs; more precisely,

$$ G_{[n]} = \bigsqcup_{z^n \in \mathcal{Z}^n} \bigvee_{t \le n} G_{zt}^f. \quad (25) $$

Although $G_{[n]}$ cannot be expressed as an $n$-th OR power, we will show that its chromatic entropy asymptotically coincide with that of an appropriate OR power: we now search for an asymptotic equivalent of $H_\chi(G_{[n]})$.

**Definition VI.3** $S_n$ is the set of colorings of $G_{[n]}$ that can be written as $(x^n, z^n) \mapsto (T_{z^n}, \tilde{c}(x^n, z^n))$ for some mapping $\tilde{c}: \mathcal{X}^n \times \mathcal{Z}^n \to \tilde{C}$; where $T_{z^n}$ denotes the type of $z^n$.

In the following, we define $Z^n \doteq (g(Y_t))_{t \le n}$. Now we need several Lemmas. Lemma 1 states that the optimal coloring $c(x^n, z^n)$ of $G_{[n]}$ has the type of $z^n$ as a prefix at a negligible rate cost. Lemma 2 is an adapted version for chromatic entropies of the following observation: minimum colorings on each connected component induce a minimum coloring of the whole graph. Lemma 3 gives an asymptotic formula for the minimal entropy of the colorings from $S_n$.

**Lemma 1** The following asymptotic comparison holds:

$$ H_{\chi}(G_{[n]}) = \inf_{\substack{c \text{ coloring of } G_{[n]} \\ \text{s.t. } c \in S_n}} H(c(X^n, Z^n)) + O(\log n). \quad (26) $$

**Lemma 2** Let $N \in \mathbb{N}^*$; let $G = (\mathcal{V}, \mathcal{E}, P_V)$ and for all $i \le N$, let $\tilde{G}_i = (\tilde{\mathcal{V}}_i, \tilde{\mathcal{E}}_i, P_{\tilde{V}_i})$ be probabilistic graphs such that $G = \bigsqcup_i \tilde{G}_i$ and $\tilde{G}_1 \approx \dots \approx \tilde{G}_N$. Then we have $H_\chi(G) = H_\chi(\tilde{G}_1)$.

**Lemma 3** The following asymptotic comparison holds:

$$ \inf_{\substack{c \text{ coloring of } G_{[n]} \\ \text{s.t. } c \in S_n}} H(c(X^n, Z^n)) = n \sum_{z \in \mathcal{Z}} P_{g(Y)}(z) H_{\kappa}(G_z^f) + o(n). \quad (27) $$

An extended version with complete proofs of Lemmas 1, 2, 3 can be found at [21].

Lemma 2 is proved using the concavity of the entropy, which implies the following: an optimal coloring colors all the isomorphic connected components the same way.

The proof of Lemma 3 relies on the decomposition $G_{[n]} = \bigsqcup_{Q_n \in \Delta_n(\mathcal{Z})} G_{[n]}^{Q_n}$, where $G_{[n]}^{Q_n}$ is the subgraph induced by the vertices $(x^n, z^n)$ such that the type of $z^n$ is $Q_n$. We show that $G_{[n]}^{Q_n}$ is a disjoint union of isomorphic graphs whose chromatic entropy is given by Lemma 2 and (14): $|H_\chi(G_{[n]}^{Q_n}) - n \sum_{z \in \mathcal{Z}} Q_n(z) H_\kappa(G_z^f)| \le n\epsilon_n$. Finally, uniform convergence arguments enable us to conclude.

Now let us combine these results together:

$$ R^* = \frac{1}{n} H_\chi(G_{[n]}) + o(1) \quad (28) $$

$$ = \inf_{\substack{n \\ \text{ c coloring of } G_{[n]} \\ \text{s.t. } c \in S_n}} H(c(X^n, Z^n)) + o(1) \quad (29) $$

$$ = \sum_{z \in \mathcal{Z}} P_{g(Y)}(z) H_{\kappa}(G_z^f) + o(1), \quad (30) $$

where (28) comes from Theorem III.4, (29) comes from Lemma 1, and (30) comes from Lemma 3. The proof of Theorem IV.6 is complete.

## REFERENCES

[1] L. Duan, J. Liu, W. Yang, T. Huang, and W. Gao, "Video coding for machines: A paradigm of collaborative compression and intelligent analytics," *IEEE Transactions on Image Processing*, vol. 29, pp. 8680–8695, 2020.

[2] W. Gao, S. Liu, X. Xu, M. Rafie, Y. Zhang, and I. Curcio, "Recent standard development activities on video coding for machines," *arXiv preprint arXiv:2105.12653*, 2021.

[3] N. Alon and A. Orlitsky, "Source coding and graph entropies," *IEEE Transactions on Information Theory*, vol. 42, no. 5, pp. 1329–1339, 1996.

[4] P. Koulgi, E. Tuncel, S. L. Regunathan, and K. Rose, "On zero-error source coding with decoder side information," *IEEE Transactions on Information Theory*, vol. 49, no. 1, pp. 99–111, 2003.

[5] J. Korner and G. Longo, "Two-step encoding for finite sources," *IEEE Transactions on Information Theory*, vol. 19, no. 6, pp. 778–782, 1973.

[6] K. Marton, "On the shannon capacity of probabilistic graphs," *Journal of Combinatorial Theory, Series B*, vol. 57, no. 2, pp. 183–195, 1993.

[7] C. Shannon, "The zero error capacity of a noisy channel," *IRE Transactions on Information Theory*, vol. 2, no. 3, pp. 8–19, 1956.

[8] A. Orlitsky and J. R. Roche, "Coding for computing," in *Proceedings of IEEE 36th Annual Foundations of Computer Science*, 1995.

[9] H. Yamamoto, "Wyner-ziv theory for a general function of the correlated sources (corresp.)," *IEEE Transactions on Information Theory*, vol. 28, no. 5, pp. 803–807, 1982.

[10] O. Shayevitz, "Distributed computing and the graph entropy region," *IEEE Transactions on Information Theory*, vol. 60, no. 6, 2014.

[11] D. Krithivasan and S. S. Pradhan, "Distributed source coding using abelian group codes: A new achievable rate-distortion region," *IEEE Transactions on Information Theory*, vol. 57, no. 3, 2011.

[12] S. Basu, D. Seo, and L. R. Varshney, "Hypergraph-based coding schemes for two source coding problems under maximal distortion," in *IEEE International Symposium on Information Theory (ISIT)*, 2020.

[13] D. Malak and M. Médard, "Hyper binning for distributed function coding," in *2020 IEEE 21st International Workshop on Signal Processing Advances in Wireless Communications (SPAWC)*. IEEE, 2020, pp. 1–5.

[14] S. Feizi and M. Médard, "On network functional compression," *IEEE Transactions on Information Theory*, vol. 60, no. 9, pp. 5387–5401, 2014.

[15] M. Sefidgaran and A. Tchamkerten, "Distributed function computation over a rooted directed tree," *IEEE Transactions on Information Theory*, vol. 62, no. 12, pp. 7135–7152, 2016.

[16] J. Ravi and B. K. Dey, "Function computation through a bidirectional relay," *IEEE Transactions on Information Theory*, vol. 65, no. 2, pp. 902–916, 2018.

[17] X. Guang, R. W. Yeung, S. Yang, and C. Li, "Improved upper bound on the network function computing capacity," *IEEE Transactions on Information Theory*, vol. 65, no. 6, pp. 3790–3811, 2019.

[18] H. Witsenhausen, "The zero-error side information problem and chromatic numbers (corresp.)," *IEEE Transactions on Information Theory*, vol. 22, no. 5, pp. 592–593, 1976.

[19] J. Körner, "Coding of an information source having ambiguous alphabet and the entropy of graphs," in *6th Prague conference on information theory*, 1973, pp. 411–425.

[20] J. A. Bondy, U. S. R. Murty et al., *Graph theory with applications*. Macmillan London, 1976, vol. 290.

[21] N. Charpenay, M. I. Treust, and A. Roumy, "Zero-error coding for computing with encoder side-information," *arXiv preprint arXiv:2211.03649*, 2022.