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

Nicolas Charpenay  Institut de Recherche en Informatique
et Systèmes Aléatoires (IRISA)
Rennes, FRANCE
<EMAIL_ADDRESS>Maël le Treust  Institut de Recherche en
Informatique
et Systèmes Aléatoires (IRISA)
Rennes, FRANCE
<EMAIL_ADDRESS>Aline Roumy  Institut National de Recherche
en Informatique et en Automatique (INRIA)
Rennes, FRANCE
<EMAIL_ADDRESS>
###### 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$. 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}$. The encoder knows $X^{n}$, has
$(g(Y_{t}))_{t\leq 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\leq n}$,
where $f,g$ are deterministic. What is the minimal $R$ such that
$(f(X_{t},Y_{t}))_{t\leq n}$ can be retrieved by the decoder with probability
of error $0$?

EncoderDecoder$\big{(}g(Y_{t})\big{)}_{t\leq
n}$$Y^{n}$$\big{(}f(X_{t},Y_{t})\big{)}_{t\leq n}$$X^{n}$$\diagup$$R$ Figure
1: Zero-error coding for computing with side information at the encoder.

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\leq 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 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^{n}_{X,Y}$.

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 $\text{supp }P_{X}$. Given the sequence length
$n\in\mathbb{N}^{\star}$, 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

$\displaystyle f:\mathcal{X}\times\mathcal{Y}\rightarrow\mathcal{U},$ (1)
$\displaystyle g:\mathcal{Y}\rightarrow\mathcal{Z}.$ (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^{n}_{X,Y}\in\Delta(\mathcal{X}^{n}\times\mathcal{Y}^{n})$.

  * -

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

  * -

The decoder has to recover $(f(X_{t},Y_{t}))_{t\leq 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}^{\star}$, a $(n,R_{n})$-zero-error source code consists
of an encoding function
$\phi_{e}:\mathcal{X}^{n}\times\mathcal{Z}^{n}\rightarrow\\{0,1\\}^{*}$ and a
decoding function
$\phi_{d}:\mathcal{Y}^{n}\times\\{0,1\\}^{*}\rightarrow\mathcal{U}^{n}$ such
that:

  1. 1.

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

  2. 2.

$R_{n}=\frac{1}{n}\mathbb{E}\big{[}l\circ\phi_{e}\big{(}X^{n},(g(Y_{t}))_{t\leq
n}\big{)}\big{]}$, where $l(\cdot)$ denotes the length of a binary word,

  3. 3.

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

$\displaystyle\forall(x^{n},y^{n})\in\operatorname*{supp}P^{n}_{X,Y},$
$\displaystyle\phi_{d}\Big{(}y^{n},\phi_{e}\Big{(}x^{n},\big{(}g(y_{t})\big{)}_{t\leq
n}\Big{)}\Big{)}=\big{(}f(x_{t},y_{t})\big{)}_{t\leq n}.$ (3)

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\geq 0\>|\>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
$\big{(}X^{n},\big{(}g(Y_{t})\big{)}_{t\leq n}\big{)}$ 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^{n}_{X,g(Y)}$,

  * -

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

$\displaystyle\forall t\leq
n,\,P_{X,Y}(x_{t},y_{t})P_{X,Y}(x^{\prime}_{t},y_{t})>0,$ (4) and
$\displaystyle\exists t\leq n,\,f(x_{t},y_{t})\neq f(x^{\prime}_{t},y_{t});$
(5)

where
$g^{-1}(z^{n})=\big{\\{}y^{n}\in\mathcal{Y}^{n}\>\big{|}\>\big{(}g(y_{t})\big{)}_{t\leq
n}=z^{n}\big{\\}}$.

The characteristic graph $G_{[n]}$ is designed with the same core idea as in
[18]: $(x^{n},z^{n})$ and $(x^{\prime 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^{\prime n}$ and $y^{n}\in g^{-1}(z^{n})$), such that
$f(x^{n},y^{n})\neq f(x^{\prime 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
$\mathcal{S}\subseteq\mathcal{V}$ is independent if
$xx^{\prime}\notin\mathcal{E}$ for all $x,x^{\prime}\in\mathcal{S}$. Let
$\mathcal{C}$ be a finite set (the set of colors), a mapping
$c:\mathcal{V}\rightarrow\mathcal{C}$ is a coloring if $c^{-1}(i)$ is an
independent subset for all $i\in\mathcal{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_{\chi}$)

The chromatic entropy of a probabilistic graph
$G=(\mathcal{V},\mathcal{E},P_{V})$ is defined by

$\displaystyle H_{\chi}(G)=\inf\big{\\{}H\big{(}c(V)\big{)}\>\big{|}\>c\text{
is a coloring of }G\big{\\}}.$ (6)

######  Theorem III.4 (Optimal rate)

The optimal rate writes:

$R^{*}=\lim_{n\rightarrow\infty}\frac{1}{n}H_{\chi}(G_{[n]}).\ $ (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

$\displaystyle R^{*}=$ $\displaystyle\>\inf_{n}\inf_{\phi_{e}\text{ coloring
of }G_{[n]}}H\Big{(}\phi_{e}\Big{(}X^{n},\big{(}g(Y_{t})\big{)}_{t\leq
n}\Big{)}\Big{)}$ (8) $\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}\frac{1}{n}H_{\chi}(G_{[n]}).$ (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

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

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

Note that any full-support distribution $P_{X,Y}$ satisfies the “pairwise
shared side information” hypothesis.

######  Definition IV.2 (AND, OR product)

Let $G_{1}\\!=\\!(\mathcal{V}_{1},\mathcal{E}_{1},P_{V_{1}})$,
$G_{2}=(\mathcal{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: $\mathcal{V}_{1}\times\mathcal{V}_{2}$ as
set of vertices, $P_{V_{1}}P_{V_{2}}$ as probability distribution on the
vertices, and $(v_{1}v_{2}),(v^{\prime}_{1}v^{\prime}_{2})$ are adjacent if

$\displaystyle v_{1}v^{\prime}_{1}\in\mathcal{E}_{1}\text{ AND }$
$\displaystyle v_{2}v^{\prime}_{2}\in\mathcal{E}_{2},$ (11)
$\displaystyle\text{resp. }(v_{1}v^{\prime}_{1}\in\mathcal{E}_{1}\text{ and
}v_{1}\neq v^{\prime}_{1})\text{ OR }$
$\displaystyle(v_{2}v^{\prime}_{2}\in\mathcal{E}_{2}\text{ and }v_{2}\neq
v^{\prime}_{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\rightarrow\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

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

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

######  Proposition IV.4 (Properties of $H_{\kappa}$)

[3, Theorem 5] For all probabilistic graphs $G$ and $G^{\prime}$,

$\displaystyle
H_{\kappa}(G)=\lim_{n\rightarrow\infty}\frac{1}{n}H_{\chi}(G^{\vee n}),$ (13)
$\displaystyle H_{\kappa}(G\vee
G^{\prime})=H_{\kappa}(G)+H_{\kappa}(G^{\prime}).$ (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^{f}_{z}$)

For all $z\in\mathcal{Z}$, we define the auxiliary graph $G^{f}_{z}$ by

  * -

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

  * -

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

######  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^{f}_{z}).$ (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:

$\displaystyle R^{*}=$ $\displaystyle\>H\big{(}j(X,g(Y))\big{|}g(Y)\big{)},$
(16)

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

$\displaystyle j:$
$\displaystyle\>\mathcal{X}\times\mathcal{Z}\rightarrow\mathcal{U}^{*}$ (17)
$\displaystyle(x,z)\mapsto\big{(}f(x,y^{\prime})\big{)}_{y^{\prime}\in
g^{-1}(z)}.$

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

##  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.

$P_{X,Y}$$Y$$X$$0$$1$$2$$3$$4$$5$$6$$7$$0$$1$$2$$3$$0.1$$0.05$$*$$*$$0.1$$*$$0.05$$*$$0.1$$*$$*$$0.05$$*$$0.05$$0.05$$0.05$$0.05$$0.05$$*$$*$$0.05$$0.05$$0.05$$*$$*$$0.05$$*$$*$$*$$0.05$$*$$0.05$$g(Y)=0$$g(Y)=1$

$f(\cdot,\cdot)$$Y$$X$$0$$1$$2$$3$$4$$5$$6$$7$$0$$1$$2$$3$$a$$b$$*$$*$$a$$*$$b$$*$$b$$*$$*$$c$$*$$c$$c$$c$$b$$a$$*$$*$$a$$a$$b$$*$$*$$b$$*$$*$$*$$c$$*$$c$$g(Y)=0$$g(Y)=1$

Figure 2: An example of $P_{X,Y}$ and $g$ that satisfy (10); along with the
outcomes $f(X,Y)$. The elements outside $\operatorname*{supp}P_{X,Y}$ are
denoted by $*$.

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 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

$\displaystyle
R^{*}=P_{g(Y)}(0)H_{\kappa}(G^{f}_{0})+P_{g(Y)}(1)H_{\kappa}(G^{f}_{1}).$ (18)

First we need to determine the probabilistic graphs $G^{f}_{0}$ and
$G^{f}_{1}$. In $G^{f}_{0}$, 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^{f}_{0}=(C_{4},\text{Unif}(\mathcal{X}))$
where $C_{4}$ is the cycle graph with $4$ vertices.

In $G^{f}_{1}$, 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^{f}_{1}=(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^{f}_{0})$ and $H_{\kappa}(G^{f}_{1})$. On
one hand,

$\displaystyle H_{\kappa}(G^{f}_{0})$ $\displaystyle=H(V_{0})-\max_{V_{0}\in
W\in\Gamma(G^{f}_{0})}H(V_{0}|W)$ (19) $\displaystyle=2-1=1,$ (20)

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,

$\displaystyle H_{\kappa}(G^{f}_{1})$ $\displaystyle=\min_{V_{1}\in
W\in\Gamma(G^{f}_{1})}I(W;V_{1})$ (21) $\displaystyle=H(V_{1})\simeq 1.906,$
(22)

with $V_{1}\sim P_{X|g(Y)=1}$; where (22) follows from
$\Gamma(G^{f}_{1})=\\{\\{0\\},...,\\{3\\}\\}$, as $G^{f}_{1}$ is complete.
Hence $R^{*}\simeq 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))\simeq 1.962$.

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

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

In this example we have

$\displaystyle H(X)=R_{\text{No }g}>R_{\text{Huff}}>R^{*}>H(f(X,Y)|Y).$ (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

###  VI-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}^{\star}$; let $G=(\mathcal{V},\mathcal{E},P_{V})$ and for
all $i\leq N$, let
$\tilde{G}_{i}=(\mathcal{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\leq
N}\tilde{G}_{i}$, if the following is satisfied:

  * -

$\mathcal{V}$ is the disjoint union of the sets $(\mathcal{V}_{i})_{i\leq N}$,
i.e. $\mathcal{V}=\bigcup_{i}\mathcal{V}_{i}$ and
$\mathcal{V}_{i}\cap\mathcal{V}_{i^{\prime}}=\emptyset$ for all $i\neq
i^{\prime}$;

  * -

For all $v,v^{\prime}\in\mathcal{V}$, let $i,i^{\prime}$ be the unique indexes
such that $v\in\mathcal{V}_{i}$ and $v^{\prime}\in\mathcal{V}_{i^{\prime}}$.
Then if $i=i^{\prime}$, $vv^{\prime}\in\mathcal{E}\Longleftrightarrow
vv^{\prime}\in\mathcal{E}_{i}$; if $i\neq i^{\prime}$,
$vv^{\prime}\notin\mathcal{E}$;

  * -

For all $i\leq n$, $P_{V|V\in\mathcal{V}_{i}}=P_{V_{i}}$.

$0.05$$0.2$$0.05$$0.2$$0.05$$0.2$$0.05$$0.2$ Figure 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.

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

Let $G_{1}=(\mathcal{V}_{1},\mathcal{E}_{1},P_{V_{1}})$ and
$G_{2}=(\mathcal{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:\mathcal{V}_{1}\rightarrow\mathcal{V}_{2}$ such that:

  * -

For all $v_{1},v_{1}^{\prime}\in\mathcal{V}_{1}$,
$v_{1}v^{\prime}_{1}\in\mathcal{E}_{1}\Longleftrightarrow\psi(v_{1})\psi(v^{\prime}_{1})\in\mathcal{E}_{2}$,

  * -

For all $v_{1}\in\mathcal{V}_{1}$,
$P_{V_{1}}(v_{1})=P_{V_{2}}\big{(}\psi(v_{1})\big{)}$.

###  VI-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^{\prime n},z^{n})$ are adjacent if
$z^{n}=z^{\prime n}$ and

$\displaystyle\exists y^{n}\in g^{-1}(z^{n}),\exists t\leq
n,f(x_{t},y_{t})\neq f(x^{\prime}_{t},y_{t}).$ (24)

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

$\displaystyle G_{[n]}=\bigsqcup_{z^{n}\in\mathcal{Z}^{n}}\bigvee_{t\leq
n}G^{f}_{z_{t}}.$ (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

$\mathcal{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}\rightarrow\tilde{\mathcal{C}}$;
where $T_{z^{n}}$ denotes the type of $z^{n}$.

In the following, we define $Z^{n}\doteq\big{(}g(Y_{t})\big{)}_{t\leq 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 $\mathcal{S}_{n}$.

###### Lemma 1

The following asymptotic comparison holds:

$\displaystyle H_{\chi}(G_{[n]})=\inf_{\begin{subarray}{c}c\text{ coloring of
}G_{[n]}\\\ \text{s.t.
}c\in\mathcal{S}_{n}\end{subarray}}H(c(X^{n},Z^{n}))+O(\log n).$ (26)

###### Lemma 2

Let $N\in\mathbb{N}^{\star}$; let $G=(\mathcal{V},\mathcal{E},P_{V})$ and for
all $i\leq N$, let $\tilde{G}_{i}=(\mathcal{V}_{i},\mathcal{E}_{i},P_{V_{i}})$
be probabilistic graphs such that $G=\bigsqcup_{i}\tilde{G}_{i}$ and
$\tilde{G}_{1}\simeq...\simeq\tilde{G}_{N}$. Then we have
$H_{\chi}(G)=H_{\chi}(\tilde{G}_{1})$.

###### Lemma 3

The following asymptotic comparison holds:

$\displaystyle\inf_{\begin{subarray}{c}c\text{ coloring of }G_{[n]}\\\
\text{s.t.
}c\in\mathcal{S}_{n}\end{subarray}}H(c(X^{n},Z^{n}))=n\sum_{z\in\mathcal{Z}}P_{g(Y)}(z)H_{\kappa}(G^{f}_{z})+o(n).$
(27)

The keypoint of the proof of Lemma 1 is the asymptotically negligible entropy
of the prefix $T_{Z^{n}}$ of the colorings of $\mathcal{S}_{n}$.

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):
$\big{|}H_{\chi}(G^{Q_{n}}_{[n]})-n\sum_{z\in\mathcal{Z}}Q_{n}(z)H_{\kappa}(G^{f}_{z})\big{|}\leq
n\epsilon_{n}$. Finally, uniform convergence arguments enable us to conclude.

Now let us combine these results together:

$\displaystyle R^{*}$ $\displaystyle=\frac{1}{n}H_{\chi}(G_{[n]})+o(1)$ (28)
$\displaystyle=\frac{1}{n}\inf_{\begin{subarray}{c}c\text{ coloring of
}G_{[n]}\\\ \text{s.t.
}c\in\mathcal{S}_{n}\end{subarray}}H(c(X^{n},Z^{n}))+o(1)$ (29)
$\displaystyle=\sum_{z\in\mathcal{Z}}P_{g(Y)}(z)H_{\kappa}(G^{f}_{z})+o(1),$
(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.

###  VI-C Proof of Lemmas 1, 2, 3

Proof of Lemma 1. Let $c_{n}^{*}$ be the coloring of $G_{[n]}$ with minimal
entropy. Then we have:

$\displaystyle H_{\chi}(G_{[n]})$ $\displaystyle=\inf_{c\text{ coloring of
}G_{[n]}}H(c(X^{n},Z^{n}))$ (31)
$\displaystyle\leq\inf_{\begin{subarray}{c}c\text{ coloring of }G_{[n]}\\\
\text{s.t. }c\in\mathcal{S}_{n}\end{subarray}}H(c(X^{n},Z^{n}))$ (32)
$\displaystyle=\inf_{\begin{subarray}{c}c:(x^{n},z^{n})\\\
\mapsto(T_{z^{n}},\tilde{c}(x^{n},z^{n}))\end{subarray}}H(T_{Z^{n}},\tilde{c}(X^{n},Z^{n}))$
(33) $\displaystyle\leq H(T_{Z^{n}})+H(c_{n}^{*}(X^{n},Z^{n}))$ (34)
$\displaystyle=H_{\chi}(G_{[n]})+O(\log n),$ (35)

where (33) comes from Definition VI.3; (34) comes from the subadditivity of
the entropy, and the fact that
$(x^{n},z^{n})\mapsto(T_{z^{n}},c^{*}_{n}(x^{n},z^{n}))$ is a coloring of
$G_{[n]}$ that belongs to $\mathcal{S}_{n}$; and (35) comes from
$H(T_{Z^{n}})=O(\log n)$, as $\log|\Delta_{n}(\mathcal{Z})|=O(\log n)$. The
desired equality comes from the bounds $H_{\chi}(G_{[n]})$ and
$H_{\chi}(G_{[n]})+O(\log n)$ on (32).

Proof of Lemma 2. Let $(\tilde{G}_{i})_{i\leq N}$ be isomorphic probabilistic
graphs and $G$ such that $G=\bigsqcup_{i}\tilde{G}_{i}$. Let
$c_{1}^{*}:\mathcal{V}_{1}\rightarrow\mathcal{C}$ be the coloring of
$\tilde{G}_{1}$ with minimal entropy, and let $c^{*}$ be the coloring of $G$
defined by

$\displaystyle c^{*}:\>$ $\displaystyle\mathcal{V}\rightarrow\mathcal{C}$ (36)
$\displaystyle v\mapsto c_{1}^{*}\circ\psi_{i_{v}\rightarrow 1}(v),$ (37)

where $i_{v}$ is the unique integer such that $v\in\mathcal{V}_{i_{v}}$, and
$\psi_{i_{v}\rightarrow 1}:\mathcal{V}_{i_{v}}\rightarrow\mathcal{V}_{1}$ is
an isomorphism between $\tilde{G}_{i_{v}}$ and $\tilde{G}_{1}$. In other words
$c^{*}$ applies the same coloring pattern $c^{*}_{1}$ on each connected
component of $G$. We have

$\displaystyle H_{\chi}(G)$ $\displaystyle\leq H(c^{*}(V))$ (38)
$\displaystyle=h\Big{(}\sum_{j\leq N}P_{i_{V}}(j)P_{c^{*}(V_{j})}\Big{)}$ (39)
$\displaystyle=h\Big{(}\sum_{j\leq N}P_{i_{V}}(j)P_{c_{1}^{*}(V_{1})}\Big{)}$
(40) $\displaystyle=H(c^{*}_{1}(V_{1}))$ (41)
$\displaystyle=H_{\chi}(\tilde{G}_{1}),$ (42)

where $h$ denotes the entropy of a distribution; (40) comes from the
definition of $c^{*}$; and (42) comes from the definition of $c_{1}^{*}$.

Now let us prove the upper bound on $H_{\chi}(\tilde{G}_{1})$. Let $c$ be a
coloring of $G$, and let
$i^{*}\doteq\operatorname*{\arg\\!\min}_{i}H(c(V_{i}))$ (i.e. $i^{*}$ is the
index of the connected component for which the entropy of the coloring induced
by $c$ is minimal). We have

$\displaystyle H(c(V))$ $\displaystyle=h\Big{(}\sum_{j\leq
N}P_{i_{V}}(j)P_{c(V_{j})}\Big{)}$ (43) $\displaystyle\geq\sum_{j\leq
N}P_{i_{V}}(j)h(P_{c(V_{j})})$ (44) $\displaystyle\geq\sum_{j\leq
N}P_{i_{V}}(j)H(c(V_{i^{*}}))$ (45) $\displaystyle\geq
H_{\chi}(\tilde{G}_{i^{*}}),$ (46) $\displaystyle=H_{\chi}(\tilde{G}_{1}),$
(47)

where (44) follows from the concavity of $h$; (45) follows from the definition
of $i^{*}$; (46) comes from the fact that $c$ induces a coloring of
$\tilde{G}_{i^{*}}$; (47) comes from the fact that $\tilde{G}_{1}$ and
$\tilde{G}_{i^{*}}$ are isomorphic. Now, we can combine the bounds (42) and
(47): for all coloring $c$ of $G$ we have

$\displaystyle H_{\chi}(G)\leq H_{\chi}(\tilde{G}_{1})\leq H(c(V)),$ (48)

which yields the desired equality when taking the infimum over $c$.

Proof of Lemma 3. For all $Q_{n}\in\Delta_{n}(\mathcal{Z})$, let

$\displaystyle
G^{Q_{n}}_{[n]}=\bigsqcup_{\begin{subarray}{c}z^{n}\in\mathcal{Z}^{n}\\\
T_{z^{n}}=Q_{n}\end{subarray}}\bigvee_{t\leq n}G^{f}_{z_{t}},$ (49)

with the probability distribution induced by $P^{n}_{X,Z}$. This graph is
formed of the connected components of $G_{[n]}$ whose corresponding $z^{n}$
has type $Q_{n}$. We need to find an equivalent for
$H_{\chi}(G^{Q_{n}}_{[n]})$. Since $G^{Q_{n}}_{[n]}$ is a disjoint union of
isomorphic graphs, we can use Lemma 2:

$\displaystyle
H_{\chi}(G^{Q_{n}}_{[n]})=H_{\chi}\bigg{(}\bigvee_{z\in\mathcal{Z}}(G^{f}_{z})^{\vee
nQ_{n}(z)}\bigg{)}.$ (50)

On one hand,

$\displaystyle H_{\chi}\bigg{(}\bigvee_{z\in\mathcal{Z}}(G^{f}_{z})^{\vee
nQ_{n}(z)}\bigg{)}$ $\displaystyle\geq
H_{\kappa}\bigg{(}\bigvee_{z\in\mathcal{Z}}(G^{f}_{z})^{\vee
nQ_{n}(z)}\bigg{)}$ (51)
$\displaystyle=n\sum_{z\in\mathcal{Z}}Q_{n}(z)H_{\kappa}(G^{f}_{z}),$ (52)

where (51) comes from $H_{\kappa}\leq H_{\chi}$ [3, Lemma 14], (52) comes from
(14). On the other hand,

$\displaystyle\\!\\!\\!H_{\chi}\bigg{(}\bigvee_{z\in\mathcal{Z}}(G^{f}_{z})^{\vee
nQ_{n}(z)}\bigg{)}$
$\displaystyle\leq\sum_{z\in\mathcal{Z}}Q_{n}(z)H_{\chi}((G^{f}_{z})^{\vee
n})$ (53)
$\displaystyle=n\sum_{z\in\mathcal{Z}}Q_{n}(z)H_{\kappa}(G^{f}_{z})+n\epsilon_{n},$
(54)

where $\epsilon_{n}\doteq\max_{z}\frac{1}{n}H_{\chi}((G^{f}_{z})^{\vee
n})-H_{\kappa}(G^{f}_{z})$ is a quantity that does not depend on $Q_{n}$ and
satisfies $\lim_{n\rightarrow\infty}\epsilon_{n}=0$; (53) comes from the
subadditivity of $H_{\chi}$. Combining equations (50), (52) and (54) yields

$\displaystyle\left|H_{\chi}(G^{Q_{n}}_{[n]})-n\sum_{z\in\mathcal{Z}}Q_{n}(z)H_{\kappa}(G^{f}_{z})\right|\leq
n\epsilon_{n}.$ (55)

Now, we have an equivalent for $H_{\chi}(G^{Q_{n}}_{[n]})$.

$\displaystyle\inf_{\begin{subarray}{c}c\text{ coloring of }G_{[n]}\\\
\text{s.t. }c\in\mathcal{S}_{n}\end{subarray}}H(c(X^{n},Z^{n}))$ (56)
$\displaystyle=$ $\displaystyle\inf_{\begin{subarray}{c}c:(x^{n},z^{n})\\\
\mapsto(T_{z^{n}},\tilde{c}(x^{n},z^{n}))\end{subarray}}H(\tilde{c}(X^{n},Z^{n})|T_{Z^{n}})+H(T_{Z^{n}})$
(57) $\displaystyle=$
$\displaystyle\inf_{\begin{subarray}{c}c:(x^{n},z^{n})\\\
\mapsto(T_{z^{n}},\tilde{c}(x^{n},z^{n}))\end{subarray}}\sum_{Q_{n}\in\Delta_{n}(\mathcal{Z})}P_{T_{Z^{n}}}(Q_{n})$
$\displaystyle H(\tilde{c}(X^{n},Z^{n})|T_{Z^{n}}=Q_{n})+O(\log n)$ (58)
$\displaystyle=$
$\displaystyle\sum_{Q_{n}\in\Delta_{n}(\mathcal{Z})}P_{T_{Z^{n}}}(Q_{n})\inf_{c_{Q_{n}}\text{
coloring of }G^{Q_{n}}_{[n]}}$ $\displaystyle
H(c_{Q_{n}}(X^{n},Z^{n})|T_{Z^{n}}=Q_{n})+O(\log n)$ (59) $\displaystyle=$
$\displaystyle\sum_{Q_{n}\in\Delta_{n}(\mathcal{Z})}P_{T_{Z^{n}}}(Q_{n})H_{\chi}(G^{Q_{n}}_{[n]})+O(\log
n)$ (60) $\displaystyle=\>$
$\displaystyle\sum_{Q_{n}\in\Delta_{n}(\mathcal{Z})}P_{T_{Z^{n}}}(Q_{n})\left(n\sum_{z\in\mathcal{Z}}Q_{n}(z)H_{\kappa}(G^{f}_{z})\pm
n\epsilon_{n}\right)$ $\displaystyle+O(\log n)$ (61) $\displaystyle=\>$
$\displaystyle
n\sum_{Q_{n}\in\Delta_{n}(\mathcal{Z})}2^{-nD(Q_{n}\|P_{g(Y)})+o(n)}\left(\sum_{z\in\mathcal{Z}}Q_{n}(z)H_{\kappa}(G^{f}_{z})\right)$
$\displaystyle\pm n\epsilon_{n}+O(\log n)$ (62) $\displaystyle=\>$
$\displaystyle n\sum_{z\in\mathcal{Z}}P_{g(Y)}(z)H_{\kappa}(G^{f}_{z})+o(n),$
(63)

where (58) comes from $H(T_{Z^{n}})=O(\log n)$, as
$\log|\Delta_{n}(\mathcal{Z})|=O(\log n)$; (59) follows from the fact that the
entropy of $\tilde{c}$ can be minimized independently on each
$G^{Q_{n}}_{[n]}$; (60) follows from the definition of $G^{Q_{n}}_{[n]}$; (61)
comes from (55); (62) comes from [21, Lemma 2.6] and the fact that
$\epsilon_{n}$ does not depend on $Q_{n}$.

## 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] I. Csiszár and J. Körner, _Information theory: coding theorems for discrete memoryless systems_. Cambridge University Press, 2011.