Multiple Access Channel Resolvability Codes from Source Resolvability Codes
Rumia Sultana and Rémi A. Chou Part of this work has been presented at the
2019 Annual Allerton Conference on Communication, Control, and Computing
sultana2019explicit, and the 2020 IEEE International Symposium on Information
Theory sultana2020explicit. This work was supported in part by NSF grant
CCF-1850227. E-mails<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

We show that the problem of code construction for multiple access channel
(MAC) resolvability can be reduced to the simpler problem of code construction
for source resolvability. Specifically, we propose a MAC resolvability code
construction that relies on a combination of multiple source resolvability
codes, used in a black-box manner, and leverages randomness recycling
implemented via distributed hashing and block-Markov coding. Since explicit
source resolvability codes are known, our results also yield the first
explicit coding schemes that achieve the entire MAC resolvability region for
any discrete memoryless multiple-access channel with binary input alphabets.

##  I Introduction

The concept of multiple access channel (MAC) resolvability has been introduced
in [3] as a natural extension of channel resolvability for point-to-point
channels [4]. MAC resolvability represents a fundamental primitive that finds
applications in a large variety of network information-theoretic problems,
including strong secrecy for multiple access wiretap channels [5, 6],
cooperative jamming [5], semantic security for multiple access wiretap
channels [7], and strong coordination in networks [8]. These applications are,
however, restricted by the fact that no explicit coding scheme is known to
optimally implement MAC resolvability. Note indeed that [3, 7] only provide
existence results and no explicit code constructions. The objective of this
paper is to bridge this gap by providing explicit coding schemes that achieve
the MAC resolvability region [7]. While previous works have been successful in
providing explicit coding schemes for channel resolvability over point-to-
point channels,111Explicit constructions based on polar codes for channel
resolvability have been proposed for binary _symmetric_ point-to-point
channels [9] and discrete memoryless point-to-point channels whose input
alphabets have prime cardinalities [10]. Another explicit construction based
on injective group homomorphisms has been proposed in [11] for channel
resolvability over binary _symmetric_ point-to-point channels. Low-complexity,
but non-explicit, linear coding schemes for channel resolvability over
arbitrary memoryless point-to-point channels have also been proposed in [12].
to the best of our knowledge, the only known explicit constructions for MAC
resolvability are those of [13]. However, the explicit constructions in [13],
one based on invertible extractors and a second one based on injective group
homomorphisms, are limited to _symmetric_ multiple access channels, and do not
seem to generalize to _arbitrary_ multiple access channels.

In this paper, we propose a novel approach to the construction of MAC
resolvability codes by showing that such a construction can be reduced to the
simpler problem of code construction for source resolvability [14]. Since
explicit constructions of source resolvability codes are known, e.g., [10],
our results yield the first explicit construction of MAC resolvability codes
that achieve the entire MAC resolvability region of arbitrary multiple access
channels with binary input alphabets. More specifically, our approach to the
construction of MAC resolvability codes relies on a combination of
appropriately chosen source resolvability codes, and leverages randomness
recycling implemented with distributed hashing and a block-Markov encoding
scheme. In essence, the idea of block-Markov encoding to recycle randomness is
closely related to recursive constructions of seeded extractors in the
computer science literature, e.g., [15]. We stress that our construction is
valid independently from the way those source resolvability codes are
implemented. Additionally, to avoid time-sharing whenever it is known to be
unnecessary, we also show how to implement the idea of rate splitting, first
developed in [16] for multiple access channel coding, for the MAC
resolvability problem with two transmitters. Note that the main difference
with [13], is that our approach aims to reduce the construction of MAC
resolvability codes to a simpler problem, namely the construction of source
resolvability codes, whereas [13] attempts a code construction directly
adapted to multiple access channels.

The remainder of the paper is organized as follows. The problem statement is
provided in Section II. Our main result is summarized in Section III. Our
proposed coding scheme and its analysis are provided in Section IV and Section
V, respectively. While our main result focuses on multiple access channels
with two transmitters, we discuss an extension of our result to an arbitrary
number of transmitters in Section VI. Finally, Section VII provides concluding
remarks.

##  II Problem Statement and Review of Source Resolvability

###  II-A Notation

For $a,b\in\mathbb{R}$, define $\llbracket a,b\rrbracket\triangleq[\lfloor
a\rfloor,\lceil b\rceil]\cap\mathbb{N}$. The components of a vector $X^{1:N}$
of size $N$ are denoted with superscripts, i.e.,
$X^{1:N}\triangleq(X^{1},X^{2},\ldots,X^{N})$. For two probability
distributions $p$ and $q$ defined over the same alphabet $\mathcal{X}$, the
variational distance $\mathbb{V}(p,q)$ between $p$ and $q$ is defined as
$\mathbb{V}(p,q)\triangleq\sum_{x\in\mathcal{X}}|p(x)-q(x)|.$

###  II-B Problem Statement

Consider a discrete memoryless multiple access channel
$(\mathcal{X}\times\mathcal{Y},q_{Z|XY},\mathcal{Z})$, where
$\mathcal{X}=\\{0,1\\}=\mathcal{Y}$, and $\mathcal{Z}$ is a finite alphabet. A
target distribution $q_{Z}$ is defined as the channel output distribution when
the input distributions are $q_{X}$ and $q_{Y}$, i.e.,

$\displaystyle\forall
z\in\mathcal{Z},q_{Z}(z)\triangleq\displaystyle\sum_{x\in\mathcal{X}}\sum_{y\in\mathcal{Y}}q_{Z|XY}(z|x,y)q_{X}(x)q_{Y}(y).$
(1)

######  Definition 1.

A $(2^{NR_{1}},2^{NR_{2}},N)$ code for the memoryless multiple access channel
$(\mathcal{X}\times\mathcal{Y},q_{Z|XY},\mathcal{Z})$ consists of

  * •

Two randomization sequences $S_{1}$ and $S_{2}$ independent and uniformly
distributed over $\mathcal{S}_{1}\triangleq\llbracket 1,2^{NR_{1}}\rrbracket$
and $\mathcal{S}_{2}\triangleq~{}\llbracket 1,2^{NR_{2}}\rrbracket$,
respectively;

  * •

Two encoding functions $f_{1,N}:\mathcal{S}_{1}\to\mathcal{X}^{N}$ and
$f_{2,N}:\mathcal{S}_{2}\to\mathcal{Y}^{N}$;

and operates as follows: Transmitters 1 and 2 form $f_{1,N}(S_{1})$ and
$f_{2,N}(S_{2})$, respectively, which are sent over the channel
$(\mathcal{X}\times\mathcal{Y},q_{Z|XY},\mathcal{Z})$.

######  Definition 2.

$(R_{1},R_{2})$ is an achievable resolvability rate pair for the memoryless
multiple access channel $(\mathcal{X}\times\mathcal{Y},q_{Z|XY},\mathcal{Z})$
if there exists a sequence of $(2^{NR_{1}},2^{NR_{2}},N)$ codes such that

$\displaystyle\lim_{N\to+\infty}\mathbb{V}(\widetilde{p}_{Z^{1:N}},q_{Z^{1:N}})=0,$

where $q_{Z^{1:N}}\triangleq\prod_{i=1}^{N}q_{Z}$ with $q_{Z}$ defined in
$(1)$ and $\forall z^{1:N}\in\mathcal{Z}^{N},$

$\displaystyle\widetilde{p}_{Z^{1:N}}(z^{1:N})\triangleq\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\sum_{(s_{1},s_{2})\in\mathcal{S}_{1}\times\mathcal{S}_{2}}\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\frac{q_{Z^{1:N}|X^{1:N}Y^{1:N}}\\!\left(z^{1:N}|f_{1,N}(s_{1}),f_{2,N}(s_{2})\right)}{|\mathcal{S}_{1}||\mathcal{S}_{2}|}.$

The multiple access channel resolvability region $\mathcal{R}_{q_{Z}}$ is
defined as the closure of the set of all achievable rate pairs.

######  Theorem 1 ([7, Theorem 1]).

We have $\mathcal{R}_{q_{Z}}=\mathcal{R}^{\prime}_{q_{Z}}$ with

$\displaystyle\mathcal{R}^{\prime}_{q_{Z}}\triangleq\smash{\bigcup_{p_{T},q_{X|T},q_{Y|T}}}\\!\\!\\!\\!\\!\\!\\!\\!\\!\\{(R_{1},R_{2}):I(XY;Z|T)$
$\displaystyle\leq R_{1}+R_{2},$ $\displaystyle I(X;Z|T)$ $\displaystyle\leq
R_{1},$ $\displaystyle I(Y;Z|T)$ $\displaystyle\leq R_{2}\\},$

where $p_{T}$ is defined over $\mathcal{T}\triangleq\llbracket
1,|\mathcal{Z}|+3\rrbracket$ and $q_{X|T},q_{Y|T}$ are such that, for any
$t\in\mathcal{T}$ and $z\in\mathcal{Z}$,

$\displaystyle
q_{Z}(z)=\sum_{{x\in\mathcal{X}}}\sum_{y\in\mathcal{Y}}q_{X|T}(x|t)q_{Y|T}(y|t)q_{Z|XY}(z|x,y).$

Note that reference [7] provides only the existence of a coding scheme that
achieves any rate pair in $\mathcal{R}_{q_{Z}}$. By contrast, _our goal is to
provide explicit coding schemes that can achieve the region
$\mathcal{R}_{q_{Z}}$_ by relying on source resolvability codes, which are
used in a black box manner. The notion of source resolvability is reviewed
next.

###  II-C Review of Source Resolvability

######  Definition 3.

A $(2^{NR},N)$ source resolvability code for $(\mathcal{X},q_{X})$ consists of

  * •

A randomization sequence $S$ uniformly distributed over
$\mathcal{S}\triangleq\llbracket 1,2^{NR}\rrbracket$;

  * •

An encoding function $e_{N}:\mathcal{S}\to\mathcal{X}^{N}$;

and operates as follows: The encoder forms $\widetilde{X}^{1:N}\triangleq
e_{N}(S)$ and the distribution of $\widetilde{X}^{1:N}$ is denoted by
$\widetilde{p}_{X^{1:N}}$.

######  Definition 4.

$R$ is an achievable resolution rate for a discrete memoryless source
$(\mathcal{X},q_{X})$ if there exists a sequence of $(2^{NR},N)$ source
resolvability codes such that

$\displaystyle\lim_{N\to+\infty}\mathbb{V}(\widetilde{p}_{X^{1:N}},q_{X^{1:N}})=0,$
(2)

where $q_{X^{1:N}}\triangleq\prod_{i=1}^{N}q_{X}$. The infimum of such
achievable rates is called source resolvability.

######  Theorem 2 ([4]).

The source resolvability of a discrete memoryless source $(\mathcal{X},q_{X})$
is $H(X)$.

Note that explicit low-complexity source resolvability codes can, for
instance, be obtained with polar codes as reviewed in Appendix A.

##  III Main result

Our main result is summarized as follows.

######  Theorem 3.

The coding scheme presented in Section IV, which solely relies on source
resolvability codes, used as black boxes, and two-universal hash functions
[17], achieves the entire multiple access channel resolvability region
$\mathcal{R}_{q_{Z}}$ for any discrete memoryless multiple access channel with
binary input alphabets. Moreover, time-sharing is avoided whenever it is known
to be unnecessary.

As a corollary, we obtain the first explicit construction of multiple access
channel resolvability codes that achieves the entire multiple access channel
resolvability region $\mathcal{R}_{q_{Z}}$ for any discrete memoryless
multiple access channel with binary input alphabets.

######  Corollary 1.

Since explicit constructions for source resolvability codes and two-universal
hash functions are known, e.g., [17, 18], Theorem 3 yields an explicit coding
scheme that achieves $\mathcal{R}_{q_{Z}}$ for any discrete memoryless
multiple access channel with binary input alphabets.

##  IV Coding Scheme

We explain in Section IV-A that the general construction of MAC resolvability
codes can be reduced to two special cases. Then, we provide a coding scheme
for these two special cases in Sections IV-B, IV-C.

###  IV-A Reduction of the general construction of MAC resolvability codes to
two special cases

######  Definition 5.

For the memoryless multiple access channel
$(\mathcal{X}\times\mathcal{Y},q_{Z|XY},\mathcal{Z})$ we define

$\displaystyle\mathcal{R}_{X,Y}\triangleq\\{(R_{1},R_{2}):I(XY;Z)$
$\displaystyle\leq R_{1}+R_{2},$ $\displaystyle I(X;Z)$ $\displaystyle\leq
R_{1},$ $\displaystyle I(Y;Z)$ $\displaystyle\leq R_{2}\\},$

for some product distribution $p_{X}p_{Y}$ on $\mathcal{X}\times\mathcal{Y}$.

To show the achievability of $\mathcal{R}^{\prime}_{q_{Z}}$, it is sufficient
to show the achievability of $\mathcal{R}_{X,Y}$. Indeed, note that if
$\mathcal{R}_{X,Y}$ is achievable, then
$\textup{Conv}(\bigcup_{p_{X}p_{Y}}\mathcal{R}_{X,Y})$ is also achievable,
where Conv denotes the convex hull. Hence, $\mathcal{R}^{\prime}_{q_{Z}}$ is
achievable because
$\textup{Conv}(\bigcup_{p_{X}p_{Y}}\mathcal{R}_{X,Y})\supset\mathcal{R}^{\prime}_{q_{Z}}$
by remarking that the corner points of $\mathcal{R}^{\prime}_{q_{Z}}$ are in
$\textup{Conv}(\bigcup_{p_{X}p_{Y}}\mathcal{R}_{X,Y})$. For instance, the
point $(I(X;Z|T),I(Y;Z|XT))\in\mathcal{R}^{\prime}_{q_{Z}}$ belongs to
$\textup{Conv}(\bigcup_{p_{X}p_{Y}}\mathcal{R}_{X,Y})$ since

$\displaystyle(I(X;Z|T),I(Y;Z|XT))$
$\displaystyle=\sum_{t\in\mathcal{T}}p_{T}(t)(I(X;Z|T=t),I(Y;Z|X,T=t)).$

Similarly, all the corner points of $\mathcal{R}^{\prime}_{q_{Z}}$ also belong
to $\textup{Conv}(\bigcup_{p_{X}p_{Y}}\mathcal{R}_{X,Y})$. Next, we consider
two cases to achieve the region $\mathcal{R}_{X,Y}$ for some fixed
distribution $p_{X}p_{Y}$.

  * •

Case 1 (depicted in Figure 2): $I(XY;Z)>I(X;Z)+I(Y;Z)$. In this case, it is
sufficient to achieve the dominant face $\mathcal{D}$ of $\mathcal{R}_{X,Y}$,
where

$\displaystyle\mathcal{D}\triangleq\\{(R_{1},R_{2}):R_{1}\in$
$\displaystyle[I(X;Z),I(X;Z|Y)],$ $\displaystyle R_{2}=$ $\displaystyle
I(XY;Z)-R_{1}\\}.$

  * •

Case 2 (depicted in Figure 2): $I(XY;Z)=I(X;Z)+I(Y;Z)$. In this case, only the
corner point $C$ needs to be achieved. Note that it is impossible to have
$I(XY;Z)<I(X;Z)+I(Y;Z)$ by independence of $X$ and $Y$.

Figure 1: Region $\mathcal{R}_{X,Y}$ in Case 1: $I(XY;Z)>~{}I(X;Z)+I(Y;Z)$.

Figure 2: Region $\mathcal{R}_{X,Y}$ in Case 2: $I(XY;Z)=~{}I(X;Z)+I(Y;Z)$.

###  IV-B Encoding Scheme for Case 1

Consider the region $\mathcal{R}_{X,Y}$ for some product distribution
$p_{X}p_{Y}$ on $\mathcal{X}\times\mathcal{Y}$ such that
$I(XY;Z)>I(X;Z)+I(Y;Z)$. Since $\mathcal{R}_{X,Y}$ is a contrapolymatroid
[19], to achieve the region $\mathcal{R}_{X,Y}$, it is sufficient to achieve
any rate pair $(R_{1},R_{2})$ of the dominant face $\mathcal{D}$ of
$\mathcal{R}_{X,Y}$. We next show that $\mathcal{D}$ can be achieved through
rate-splitting using the following lemma proved in Appendix C.

######  Lemma 1.

Consider $f:~{}\mathcal{Y}\times~{}\mathcal{Y}\rightarrow\mathcal{Y}$,
$(u,v)\mapsto\max(u,v)$, and form
$(\mathcal{Y}\times\mathcal{Y},p_{U_{\epsilon}}p_{V_{\epsilon}}),\epsilon\in[0,1]$,
such that $p_{U_{\epsilon}V_{\epsilon}}=p_{U_{\epsilon}}p_{V_{\epsilon}}$,
$p_{f(U_{\epsilon},V_{\epsilon})}=p_{Y}$, for fixed
$(y,u),p_{f(U_{\epsilon},V_{\epsilon})|U_{\epsilon}}(y|u)$ is a continuous
function of $\epsilon$, and

$\displaystyle U_{\epsilon=0}=0=V_{\epsilon=1},$ (3) $\displaystyle
U_{\epsilon=1}=f(U_{\epsilon=1},V_{\epsilon=1}),$ (4) $\displaystyle
V_{\epsilon=0}=f(U_{\epsilon=0},V_{\epsilon=0}).$ (5)

The above construction is indeed possible as shown in [16, Example 3]. Then,
we have $I(XY;Z)=R_{1}+R_{U}+R_{V}$, where we have defined the functions

$\displaystyle R_{1}:[0,1]\to\ \mathbb{R}^{+},\epsilon\mapsto
I(X;Z|U_{\epsilon}),$ $\displaystyle R_{U}:[0,1]\to\
\mathbb{R}^{+},\epsilon\mapsto I(U_{\epsilon};Z),$ $\displaystyle
R_{V}:[0,1]\to\ \mathbb{R}^{+},\epsilon\mapsto
I(V_{\epsilon};Z|U_{\epsilon}X).$

Moreover, $R_{1}$ is continuous with respect to $\epsilon$ and
$[I(X;Z),I(X;Z|Y)]$ is contained in its image.

When the context is clear, we do not explicitly write the dependence of $U$
and $V$ with respect to $\epsilon$ by dropping the subscript $\epsilon$.

Fix a point $(R_{1},R_{2})$ in $\mathcal{D}$. By Lemma 1, there exists a joint
probability distribution $q_{UVXYZ}$ over
$\mathcal{Y}\times\mathcal{Y}\times\mathcal{X}\times\mathcal{Y}\times\mathcal{Z}$
such that $R_{1}=I(X;Z|U)$, $R_{2}=R_{U}+R_{V}$ with $R_{U}=I(U;Z)$ and
$R_{V}=I(V;Z|UX)$. We provide next a coding scheme that will be shown to
achieve the point $(R_{1},R_{2})$. The encoding scheme operates over
$k\in\mathbb{N}$ blocks of length $N$ and is described in Algorithms 1 and 2.
A high level description of the encoding scheme is as follows. For the first
transmitter, we perform source resolvability for the discrete memoryless
source $(\mathcal{X},q_{X})$ using randomness with rate $H(X)$ in Block $1$.
Using Lemma 1, we perform rate splitting for the second transmitter to get two
virtual users such that one virtual user is associated with the discrete
memoryless source $(\mathcal{Y},q_{U})$ and the other virtual user is
associated with the discrete memoryless source $(\mathcal{Y},q_{V})$. Then, we
perform source resolvability with rates $H(U)$ and $H(V)$ for the discrete
memoryless sources$(\mathcal{Y},q_{U})$ and $(\mathcal{Y},q_{V})$,
respectively. For the next encoding blocks, we proceed as in Block $1$ using
source resolvability and rate splitting except that part of the randomness is
now recycled from the previous block. More precisely, we recycle the bits of
randomness used at the inputs of the channel in the previous block that are
almost independent from the channel output. The rates of those bits will be
shown to approach $H(X|UZ)$, $H(U|Z)$, $H(V|UZX)$ for User $1$ and the two
virtual users, respectively.

  * •

The encoding at Transmitter $1$ is described in Algorithm 1 and uses

    * –

A hash function $G_{X}:\\{0,1\\}^{N}\longrightarrow\\{0,1\\}^{r_{X}}$ chosen
uniformly at random in a family of two-universal hash functions, where the
output length of the hash function $G_{X}$ is defined as follows

$\displaystyle{r_{X}}\triangleq N(H(X|UZ)-\epsilon_{1}/2),$ (6)

where $\epsilon_{1}\triangleq 2(\delta_{\mathcal{A}}(N)+\xi)$,
$\delta_{\mathcal{A}}(N)\triangleq\log(|\mathcal{Y}|^{2}|\mathcal{X}|+3)\sqrt{\frac{2}{N}(3+\log
N)}$, $\xi>0$.

    * –

A source resolvability code for the discrete memoryless source
$(\mathcal{X},q_{X})$ with encoder function $e_{N}^{X}$ and rate
$H(X)+\frac{\epsilon_{1}}{2}$, such that the distribution of the encoder
output $\widetilde{p}_{X^{1:N}}$ satisfies
$\mathbb{V}(\widetilde{p}_{X^{1:N}},q_{X^{1:N}})\leq\delta(N)$, where
$\delta(N)$ is such that $\lim_{N\to+\infty}\delta(N)=0$.

In Algorithm 1, the hash function output $\widetilde{E}_{i}$, $i\in\llbracket
2,k\rrbracket$, with length $r_{X}$ corresponds to recycled randomness from
Block $i-1$.

  * •

The encoding at Transmitter $2$ is described in Algorithm 2 and uses

    * –

Two hash functions $G_{U}:\\{0,1\\}^{N}\longrightarrow\\{0,1\\}^{r_{U}}$ and
$G_{V}:\\{0,1\\}^{N}\longrightarrow\\{0,1\\}^{r_{V}}$ chosen uniformly at
random in families of two-universal hash functions, where the output lengths
of the hash functions $G_{U}$ and $G_{V}$ are defined as follows

$\displaystyle\quad r_{U}$ $\displaystyle\triangleq N(H(U|Z)-\epsilon_{1}/2),$
$\displaystyle\quad r_{V}$ $\displaystyle\triangleq
N(H(V|UZX)-\epsilon_{1}/2).$ (7)

    * –

A source resolvability code for the discrete memoryless source
$(\mathcal{U},q_{U})$ with encoding function $e_{N}^{U}$ and rate
$H(U)+\frac{\epsilon_{1}}{2}$, such that the distribution of the encoder
output $\widetilde{p}_{U^{1:N}}$ satisfies
$\mathbb{V}(\widetilde{p}_{U^{1:N}},q_{U^{1:N}})\leq\delta(N)$, where
$\delta(N)$ is such that $\lim_{N\to+\infty}\delta(N)=0$.

    * –

A source resolvability code for the discrete memoryless source
$(\mathcal{V},q_{V})$ with encoding function $e_{N}^{V}$ and rate
$H(V)+\frac{\epsilon_{1}}{2}$, such that the distribution of the encoder
output $\widetilde{p}_{V^{1:N}}$ satisfies
$\mathbb{V}(\widetilde{p}_{V^{1:N}},q_{V^{1:N}})\leq\delta(N)$, where
$\delta(N)$ is such that $\lim_{N\to+\infty}\delta(N)=0$.

In Algorithm 2, the hash function outputs $\widetilde{D}_{i}$ and
$\widetilde{F}_{i}$, $i\in\llbracket 2,k\rrbracket$, with lengths $r_{U}$ and
$r_{V}$, respectively, correspond to recycled randomness from Block $i-1$.

The dependencies between the random variables involved in Algorithms 1 and 2
are represented in Figure 3.

Algorithm 1 Encoding algorithm at Transmitter $1$ in Case 1

0: A vector $E_{1}$ of $N(H(X)+\epsilon_{1})$ uniformly distributed bits, and
for $i\in\llbracket 2,k\rrbracket$, a vector $E_{i}$ of
$N(I(X;UZ)+\epsilon_{1})$ uniformly distributed bits.

1: for Block $i=1$ to $k$ do

2: if $i=1$ then

3: Define $\widetilde{X}_{1}^{1:N}\triangleq e^{X}_{N}(E_{1})$

4: else if $i>1$ then

5: Define $\widetilde{E}_{i}\triangleq G_{X}(\widetilde{X}_{i-1}^{1:N})$

6: Define $\widetilde{X}_{i}^{1:N}\triangleq e^{X}_{N}(\widetilde{E}_{i}\lVert
E_{i})$, where $\lVert$ denotes concatenation

7: end if

8: Send $\widetilde{X}_{i}^{1:N}$ over the channel

9: end for

Algorithm 2 Encoding algorithm at Transmitter $2$ in Case 1

0: A vector $D_{1}$ of $N(H(U)+\epsilon_{1})$ uniformly distributed bits, and
for $i\in\llbracket 2,k\rrbracket$, a vector $D_{i}$ of
$N(I(U;Z)+\epsilon_{1})$ uniformly distributed bits. A vector $F_{1}$ of
$N(H(V)+\epsilon_{1})$ uniformly distributed bits, and for $i\in\llbracket
2,k\rrbracket$, a vector $F_{i}$ of $N(I(V;UZX)+\epsilon_{1})$ uniformly
distributed bits.

1: for Block $i=1$ to $k$ do

2: if $i=1$ then

3: Define $\widetilde{U}_{1}^{1:N}\triangleq e^{U}_{N}(D_{1})$ and
$\widetilde{V}_{1}^{1:N}\triangleq e^{V}_{N}(F_{1})$

4: else if $i>1$ then

5: Define $\widetilde{D}_{i}\triangleq G_{U}(\widetilde{U}_{i-1}^{1:N})$ and
$\widetilde{F}_{i}\triangleq G_{V}(\widetilde{V}_{i-1}^{1:N})$

6: Define $\widetilde{U}_{i}^{1:N}\triangleq e^{U}_{N}(\widetilde{D}_{i}\lVert
D_{i})$ and $\widetilde{V}_{i}^{1:N}\triangleq
e^{V}_{N}(\widetilde{F}_{i}\lVert F_{i})$

7: Define $\widetilde{Y}_{i}^{1:N}\triangleq
f(\widetilde{U}_{i}^{1:N},\widetilde{V}_{i}^{1:N})$, where $f$ is defined in
Lemma 1

8: end if

9: Send $\widetilde{Y}_{i}^{1:N}$ over the channel

10: end for

Figure 3: Dependence graph for the random variables involved in the encoding
for Case 1. $N_{i}$, $i\in\llbracket 1,k\rrbracket$, is the channel noise
corresponding to the transmission over Block $i$. For Block $i\in\llbracket
2,k\rrbracket$, $(D_{i},\widetilde{D}_{i}$), $(F_{i},\widetilde{F}_{i}$),
$(E_{i},\widetilde{E}_{i}$) are the random sequences used at the encoders to
form $\widetilde{U}^{1:N}_{i}$, $\widetilde{V}^{1:N}_{i}$,
$\widetilde{X}^{1:N}_{i}$, respectively.

###  IV-C Encoding Scheme for Case 2

The encoding scheme for Case $2$ is same as the encoding for Case $1$ with the
substitutions $U\leftarrow\emptyset$ and $V\leftarrow Y$.

##  V Coding Scheme Analysis

###  V-A Coding Scheme Analysis for Case $1$

First, we show that in each encoding Block $i\in\llbracket 1,k\rrbracket$, the
random variables
$\widetilde{U}_{i}^{1:N},\widetilde{V}_{i}^{1:N},\widetilde{X}_{i}^{1:N},\widetilde{Y}_{i}^{1:N},\widetilde{Z}_{i}^{1:N}$
induced by the coding scheme approximate well the target distribution
$q_{U^{1:N}V^{1:N}X^{1:N}Y^{1:N}Z^{1:N}}$. Then, we show that the target
output distribution $q_{Z^{1:kN}}$ is well approximated jointly over all
blocks. To do so, we show that the recycled randomness
$\widetilde{E}_{i},\widetilde{D}_{i},\widetilde{F}_{i}$ in Block
$i\in\llbracket 2,k\rrbracket$ that appears in Line $5$ of Algorithms 1 and 2
is almost independent of the channel output in Block $i-1$. Note that
randomness recycling is studied via a distributed version of the leftover hash
lemma stated in Lemma 17. Finally, we prove that the encoding scheme of
Section IV-B achieves the desired rate-tuple.

For convenience, define $\widetilde{E}_{1}\triangleq\emptyset$,
$\widetilde{D}_{1}\triangleq\emptyset$, and
$\widetilde{F}_{1}\triangleq\emptyset$. Let

$\displaystyle\widetilde{p}_{E_{i}D_{i}F_{i}X^{1:N}_{i}U^{1:N}_{i}V^{1:N}_{i}Y^{1:N}_{i}Z^{1:N}_{i}}$
(8)

denote the joint probability distribution of the random variables
$\widetilde{E}_{i},\widetilde{D}_{i},\widetilde{F}_{i},\widetilde{X}^{1:N}_{i},\widetilde{U}^{1:N}_{i},\widetilde{V}^{1:N}_{i},\widetilde{Y}^{1:N}_{i}$,
and $\widetilde{Z}^{1:N}_{i}$ created in Block $i\in\llbracket 1,k\rrbracket$
of the coding scheme of Section IV-B.

We first prove in the following lemma that in Block $i\in\llbracket
2,k\rrbracket$, if the inputs $\widetilde{X}_{i-1}^{1:N}$,
$\widetilde{U}_{i-1}^{1:N}$, $\widetilde{V}_{i-1}^{1:N}$ of the hash functions
$G_{X}$, $G_{U}$, $G_{V}$, respectively, are replaced by $X^{1:N}$, $U^{1:N}$,
$V^{1:N}$ distributed according to
$q_{X^{1:N}U^{1:N}V^{1:N}}\triangleq\prod_{i=1}^{N}q_{XUV}$, then the output
of these hash functions are almost jointly uniformly distributed.

######  Lemma 2.

Let $p^{unif}_{\bar{E}},p^{unif}_{\bar{D}},p^{unif}_{\bar{F}}$ denote the
uniform distributions over $\\{0,1\\}^{r_{X}}$, $\\{0,1\\}^{r_{U}}$,
$\\{0,1\\}^{r_{V}}$, respectively. Then,

$\displaystyle\mathbb{V}\left(q_{G_{X}({X}^{1:N})G_{U}({U}^{1:N})G_{V}({V}^{1:N})Z^{1:N}},p^{unif}_{\bar{E}}p^{unif}_{\bar{D}}p^{unif}_{\bar{F}}q_{Z^{1:N}}\right)$
$\displaystyle\phantom{--}\leq{\color[rgb]{0,0,0}\delta^{(0)}(N)},$

where ${\color[rgb]{0,0,0}\delta^{(0)}(N)}\triangleq 2/N+\sqrt{7}\cdot
2^{-\frac{N\xi}{2}}.$

###### Proof.

Define $\mathcal{A}\triangleq\\{U,V,X\\}$ and, for any
$\mathcal{S}\subseteq\mathcal{A}$, define
$T_{\mathcal{S}}\triangleq(W)_{W\in\mathcal{S}}.$ Hence, we have

$\displaystyle T_{\mathcal{A}}^{1:N}$
$\displaystyle=({{X}}^{1:N},{{U}}^{1:N},{{V}}^{1:N}),$ $\displaystyle
q_{T_{\mathcal{A}}^{1:N}Z^{1:N}}$
$\displaystyle=q_{X^{1:N}U^{1:N}V^{1:N}Z^{1:N}}.$

Then, by Lemma 16 in Appendix B, applied to the product distribution
$q_{T_{\mathcal{A}}^{1:N}Z^{1:N}}$, there exists a subnormalized non-negative
function $w_{{T_{\mathcal{A}}^{1:N}}Z^{1:N}}$ such that, for any
$\mathcal{S}\subseteq\mathcal{A}$,

$\displaystyle\mathbb{V}({w}_{X^{1:N}U^{1:N}V^{1:N}Z^{1:N}},q_{X^{1:N}U^{1:N}V^{1:N}Z^{1:N}})\leq
1/N,$ (9) $\displaystyle
H_{\infty}({w}_{{{T}_{\mathcal{S}}^{1:N}}Z^{1:N}}|q_{Z^{1:N}})\geq\\!\\!NH({{T}_{\mathcal{S}}}|Z)-N\delta_{\mathcal{S}}(N),$
(10)

where the min-entropy
$H_{\infty}({w}_{{{T}_{\mathcal{S}}^{1:N}}Z^{1:N}}|q_{Z^{1:N}})$ is defined in
Lemma 16 in Appendix B, and
$\delta_{\mathcal{S}}(N)\triangleq\log(\lvert\mathcal{T}_{\mathcal{S}}\rvert+3)\sqrt{\frac{2}{N}(3+\log
N)}$ with $\mathcal{T}_{\mathcal{S}}$ is the domain over which
${T}_{\mathcal{S}}$ is defined. Next, let $q_{EDF}$ define the joint
distribution of

$\displaystyle E\triangleq G_{X}(X^{1:N}),D\triangleq
G_{U}(U^{1:N}),F\triangleq G_{V}(V^{1:N}),$ (11)

where $U^{1:N}$, $V^{1:N}$, and $X^{1:N}$ are distributed according to
$q_{U^{1:N}V^{1:N}X^{1:N}}$. Then, we have

$\displaystyle\mathbb{V}(q_{EDFZ^{1:N}},p^{unif}_{\bar{E}}p^{unif}_{\bar{D}}p^{unif}_{\bar{F}}q_{Z^{1:N}})$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\mathbb{V}(q_{EDFZ^{1:N}},w_{EDFZ^{1:N}})$
$\displaystyle\phantom{--}+\mathbb{V}(w_{EDFZ^{1:N}},p^{unif}_{\bar{E}}p^{unif}_{\bar{D}}p^{unif}_{\bar{F}}q_{Z^{1:N}})$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}\mathbb{V}(q_{G_{X}({X}^{1:N})G_{U}({U}^{1:N})G_{V}({V}^{1:N})Z^{1:N}},$
$\displaystyle\phantom{----}w_{G_{X}({X}^{1:N})G_{U}({U}^{1:N})G_{V}({V}^{1:N})Z^{1:N}})$
$\displaystyle\phantom{--}+\mathbb{V}(w_{EDFZ^{1:N}},p^{unif}_{\bar{E}}p^{unif}_{\bar{D}}p^{unif}_{\bar{F}}q_{Z^{1:N}})$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{\leq}}\mathbb{V}(q_{X^{1:N}U^{1:N}V^{1:N}Z^{1:N}},{w}_{X^{1:N}U^{1:N}V^{1:N}Z^{1:N}})$
$\displaystyle\phantom{--}+\mathbb{V}(w_{EDFZ^{1:N}},p^{unif}_{\bar{E}}p^{unif}_{\bar{D}}p^{unif}_{\bar{F}}q_{Z^{1:N}})$
$\displaystyle\stackrel{{\scriptstyle(d)}}{{\leq}}1/N+\mathbb{V}(w_{EDFZ^{1:N}},p^{unif}_{\bar{E}}p^{unif}_{\bar{D}}p^{unif}_{\bar{F}}w_{Z^{1:N}})$
$\displaystyle\phantom{--}+\mathbb{V}(p^{unif}_{\bar{E}}p^{unif}_{\bar{D}}p^{unif}_{\bar{F}}w_{Z^{1:N}},p^{unif}_{\bar{E}}p^{unif}_{\bar{D}}p^{unif}_{\bar{F}}q_{Z^{1:N}})$
$\displaystyle\stackrel{{\scriptstyle(e)}}{{\leq}}2/N+\mathbb{V}(w_{EDFZ^{1:N}},p^{unif}_{\bar{E}}p^{unif}_{\bar{D}}p^{unif}_{\bar{F}}w_{Z^{1:N}})$
$\displaystyle\stackrel{{\scriptstyle(f)}}{{\leq}}2/N+\sqrt{{\displaystyle\sum_{\begin{subarray}{c}{\mathcal{S}\subseteq\mathcal{A}},{\mathcal{S}\neq\emptyset}\end{subarray}}}2^{r_{\mathcal{S}}-H_{\infty}({w}_{{{T}_{\mathcal{S}}^{1:N}}Z^{1:N}}|q_{Z^{1:N}})}}$
$\displaystyle\stackrel{{\scriptstyle(g)}}{{\leq}}2/N+{{{\sqrt{{\displaystyle\sum_{\begin{subarray}{c}{\mathcal{S}\subseteq\mathcal{A}},{\mathcal{S}\neq\emptyset}\end{subarray}}}2^{r_{\mathcal{S}}-NH(T_{\mathcal{S}}|Z)+N\delta_{\mathcal{S}}(N)}}}}}$
$\displaystyle\stackrel{{\scriptstyle(h)}}{{\leq}}2/N+{{{\sqrt{{\displaystyle\sum_{\begin{subarray}{c}{\mathcal{S}\subseteq\mathcal{A}},{\mathcal{S}\neq\emptyset}\end{subarray}}}2^{r_{\mathcal{S}}-NH(T_{\mathcal{S}}|Z)+N\delta_{\mathcal{A}}(N)}}}}}$

where $(a)$ holds by the triangle inequality, $(b)$ holds by (11), $(c)$ holds
by the data processing inequality, $(d)$ holds by (9) and the triangle
inequality, $(e)$ holds by (9), $(f)$ holds by Lemma 17 in Appendix B and
$r_{\mathcal{S}}\triangleq\sum_{i\in\mathcal{S}}r_{i}$ similar to the notation
of Lemma 17, $(g)$ holds by (10), $(h)$ holds because for any
$\mathcal{S}\subseteq\mathcal{A}$,
$\delta_{\mathcal{S}}(N)\leq\delta_{\mathcal{A}}(N)$. Next, we have

$\displaystyle{{{\sqrt{{\displaystyle\sum_{\begin{subarray}{c}{\mathcal{S}\subseteq\mathcal{A}},{\mathcal{S}\neq\emptyset}\end{subarray}}}2^{r_{\mathcal{S}}-NH(T_{\mathcal{S}}|Z)+N\delta_{\mathcal{A}}(N)}}}}}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\left({{{{2^{N(H(X|UZ)-\frac{\epsilon_{1}}{2})-NH(X|Z)}}}}}\right.$
$\displaystyle\phantom{--}+2^{N(H(U|Z)-\frac{\epsilon_{1}}{2})-NH(U|Z)}$
$\displaystyle\phantom{--}+2^{N(H(V|UZX)-\frac{\epsilon_{1}}{2})-NH(V|Z)}$
$\displaystyle\phantom{--}+2^{N(H(X|UZ)-\frac{\epsilon_{1}}{2})+N(H(U|Z)-\frac{\epsilon_{1}}{2})-NH(XU|Z)}$
$\displaystyle\phantom{--}+2^{N(H(U|Z)-\frac{\epsilon_{1}}{2})+N(H(V|UZX)-\frac{\epsilon_{1}}{2})-NH(UV|Z)}$
$\displaystyle\phantom{--}+2^{N(H(V|UZX)-\frac{\epsilon_{1}}{2})+N(H(X|UZ)-\frac{\epsilon_{1}}{2})-NH(VX|Z)}$
$\displaystyle\phantom{--}+2^{N(H(X|UZ)-\frac{\epsilon_{1}}{2})+N(H(U|Z)-\frac{\epsilon_{1}}{2})+N(H(V|UZX)-\frac{\epsilon_{1}}{2})}\
$ $\displaystyle\phantom{---}\left.\times
2^{-NH(XUV|Z)}\right)^{\frac{1}{2}}\times
2^{\frac{1}{2}N\delta_{\mathcal{A}}(N)}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}\left({{{{2^{-NI(X;U|Z)-N\frac{\epsilon_{1}}{2}}}}}}+2^{-N\frac{\epsilon_{1}}{2}}+2^{-NI(V;UX|Z)-N\frac{\epsilon_{1}}{2}}\right.$
$\displaystyle\phantom{--}+2^{-N{\epsilon_{1}}}+2^{-N{\epsilon_{1}}-NI(V;X|UZ)}+2^{-N\frac{3\epsilon_{1}}{2}}$
$\displaystyle\phantom{--}\left.+2^{-NI(V;U|ZX)-NI(X;U|Z)-N{\epsilon_{1}}}\right)^{\frac{1}{2}}\times
2^{\frac{1}{2}N\delta_{\mathcal{A}}(N)}$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{\leq}}\delta^{(0)}(N)-2/N\xrightarrow{N\to{+}\infty}0,$

where $(a)$ holds by $(\ref{eqnrX})$ and $(\ref{def1})$, $(b)$ holds by the
definition of mutual information and the chain rule for entropy, $(c)$ holds
by the definition of $\delta^{(0)}(N)$ and because
$\epsilon_{1}=2(\delta_{\mathcal{A}}(N)+\xi)$. ∎

We now show that in each encoding block, the random variables induced by the
coding scheme approximate well the target distribution.

######  Lemma 3.

For Block $i\in\llbracket 1,k\rrbracket$, we have

$\displaystyle\mathbb{V}(\widetilde{p}_{U_{i}^{1:N}V_{i}^{1:N}X_{i}^{1:N}Y_{i}^{1:N}Z_{i}^{1:N}},q_{U^{1:N}V^{1:N}X^{1:N}Y^{1:N}Z^{1:N}})\leq\\!\delta_{i}(N),$

where
$\delta_{i}(N)\triangleq\frac{3}{2}(\delta(N)+{\color[rgb]{0,0,0}\delta^{(0)}(N)})({3^{i}-1}{})+3^{i+1}\delta(N)$.

###### Proof.

We prove the result by induction. We first prove that the lemma holds for
$i=1$. Remark that

$\displaystyle\widetilde{p}_{Y^{1:N}_{1}|U_{1}^{1:N}V_{1}^{1:N}X_{1}^{1:N}}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\widetilde{p}_{Y^{1:N}_{1}|U_{1}^{1:N}V_{1}^{1:N}}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}q_{Y^{1:N}|U^{1:N}V^{1:N}}$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{=}}q_{Y^{1:N}|U^{1:N}V^{1:N}X^{1:N}},$
(12)

where (a) holds because $\widetilde{X}_{1}^{1:N}$ is independent from
$(\widetilde{U}^{1:N}_{1},\widetilde{V}^{1:N}_{1},\widetilde{Y}^{1:N}_{1})$,
(b) holds by the construction of $Y^{1:N}$ and $\widetilde{Y}_{1}^{1:N}$, (c)
holds because $X^{1:N}$ is independent from $(U^{1:N},V^{1:N},Y^{1:N})$. Next,
we have

$\displaystyle\mathbb{V}(\widetilde{p}_{U_{1}^{1:N}V_{1}^{1:N}X_{1}^{1:N}Y_{1}^{1:N}Z_{1}^{1:N}},q_{U^{1:N}V^{1:N}X^{1:N}Y^{1:N}Z^{1:N}})$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\mathbb{V}(\widetilde{p}_{Z_{1}^{1:N}|X_{1}^{1:N}Y_{1}^{1:N}}\widetilde{p}_{U_{1}^{1:N}V_{1}^{1:N}X_{1}^{1:N}Y_{1}^{1:N}},$
$\displaystyle\phantom{--}q_{Z^{1:N}|X^{1:N}Y^{1:N}}q_{U^{1:N}V^{1:N}X^{1:N}Y^{1:N}})$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}\mathbb{V}(\widetilde{p}_{U_{1}^{1:N}V_{1}^{1:N}X_{1}^{1:N}Y_{1}^{1:N}},q_{U^{1:N}V^{1:N}X^{1:N}Y^{1:N}})$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{=}}\mathbb{V}(\widetilde{p}_{U_{1}^{1:N}V_{1}^{1:N}X_{1}^{1:N}},q_{U^{1:N}V^{1:N}X^{1:N}})$
$\displaystyle\stackrel{{\scriptstyle(d)}}{{=}}\mathbb{V}(\widetilde{p}_{X_{1}^{1:N}}\widetilde{p}_{U_{1}^{1:N}V_{1}^{1:N}},q_{X^{1:N}}q_{U^{1:N}V^{1:N}})$
$\displaystyle\stackrel{{\scriptstyle(e)}}{{\leq}}\mathbb{V}(\widetilde{p}_{X_{1}^{1:N}}\widetilde{p}_{U_{1}^{1:N}V_{1}^{1:N}},q_{X^{1:N}}\widetilde{p}_{U_{1}^{1:N}V_{1}^{1:N}})$
$\displaystyle\phantom{--}+\mathbb{V}(q_{X^{1:N}}\widetilde{p}_{U_{1}^{1:N}V_{1}^{1:N}},q_{X^{1:N}}q_{U^{1:N}V^{1:N}})$
$\displaystyle\stackrel{{\scriptstyle(f)}}{{=}}\mathbb{V}(\widetilde{p}_{X_{1}^{1:N}},q_{X^{1:N}})+\mathbb{V}(\widetilde{p}_{U_{1}^{1:N}}\widetilde{p}_{V_{1}^{1:N}},q_{U^{1:N}}q_{V^{1:N}})$
$\displaystyle\stackrel{{\scriptstyle(g)}}{{\leq}}\mathbb{V}(\widetilde{p}_{X_{1}^{1:N}},q_{X^{1:N}})+\mathbb{V}(\widetilde{p}_{U_{1}^{1:N}}\widetilde{p}_{V_{1}^{1:N}},q_{U^{1:N}}\widetilde{p}_{V_{1}^{1:N}})$
$\displaystyle\phantom{--}+\mathbb{V}(q_{U^{1:N}}\widetilde{p}_{V_{1}^{1:N}},q_{U^{1:N}}q_{V^{1:N}})$
$\displaystyle=\mathbb{V}(\widetilde{p}_{X_{1}^{1:N}},q_{X^{1:N}})+\mathbb{V}(\widetilde{p}_{U_{1}^{1:N}},q_{U^{1:N}})+\mathbb{V}(\widetilde{p}_{V_{1}^{1:N}},q_{V^{1:N}})$
(13) $\displaystyle\stackrel{{\scriptstyle(h)}}{{\leq}}3\delta(N),$

where $(a)$ holds by the two Markov chains
$(U^{1:N},V^{1:N})-(X^{1:N},Y^{1:N})-Z^{1:N}$ and
$(\widetilde{U}_{1}^{1:N},\widetilde{V}_{1}^{1:N})-(\widetilde{X}^{1:N}_{1},\widetilde{Y}_{1}^{1:N})-\widetilde{Z}_{1}^{1:N}$,
$(b)$ holds because
$q_{Z^{1:N}|X^{1:N}Y^{1:N}}=\widetilde{p}_{Z_{1}^{1:N}\lvert
X_{1}^{1:N}Y_{1}^{1:N}}$, $(c)$ holds by (12), $(d)$ holds because $X^{1:N}$
is independent from $(U^{1:N},V^{1:N})$ and $\widetilde{X}_{1}^{1:N}$ is
independent from $(\widetilde{U}_{1}^{1:N},\widetilde{V}_{1}^{1:N})$, $(e)$
holds by the triangle inequality, $(f)$ holds because $U^{1:N}$ is independent
from $V^{1:N}$ and $\widetilde{U}_{1}^{1:N}$ is independent from
$\widetilde{V}_{1}^{1:N}$, $(g)$ holds by the triangle inequality, $(h)$ holds
by the source resolvability codes used at the transmitters because
$\frac{|E_{1}|}{N}>H(X)+\epsilon_{1}/2,\frac{|D_{1}|}{N}>H(U)+\epsilon_{1}/2,\frac{|F_{1}|}{N}>H(V)+\epsilon_{1}/2$.

Assume now that, for $i\in\llbracket 2,k-1\rrbracket$, the lemma holds. For
$i\in\llbracket 2,k\rrbracket$, consider $\bar{E}_{i},\bar{D}_{i},\bar{F}_{i}$
distributed according to
${p^{unif}_{\bar{E}}},{p^{unif}_{\bar{D}}},{p^{unif}_{\bar{F}}}$,
respectively. Let
$p_{\bar{X}_{i}^{1:N}},p_{\bar{U}_{i}^{1:N}},p_{\bar{V}_{i}^{1:N}}$ denote the
distribution of $\bar{X}_{i}^{1:N}\triangleq
e^{X}_{N}(\bar{E}_{i},E_{i}),\bar{U}_{i}^{1:N}\triangleq
e^{U}_{N}(\bar{D}_{i},D_{i}),\bar{V}_{i}^{1:N}\triangleq
e^{V}_{N}(\bar{F}_{i},F_{i})$, respectively. Then, for $i\in~{}\llbracket
1,k-1\rrbracket$, we have

$\displaystyle\mathbb{V}(\widetilde{p}_{U_{i+1}^{1:N}V_{i+1}^{1:N}X_{i+1}^{1:N}Y_{i+1}^{1:N}Z_{i+1}^{1:N}},q_{U^{1:N}V^{1:N}X^{1:N}Y^{1:N}Z^{1:N}})$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\mathbb{V}(\widetilde{p}_{X_{i+1}^{1:N}},q_{X^{1:N}})+\mathbb{V}(\widetilde{p}_{U_{i+1}^{1:N}},q_{U^{1:N}})+\mathbb{V}(\widetilde{p}_{V_{i+1}^{1:N}},q_{V^{1:N}})$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}\mathbb{V}(\widetilde{p}_{X_{i+1}^{1:N}},p_{\bar{X}_{i+1}^{1:N}})+\mathbb{V}(p_{\bar{X}_{i+1}^{1:N}},q_{X^{1:N}})$
$\displaystyle\phantom{--}+\mathbb{V}(\widetilde{p}_{U_{i+1}^{1:N}},p_{\bar{U}_{i+1}^{1:N}})+\mathbb{V}(p_{\bar{U}_{i+1}^{1:N}},q_{U^{1:N}})$
$\displaystyle\phantom{--}+\mathbb{V}(\widetilde{p}_{V_{i+1}^{1:N}},p_{\bar{V}_{i+1}^{1:N}})+\mathbb{V}(p_{\bar{V}_{i+1}^{1:N}},q_{V^{1:N}})$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{\leq}}3\delta(N)+\mathbb{V}(\widetilde{p}_{X_{i+1}^{1:N}},p_{\bar{X}_{i+1}^{1:N}})+\mathbb{V}(\widetilde{p}_{U_{i+1}^{1:N}},p_{\bar{U}_{i+1}^{1:N}})$
$\displaystyle\phantom{--}+\mathbb{V}(\widetilde{p}_{V_{i+1}^{1:N}},p_{\bar{V}_{i+1}^{1:N}})$
$\displaystyle\stackrel{{\scriptstyle(d)}}{{\leq}}3\delta(N)+\mathbb{V}(\widetilde{p}_{E_{i+1}},p^{unif}_{\bar{E}})+\mathbb{V}(\widetilde{p}_{D_{i+1}},p^{unif}_{\bar{D}})$
$\displaystyle\phantom{--}+\mathbb{V}(\widetilde{p}_{F_{i+1}},p^{unif}_{\bar{F}}),$
(14)

where $(a)$ holds similar to (V-A), $(b)$ holds by the triangle inequality,
$(c)$ holds by the source resolvability codes used at the transmitters because
$\frac{|\bar{E}_{i}|+|E_{i}|}{N}=H(X)+\epsilon_{1}/2,\frac{|\bar{F}_{i}|+|F_{i}|}{N}=H(V)+\epsilon_{1}/2,\frac{|\bar{D}_{i}|+|D_{i}|}{N}=H(U)+\epsilon_{1}/2$,
$(d)$ holds by the data processing inequality. Next, we have

$\displaystyle\max\left(\\!\mathbb{V}(\widetilde{p}_{E_{i+1}},p^{unif}_{\bar{E}}),\mathbb{V}(\widetilde{p}_{D_{i+1}},p^{unif}_{\bar{D}}),\mathbb{V}(\widetilde{p}_{F_{i+1}},p^{unif}_{\bar{F}})\\!\right)$
$\displaystyle\leq\mathbb{V}(\widetilde{p}_{E_{i+1}D_{i+1}F_{i+1}},p^{unif}_{\bar{E}}p^{unif}_{\bar{D}}p^{unif}_{\bar{F}})$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\mathbb{V}(\widetilde{p}_{E_{i+1}D_{i+1}F_{i+1}},q_{G_{X}({X}^{1:N})G_{U}({U}^{1:N})G_{V}({V}^{1:N})})$
$\displaystyle\phantom{--}+\mathbb{V}(q_{G_{X}({X}^{1:N})G_{U}({U}^{1:N})G_{V}({V}^{1:N})},p^{unif}_{\bar{E}}p^{unif}_{\bar{D}}p^{unif}_{\bar{F}})$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}\mathbb{V}(\widetilde{p}_{G_{X}({X}_{i}^{1:N})G_{U}({U}_{i}^{1:N})G_{V}({V}_{i}^{1:N})},$
$\displaystyle\phantom{----}q_{G_{X}({X}^{1:N})G_{U}({U}^{1:N})G_{V}({V}^{1:N})})$
$\displaystyle\phantom{--}+\mathbb{V}(q_{G_{X}({X}^{1:N})G_{U}({U}^{1:N})G_{V}({V}_{i}^{1:N})},p^{unif}_{\bar{E}}p^{unif}_{\bar{D}}p^{unif}_{\bar{F}})$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{\leq}}\mathbb{V}(\widetilde{p}_{{X}_{i}^{1:N}{U}_{i}^{1:N}{V}_{i}^{1:N}},q_{{X}^{1:N}{U}^{1:N}{V}^{1:N}})+{\color[rgb]{0,0,0}\delta^{(0)}(N)}$
$\displaystyle\stackrel{{\scriptstyle(d)}}{{\leq}}\delta_{i}(N)+{\color[rgb]{0,0,0}\delta^{(0)}(N)},$
(15)

where $(a)$ holds by the triangle inequality, $(b)$ holds because
$\widetilde{E}_{i+1}\triangleq
G_{X}(\widetilde{X}_{i}^{1:N}),\widetilde{D}_{i+1}\triangleq
G_{U}(\widetilde{U}_{i}^{1:N}),\widetilde{F}_{i+1}\triangleq
G_{V}(\widetilde{V}_{i}^{1:N})$ by Line $5$ of Algorithm 1 and Algorithm 2 ,
$(c)$ holds by the data processing inequality and Lemma 2, $(d)$ holds by the
induction hypothesis. By combining (14) and (15), we have

$\displaystyle\mathbb{V}(\widetilde{p}_{U_{i+1}^{1:N}V_{i+1}^{1:N}X_{i+1}^{1:N}Y_{i+1}^{1:N}Z_{i+1}^{1:N}},q_{U^{1:N}V^{1:N}X^{1:N}Y^{1:N}Z^{1:N}})$
$\displaystyle\leq
3(\delta(N)+\delta_{i}(N)+{\color[rgb]{0,0,0}\delta^{(0)}(N)})$
$\displaystyle={\color[rgb]{0,0,0}\delta_{i+1}(N)}.\hfill$

∎

The next lemma shows that the recycled randomness in Block $i\in\llbracket
2,k\rrbracket$ is almost independent of the channel output in Block $i-1$.

######  Lemma 4.

For $i\in\llbracket 2,k\rrbracket$, we have

$\displaystyle\mathbb{V}(\widetilde{p}_{{Z}_{i-1}^{1:N}E_{i}D_{i}F_{i}},\widetilde{p}_{{Z}_{i-1}^{1:N}}\widetilde{p}_{E_{i}D_{i}F_{i}})\leq\delta^{(1)}_{i}(N),$

where $\delta^{(1)}_{i}(N)\triangleq
4\delta_{i-1}(N)+2{\color[rgb]{0,0,0}\delta^{(0)}(N)}$.

###### Proof.

We have

$\displaystyle\mathbb{V}(\widetilde{p}_{{Z}_{i-1}^{1:N}E_{i}D_{i}F_{i}},\widetilde{p}_{{Z}_{i-1}^{1:N}}\widetilde{p}_{E_{i}D_{i}F_{i}})$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\mathbb{V}(\widetilde{p}_{Z_{i-1}^{1:N}E_{i}D_{i}F_{i}},\widetilde{p}_{Z_{i-1}^{1:N}}p^{unif}_{\bar{E}}p^{unif}_{\bar{D}}p^{unif}_{\bar{F}})$
$\displaystyle\phantom{--}+\mathbb{V}(\widetilde{p}_{Z_{i-1}^{1:N}}p^{unif}_{\bar{E}}p^{unif}_{\bar{D}}p^{unif}_{\bar{F}},\widetilde{p}_{{Z}_{i-1}^{1:N}}\widetilde{p}_{E_{i}D_{i}F_{i}})$
$\displaystyle\leq
2\mathbb{V}(\widetilde{p}_{Z_{i-1}^{1:N}E_{i}D_{i}F_{i}},\widetilde{p}_{Z_{i-1}^{1:N}}p^{unif}_{\bar{E}}p^{unif}_{\bar{D}}p^{unif}_{\bar{F}})$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}2\left(\mathbb{V}(\widetilde{p}_{E_{i}D_{i}F_{i}Z^{1:N}_{i-1}},q_{EDFZ^{1:N}})\right.$
$\displaystyle\phantom{--}\left.+\mathbb{V}(q_{EDFZ^{1:N}},p^{unif}_{\bar{E}}p^{unif}_{\bar{D}}p^{unif}_{\bar{F}}q_{Z^{1:N}}\right.)$
$\displaystyle\phantom{--}\left.+\mathbb{V}(p^{unif}_{\bar{E}}p^{unif}_{\bar{D}}p^{unif}_{\bar{F}}q_{Z^{1:N}},p^{unif}_{\bar{E}}p^{unif}_{\bar{D}}p^{unif}_{\bar{F}}\widetilde{p}_{Z_{i-1}^{1:N}})\right)$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{\leq}}2\left(\mathbb{V}(\widetilde{p}_{{X}_{i-1}^{1:N}{U}_{i-1}^{1:N}{V}_{i-1}^{1:N}Z_{i-1}^{1:N}},q_{{X}^{1:N}{U}^{1:N}{V}^{1:N}Z^{1:N}})\right.$
$\displaystyle\phantom{--}\left.+\mathbb{V}(q_{EDFZ^{1:N}},p^{unif}_{\bar{E}}p^{unif}_{\bar{D}}p^{unif}_{\bar{F}}q_{Z^{1:N}})\right.$
$\displaystyle\phantom{--}\left.+\mathbb{V}(q_{Z^{1:N}},\widetilde{p}_{Z_{i-1}^{1:N}})\right)$
$\displaystyle\stackrel{{\scriptstyle(d)}}{{\leq}}2(2\mathbb{V}(\widetilde{p}_{{X}_{i-1}^{1:N}{U}_{i-1}^{1:N}{V}_{i-1}^{1:N}Z_{i-1}^{1:N}},q_{{X}^{1:N}{U}^{1:N}{V}^{1:N}Z^{1:N}})\\!+\\!{\color[rgb]{0,0,0}\delta^{(0)}(N)})$
$\displaystyle\stackrel{{\scriptstyle(e)}}{{\leq}}4\delta_{i-1}(N)+2{\color[rgb]{0,0,0}\delta^{(0)}(N)},$

where $(a)$ and $(b)$ hold by the triangle inequality, $(c)$ holds by the data
processing inequality using (11) and $\widetilde{E}_{i}\triangleq
G_{X}(\widetilde{X}_{i-1}^{1:N}),\widetilde{D}_{i}\triangleq
G_{U}(\widetilde{U}_{i-1}^{1:N}),\widetilde{F}_{i}\triangleq
G_{V}(\widetilde{V}_{i-1}^{1:N})$ from Line $5$ of Algorithm 1 and Algorithm
2, $(d)$ holds by (11) and Lemma 2, $(e)$ holds by Lemma 3. ∎

The next lemma shows that the recycled randomness in Block $i\in\llbracket
2,k\rrbracket$ is almost independent of the channel outputs in Blocks $1$ to
$i-1$ considered jointly.

######  Lemma 5.

For $i\in\llbracket 2,k\rrbracket$, we have

$\mathbb{V}\left(\widetilde{p}_{Z_{1:i-1}^{1:N}D_{i}E_{i}F_{i}},\widetilde{p}_{Z_{1:i-1}^{1:N}}\widetilde{p}_{D_{i}E_{i}F_{i}}\right)\leq\delta_{i}^{(2)}(N),$

where
$\delta_{i}^{(2)}(N)\triangleq(2^{i-1}-1)(4\delta_{i-1}(N)+2{\color[rgb]{0,0,0}\delta^{(0)}(N)})$.

###### Proof.

We prove the result by induction. The lemma is true for $i=2$ by Lemma 4.
Assume now that the lemma holds for $i\in\llbracket 2,k-1\rrbracket$. Then,
for $i\in\llbracket 3,k\rrbracket$, we have

$\displaystyle\mathbb{V}\left(\widetilde{p}_{Z_{1:i-2}^{1:N}D_{i-1}E_{i-1}F_{i-1}},\widetilde{p}_{Z_{1:i-2}^{1:N}}\widetilde{p}_{D_{i-1}E_{i-1}F_{i-1}}\right)\leq\delta_{i-1}^{(2)}(N).$

We have

$\displaystyle\mathbb{V}\left(\widetilde{p}_{Z_{1:i-1}^{1:N}D_{i}E_{i}F_{i}},\widetilde{p}_{Z_{1:i-1}^{1:N}}\widetilde{p}_{D_{i}E_{i}F_{i}}\right)$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\mathbb{V}\left(\widetilde{p}_{Z_{1:i-1}^{1:N}D_{i}E_{i}F_{i}},\widetilde{p}_{Z_{1:i-2}^{1:N}}\widetilde{p}_{Z_{i-1}^{1:N}D_{i}E_{i}F_{i}}\right)$
$\displaystyle\phantom{--}+\mathbb{V}\left(\widetilde{p}_{Z_{1:i-2}^{1:N}}\widetilde{p}_{Z_{i-1}^{1:N}D_{i}E_{i}F_{i}},\widetilde{p}_{Z_{1:i-2}^{1:N}}\widetilde{p}_{Z_{i-1}^{1:N}}\widetilde{p}_{D_{i}E_{i}F_{i}}\right)$
$\displaystyle\phantom{--}+\mathbb{V}\left(\widetilde{p}_{Z_{1:i-2}^{1:N}}\widetilde{p}_{Z_{i-1}^{1:N}}\widetilde{p}_{D_{i}E_{i}F_{i}},\widetilde{p}_{Z_{1:i-1}^{1:N}}\widetilde{p}_{D_{i}E_{i}F_{i}}\right)$
$\displaystyle=\mathbb{V}\left(\widetilde{p}_{Z_{1:i-1}^{1:N}D_{i}E_{i}F_{i}},\widetilde{p}_{Z_{1:i-2}^{1:N}}\widetilde{p}_{Z_{i-1}^{1:N}D_{i}E_{i}F_{i}}\right)$
$\displaystyle\phantom{--}+\mathbb{V}\left(\widetilde{p}_{Z_{i-1}^{1:N}D_{i}E_{i}F_{i}},\widetilde{p}_{Z_{i-1}^{1:N}}\widetilde{p}_{D_{i}E_{i}F_{i}}\right)$
$\displaystyle\phantom{--}+\mathbb{V}\left(\widetilde{p}_{Z_{1:i-2}^{1:N}}\widetilde{p}_{Z_{i-1}^{1:N}},\widetilde{p}_{Z_{1:i-1}^{1:N}}\right)$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}\mathbb{V}\left(\widetilde{p}_{Z_{1:i-1}^{1:N}D_{i}E_{i}F_{i}},\widetilde{p}_{Z_{1:i-2}^{1:N}}\widetilde{p}_{Z_{i-1}^{1:N}D_{i}E_{i}F_{i}}\right)$
$\displaystyle\phantom{--}+\mathbb{V}\left(\widetilde{p}_{Z_{1:i-2}^{1:N}}\widetilde{p}_{Z_{i-1}^{1:N}},\widetilde{p}_{Z_{1:i-1}^{1:N}}\right)+\delta^{(1)}_{i}(N)$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{\leq}}2\mathbb{V}\left(\widetilde{p}_{Z_{1:i-1}^{1:N}D_{i-1:i}E_{i-1:i}F_{i-1:i}},\right.$
$\displaystyle\phantom{----}\left.\widetilde{p}_{Z_{1:i-2}^{1:N}}\widetilde{p}_{Z_{i-1}^{1:N}D_{i-1:i}E_{i-1:i}F_{i-1:i}}\right)+\delta^{(1)}_{i}(N)$
$\displaystyle\stackrel{{\scriptstyle(d)}}{{=}}2\mathbb{V}\left(\widetilde{p}_{Z_{1:i-2}^{1:N}D_{i-1}E_{i-1}F_{i-1}}\widetilde{p}_{Z_{i-1}^{1:N}D_{i}E_{i}F_{i}|D_{i-1}E_{i-1}F_{i-1}},\right.$
$\displaystyle\phantom{----}\left.\widetilde{p}_{Z_{1:i-2}^{1:N}}\widetilde{p}_{Z_{i-1}^{1:N}D_{i-1:i}E_{i-1:i}F_{i-1:i}}\right)+\delta^{(1)}_{i}(N)$
$\displaystyle=2\mathbb{V}\left(\widetilde{p}_{Z_{1:i-2}^{1:N}D_{i-1}E_{i-1}F_{i-1}},\widetilde{p}_{Z_{1:i-2}^{1:N}}\widetilde{p}_{D_{i-1}E_{i-1}F_{i-1}}\right)$
$\displaystyle\phantom{--}+\delta^{(1)}_{i}(N)$
$\displaystyle\stackrel{{\scriptstyle(e)}}{{\leq}}\delta^{(1)}_{i}(N)+2\delta_{i-1}^{(2)}(N)$
$\displaystyle\leq\delta_{i}^{(2)}(N),$

where $(a)$ holds by the triangle inequality, $(b)$ holds by Lemma 4, $(c)$
follows from the data processing inequality, $(d)$ holds by the Markov chain
$(\widetilde{D}_{i},\widetilde{E}_{i},\widetilde{F}_{i},\widetilde{Z}_{i-1}^{1:N})-(\widetilde{D}_{i-1},\widetilde{E}_{i-1},\widetilde{F}_{i-1})-\widetilde{Z}_{1:i-2}^{1:N}$,
$(e)$ holds by the induction hypothesis. ∎

The next lemma shows that the channel outputs of all the blocks are
asymptotically independent.

######  Lemma 6.

We have

$\mathbb{V}\left(\widetilde{p}_{Z_{1:k}^{1:N}},\prod_{i=1}^{k}\widetilde{p}_{Z_{i}^{1:N}}\right)\leq(k-1)\delta_{k}^{(2)}(N),$

where $\delta_{k}^{(2)}(N)$ is defined in Lemma 5.

###### Proof.

We have

$\displaystyle\mathbb{V}\left(\widetilde{p}_{Z_{1:k}^{1:N}},\prod_{i=1}^{k}\widetilde{p}_{Z_{i}^{1:N}}\right)$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\sum_{i=2}^{k}\mathbb{V}\left(\widetilde{p}_{Z_{1:i}^{1:N}}\prod_{j=i+1}^{k}\widetilde{p}_{Z_{j}^{1:N}},\widetilde{p}_{Z_{1:i-1}^{1:N}}\prod_{j=i}^{k}\widetilde{p}_{Z_{j}^{1:N}}\right)$
$\displaystyle=\sum_{i=2}^{k}\mathbb{V}\left(\widetilde{p}_{Z_{1:i}^{1:N}},\widetilde{p}_{Z_{1:i-1}^{1:N}}\widetilde{p}_{Z_{i}^{1:N}}\right)$
$\displaystyle\leq\sum_{i=2}^{k}\mathbb{V}\left(\widetilde{p}_{Z_{1:i}^{1:N}D_{i}E_{i}F_{i}},\widetilde{p}_{Z_{i}^{1:N}D_{i}E_{i}F_{i}}\widetilde{p}_{Z_{1:i-1}^{1:N}}\right)$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}\sum_{i=2}^{k}\mathbb{V}\left(\widetilde{p}_{Z_{1:i-1}^{1:N}|D_{i}E_{i}F_{i}}\widetilde{p}_{Z_{i}^{1:N}D_{i}E_{i}F_{i}},\widetilde{p}_{Z_{i}^{1:N}D_{i}E_{i}F_{i}}\widetilde{p}_{Z_{1:i-1}^{1:N}}\right)$
$\displaystyle=\sum_{i=2}^{k}\mathbb{V}\left(\widetilde{p}_{Z_{1:i-1}^{1:N}D_{i}E_{i}F_{i}},\widetilde{p}_{Z_{1:i-1}^{1:N}}\widetilde{p}_{D_{i}E_{i}F_{i}}\right)$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{\leq}}\sum_{i=2}^{k}\delta_{i}^{(2)}(N)$
$\displaystyle\leq(k-1)\max_{j\in\llbracket
2,k\rrbracket}\delta_{j}^{(2)}(N),$

where $(a)$ holds by the triangle inequality, $(b)$ holds by the Markov chain
$\widetilde{Z}_{i}^{1:N}-(\widetilde{D}_{i},\widetilde{E}_{i},\widetilde{F}_{i})-\widetilde{Z}_{1:i-1}^{1:N}$,
$(c)$ holds by Lemma 5. ∎

We now show that the target output distribution is well approximated jointly
over all blocks.

######  Lemma 7.

For Block $i\in\llbracket 1,k\rrbracket$, we have

$\mathbb{V}\left(\widetilde{p}_{Z_{1:k}^{1:N}},q_{Z^{1:kN}}\right)\leq(k-1)\delta_{k}^{(2)}(N)+k\delta_{k}(N),$

where $\delta_{k}^{(2)}(N)$ is defined in Lemma 5 and $\delta_{k}(N)$ is
defined in Lemma 3.

###### Proof.

We have

$\displaystyle\mathbb{V}(\widetilde{p}_{Z_{1:k}^{1:N}},q_{Z^{1:kN}})$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}(k-1)\delta_{k}^{(2)}(N)+\mathbb{V}(\prod_{i=1}^{k}\widetilde{p}_{Z_{i}^{1:N}},q_{Z^{1:kN}})$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}(k-1)\delta_{k}^{(2)}(N)+\mathbb{V}(\widetilde{p}_{Z_{1}^{1:N}}\prod_{i=2}^{k}\widetilde{p}_{Z_{i}^{1:N}},q_{Z^{1:N}}\prod_{i=2}^{k}\widetilde{p}_{Z_{i}^{1:N}})$
$\displaystyle\phantom{--}+\mathbb{V}(q_{Z^{1:N}}\prod_{i=2}^{k}\widetilde{p}_{Z_{i}^{1:N}},q_{Z^{1:kN}})$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{\leq}}(k-1)\delta_{k}^{(2)}(N)+\delta_{1}(N)+\mathbb{V}(\prod_{i=2}^{k}\widetilde{p}_{Z_{i}^{1:N}},q_{Z^{1:(k-1)N}})$
$\displaystyle\stackrel{{\scriptstyle(d)}}{{\leq}}(k-1)\delta_{k}^{(2)}(N)+\sum_{i=1}^{k}\delta_{i}(N)$
$\displaystyle\leq(k-1)\delta_{k}^{(2)}(N)+k\max_{j\in\llbracket
1,k\rrbracket}\delta_{j}(N),$

where $(a)$ holds by the triangle inequality and Lemma 6, $(b)$ holds by the
triangle inequality, $(c)$ holds by Lemma 3, $(d)$ holds by induction. ∎

Finally, the next lemma shows that the encoding scheme of Section IV-B
achieves the desired rate-tuple.

######  Lemma 8.

Let $\epsilon_{0}>0$. For $k$ large enough and $\xi>0$, we have

$\displaystyle\displaystyle\lim_{{{N\rightarrow+\infty}}}R_{1}$
$\displaystyle=I(X;ZU)+\epsilon_{0}+2\xi,$
$\displaystyle\displaystyle\lim_{{{N\rightarrow+\infty}}}R_{U}$
$\displaystyle=I(U;Z)+\epsilon_{0}+2\xi,$
$\displaystyle\displaystyle\lim_{{{N\rightarrow+\infty}}}R_{V}$
$\displaystyle=I(V;ZUX)+\epsilon_{0}+2\xi.$

###### Proof.

Let $k$ be such that $\frac{1}{k}\max(H(X),H(U),H(V))<\epsilon_{0}.$ Then, by
the definition of $\epsilon_{1}$, we have

$\displaystyle R_{1}$ $\displaystyle=\frac{\sum_{i=1}^{k}|E_{i}|}{kN}$
$\displaystyle=\frac{N(H(X)+\epsilon_{1})+(k-1)N(I(X;ZU)+\epsilon_{1})}{kN}$
$\displaystyle\leq\frac{H(X)}{k}+I(X;ZU)+\epsilon_{1}$
$\displaystyle\leq\epsilon_{0}+I(X;ZU)+\epsilon_{1}$
$\displaystyle\xrightarrow{N\to+\infty}I(X;ZU)+\epsilon_{0}+2\xi,$
$\displaystyle R_{U}$ $\displaystyle=\frac{\sum_{i=1}^{k}|D_{i}|}{kN}$
$\displaystyle=\frac{N(H(U)+\epsilon_{1}+(k-1)N(I(U;Z)+\epsilon_{1})}{kN}$
$\displaystyle\leq\frac{H(U)}{k}+I(U;Z)+\epsilon_{1}$
$\displaystyle\leq\epsilon_{0}+I(U;Z)+\epsilon_{1}$
$\displaystyle\xrightarrow{N\to+\infty}I(U;Z)+\epsilon_{0}+2\xi,$
$\displaystyle R_{V}$ $\displaystyle=\frac{\sum_{i=1}^{k}|F_{i}|}{kN}$
$\displaystyle=\frac{N(H(V)+\epsilon_{1})+(k-1)N(I(V;ZUX)+\epsilon_{1})}{kN}$
$\displaystyle\leq\frac{H(V)}{k}+I(V;ZUX)+\epsilon_{1}$
$\displaystyle\leq\epsilon_{0}+I(V;ZUX)+\epsilon_{1}$
$\displaystyle\xrightarrow{N\to+\infty}I(V;ZUX)+\epsilon_{0}+2\xi.$

∎

###  V-B Coding scheme analysis for Case 2

For Case $2$, $U=\emptyset$ and $V=Y$, so that by Lemma 8, the achieved rate
pair is such that

$\displaystyle\displaystyle\lim_{{{N\rightarrow+\infty}}}R_{1}$
$\displaystyle=I(X;Z)+\epsilon_{0}+2\xi,$
$\displaystyle\displaystyle\lim_{{{N\rightarrow+\infty}}}R_{2}$
$\displaystyle=\lim_{{{N\rightarrow+\infty}}}(R_{V}+R_{U})$
$\displaystyle=I(Y;ZX)+\epsilon_{0}+2\xi$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}I(Y;Z|X)+\epsilon_{0}+2\xi$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}I(Y;Z)+\epsilon_{0}+2\xi,$

where $(a)$ holds by independence between $X$ and $Y$, and $(b)$ holds because
$I(XY;Z)=I(X;Z)+I(Y;Z)$ in Case $2$.

##  VI Extension to more than two transmitters

Consider a discrete memoryless multiple access channel
$(\mathcal{X}_{\mathcal{L}},q_{Z|X_{\mathcal{L}}},\mathcal{Z})$, where
$\mathcal{X}_{l}=\\{0,1\\}$, $l\in\mathcal{L}\triangleq\llbracket
1,L\rrbracket$, $\mathcal{Z}$ is a finite alphabet, and
$X_{\mathcal{L}}\triangleq(X_{l})_{l\in\mathcal{L}}$. The definitions in
Section II-B immediately extend to this multiple access channel with $L$
transmitters and we have the following counterpart of Theorem 1.

######  Theorem 4.

We have $\mathcal{R}_{q_{Z}}=\mathcal{R}^{\prime}_{q_{Z}}$ with

$\displaystyle\mathcal{R}^{\prime}_{q_{Z}}\triangleq{\bigcup_{p_{T},(q_{X_{l}|T})_{l\in\mathcal{L}}}}\\!\\!\\!\\!\\!\\!\\!\\!\\!\\{(R_{l})_{l\in\mathcal{L}}:I(X_{\mathcal{S}};Z|T)$
$\displaystyle\leq R_{\mathcal{S}},\forall\mathcal{S}\subseteq\mathcal{L}\\},$

where $p_{T}$ is defined over $\mathcal{T}\triangleq\llbracket
1,|\mathcal{Z}|+2^{L}-1\rrbracket$ and $(q_{X_{l}|T})_{l\in\mathcal{L}}$ are
such that, for any $t\in\mathcal{T}$ and $z\in\mathcal{Z}$,

$\displaystyle
q_{Z}(z)=\sum_{{x_{\mathcal{L}}\in\mathcal{X}_{\mathcal{L}}}}q_{Z|X_{\mathcal{L}}}(z|x_{\mathcal{L}})\prod_{l\in\mathcal{L}}q_{X_{l}|T}(x_{l}|t).$

###### Proof.

The converse is an immediate extension of the converse of Theorem 1 from [7].
The achievability follows from Theorem 5. ∎

######  Theorem 5.

The coding scheme presented in Section VI-A, which solely relies on source
resolvability codes, used as black boxes, and two-universal hash functions,
achieves the entire multiple access channel resolvability region
$\mathcal{R}_{q_{Z}}$ of Theorem 4 for any discrete memoryless multiple access
channel with binary input alphabets.

###  VI-A Achievability Scheme

In the following, we use the notation
$X_{\mathcal{S}}\triangleq(X_{l})_{l\in\mathcal{S}}$ for
$\mathcal{S}\subseteq\mathcal{L}$, and $X_{1:l}\triangleq X_{\llbracket
1,l\rrbracket}$ for $l\in\mathcal{L}$. Let
$p_{X_{\mathcal{L}}}\triangleq\prod_{l\in\mathcal{L}}p_{X_{l}}$. We will show
the achievability of the region

$\displaystyle\mathcal{R}\left(p_{X_{\mathcal{L}}}\right)\triangleq\\{(R_{l})_{l\in\mathcal{L}}:I(X_{\mathcal{S}};Z)$
$\displaystyle\leq R_{\mathcal{S}},\forall\mathcal{S}\subseteq\mathcal{L}\\},$

which reduces to showing the achievability of the rate-tuple
$(I(X_{l};Z|X_{1:l-1}))_{l\in\mathcal{L}}$. Indeed, the set function
$\mathcal{S}\mapsto-I(X_{\mathcal{S}};Z)$ is submodular, e.g., [20], and the
region $\mathcal{R}\left(p_{X_{\mathcal{L}}}\right)$ thus forms a
contrapolymatroid [19] whose dominant face is the convex hull of its extreme
points given by $\\{(I(X_{\sigma(l)};Z|X_{\\{\sigma(i):i\in\llbracket
1,l-1\rrbracket\\}}))_{l\in\mathcal{L}}:\sigma\in\mathfrak{S}(L)\\}$, where
$\mathfrak{S}(L)$ is the symmetric group over $\mathcal{L}$. By time-sharing
and symmetry of the extreme points, the achievability of the dominant face
reduces to showing the achievability of one extreme point, which without loss
of generality can be chosen as $(I(X_{l};Z|X_{1:l-1}))_{l\in\mathcal{L}}$.

The encoding scheme to achieve $(I(X_{l};Z|X_{1:l-1}))_{l\in\mathcal{L}}$
operates over $k\in\mathbb{N}$ blocks of length $N$. In this section, we use
the double subscripts notation ${X_{l,i}}$, where the first subscript
corresponds to Transmitter $l\in\mathcal{L}$ and the second subscript
corresponds to Block $i\in\llbracket 1,k\rrbracket$. The encoding at
Transmitter $l\in\mathcal{L}$ is described in Algorithm 3 and uses

  * •

A hash function
$G_{X_{l}}:\\{0,1\\}^{N}\longrightarrow\\{0,1\\}^{r_{{X_{l}}}}$ chosen
uniformly at random in a family of two-universal hash functions, where the
output length of the hash function $G_{X_{l}}$ is defined as follows

$\displaystyle r_{X_{l}}\triangleq N(H(X_{l}|ZX_{1:l-1})-{\epsilon_{2}}/{2}).$
(16)

  * •

A source resolvability code for the discrete memoryless source
$(\mathcal{X}_{l},q_{X_{l}})$ with encoder function $e_{N}^{X_{{l}}}$ and rate
$H(X_{l})+\frac{\epsilon_{2}}{2}$, where $\epsilon_{2}\triangleq
2(\delta^{*}_{\mathcal{L}}(N)+\xi)$,
$\delta^{*}_{\mathcal{L}}(N)\triangleq\log(|\mathcal{X}_{\mathcal{L}}|+3)\sqrt{\frac{2}{N}(L+\log
N)}$, $\xi>0$, such that the distribution of the encoder output
$\widetilde{p}_{X_{l}^{1:N}}$ satisfies
$\mathbb{V}(\widetilde{p}_{X_{l}^{1:N}},q_{X_{l}^{1:N}})\leq\delta(N)$, where
$\delta(N)$ is such that $\lim_{N\to+\infty}\delta(N)=0$.

In Algorithm 3 and for any $l\in\mathcal{L}$, the hash function output
${\widetilde{E}_{{l},i}}$, $i\in\llbracket 2,k\rrbracket$, with length
$r_{X_{l}}$ corresponds to recycled randomness from Block $i-1$.

Algorithm 3 Encoding algorithm at Transmitter $l\in\mathcal{L}$

0: A vector $E_{l,1}$ of $N(H(X_{l})+\epsilon_{2})$ uniformly distributed
bits, and for $i\in\llbracket 2,k\rrbracket$, a vector $E_{l,{i}}$ of
$N(I(X_{l};ZX_{1:l-1})+\epsilon_{2})$ uniformly distributed bits.

1: for Block $i=1$ to $k$ do

2: if $i=1$ then

3: Define ${\widetilde{X}_{l,1}}^{1:N}\triangleq e^{X_{l}}_{N}(E_{l,1})$

4: else if $i>1$ then

5: Define $\widetilde{E}_{l,{i}}\triangleq
G_{X_{l}}(\widetilde{X}_{l,{i-1}}^{1:N})$

6: Define $\widetilde{X}_{l,i}^{1:N}\triangleq
e^{X_{l}}_{N}(\widetilde{E}_{l,{i}}\lVert{E_{l,i}})$

7: end if

8: Send ${\widetilde{X}_{l,i}}^{1:N}$ over the channel

9: end for

###  VI-B Achievability Scheme Analysis

For convenience, define, for any $l\in\mathcal{L}$,
$\widetilde{E}_{l,1}\triangleq\emptyset$. Let
$\widetilde{p}_{E_{1:L,i}X^{1:N}_{1:L,i}Z^{1:N}_{i}}$ denote the joint
probability distribution of the random variables
$\widetilde{E}_{l,i},\widetilde{X}^{1:N}_{l,i}$, and
$\widetilde{Z}^{1:N}_{i}$, $l\in\mathcal{L}$, created in Block $i\in\llbracket
1,k\rrbracket$ of the coding scheme of Section VI-A.

We prove in the following lemma that in Block $i\in\llbracket 2,k\rrbracket$,
if the inputs $\widetilde{X}_{1:L,i-1}^{1:N}$ of the hash functions
$(G_{X_{l}})_{l\in\mathcal{L}}$ are replaced by $X_{1:L}^{1:N}$ distributed
according to $q_{X^{1:N}_{1:L}}\triangleq\prod_{i=1}^{N}q_{X_{1:L}}$, then the
outputs of these hash functions are almost jointly uniformly distributed.
Define

$\displaystyle
G_{X_{1:L}}(X^{1:N}_{1:L})\triangleq\left(G_{X_{l}}(X^{1:N}_{l})\right)_{l\in\mathcal{L}}.$

######  Lemma 9.

Let $p^{unif}_{\bar{E}_{1:L}}$ denote the uniform distribution over
$\\{0,1\\}^{\sum_{l\in\mathcal{L}}r_{X_{l}}}$. Then, we have

$\displaystyle\mathbb{V}\left(q_{G_{X_{1:L}}(X_{1:L}^{1:N})Z^{1:N}},p^{unif}_{\bar{E}_{1:L}}q_{Z^{1:N}}\right)\leq\delta^{*(0)}(N),$

where $\delta^{*(0)}(N)\triangleq 2/N+{2^{\frac{L}{2}}2^{-\frac{N\xi}{2}}}$.

###### Proof.

Using Lemma 16 in Appendix B, with the substitutions
$\mathcal{A}\leftarrow\mathcal{L},T_{\mathcal{A}}^{1:N}\leftarrow
X_{\mathcal{L}}^{1:N}$, applied to the product distribution
$q_{X_{\mathcal{L}}^{1:N}Z^{1:N}}$, there exists a subnormalized non-negative
function $w_{{X_{\mathcal{L}}^{1:N}}Z^{1:N}}$ such that for any
$\mathcal{S}\subseteq\mathcal{L}$

$\displaystyle\mathbb{V}({w}_{X_{1:L}^{1:N}Z^{1:N}},q_{X_{1:L}^{1:N}Z^{1:N}})$
$\displaystyle\leq 1/N,$ (17) $\displaystyle
H_{\infty}({w}_{{{X}_{\mathcal{S}}^{1:N}}Z^{1:N}}|q_{Z^{1:N}})$
$\displaystyle\geq NH({{X}_{\mathcal{S}}}|Z)-N\delta^{*}_{\mathcal{S}}(N),$
(18)

where the min-entropy
$H_{\infty}({w}_{{{X}_{\mathcal{S}}^{1:N}}Z^{1:N}}|q_{Z^{1:N}})$ is defined in
Lemma 16 in Appendix B, and
$\delta^{*}_{\mathcal{S}}(N)\triangleq\log(\lvert\mathcal{X}_{\mathcal{S}}\rvert+3)\sqrt{\frac{2}{N}(L+\log
N)}$. Let $q_{E_{1:L}}$ define the distribution of

$\displaystyle E_{1:L}\triangleq G_{X_{1:L}}(X_{1:L}^{1:N}),$ (19)

where $X_{1:L}^{1:N}$ is distributed according to $q_{X_{1:L}^{1:N}}$. We have

$\displaystyle\mathbb{V}(q_{E_{1:L}Z^{1:N}},p^{unif}_{\bar{E}_{1:L}}q_{Z^{1:N}})$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\mathbb{V}(q_{E_{1:L}Z^{1:N}},w_{E_{1:L}Z^{1:N}})+\mathbb{V}(w_{E_{1:L}Z^{1:N}},p^{unif}_{\bar{E}_{1:L}}q_{Z^{1:N}})$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}\mathbb{V}(q_{X_{1:L}^{1:N}Z^{1:N}},{w}_{X_{1:L}^{1:N}Z^{1:N}})+\mathbb{V}(w_{E_{1:L}Z^{1:N}},p^{unif}_{\bar{E}_{1:L}}q_{Z^{1:N}})$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{\leq}}1/N+\mathbb{V}(w_{E_{1:L}Z^{1:N}},p^{unif}_{\bar{E}_{1:L}}w_{Z^{1:N}})$
$\displaystyle\phantom{--}+\mathbb{V}(p^{unif}_{\bar{E}_{1:L}}w_{Z^{1:N}},p^{unif}_{\bar{E}_{1:L}}q_{Z^{1:N}})$
$\displaystyle\stackrel{{\scriptstyle(d)}}{{\leq}}2/N+\mathbb{V}(w_{E_{1:L}Z^{1:N}},p^{unif}_{\bar{E}_{1:L}}w_{Z^{1:N}})$
$\displaystyle\stackrel{{\scriptstyle(e)}}{{\leq}}2/N+\sqrt{{\displaystyle\sum_{\begin{subarray}{c}{\mathcal{S}\subseteq\mathcal{L}},{\mathcal{S}\neq\emptyset}\end{subarray}}}2^{r_{X_{\mathcal{S}}}-H_{\infty}({w}_{{{X}_{\mathcal{S}}^{1:N}}Z^{1:N}}|q_{Z^{1:N}})}}$
$\displaystyle\stackrel{{\scriptstyle(f)}}{{\leq}}2/N+{{{\sqrt{{\displaystyle\sum_{\begin{subarray}{c}{\mathcal{S}\subseteq\mathcal{L}},{\mathcal{S}\neq\emptyset}\end{subarray}}}2^{r_{X_{\mathcal{S}}}-NH(X_{\mathcal{S}}|Z)+N\delta^{*}_{\mathcal{L}}(N)}}}}}$
$\displaystyle\stackrel{{\scriptstyle(g)}}{{=}}2/N+\left(\displaystyle\sum_{\begin{subarray}{c}{\mathcal{S}\subseteq\mathcal{L}},{\mathcal{S}\neq\emptyset}\end{subarray}}2^{\sum_{l\in\mathcal{S}}(N(H(X_{l}|ZX_{1:l-1})-\frac{\epsilon_{2}}{2}))}\right.$
$\displaystyle\phantom{--}\left.\times
2^{-N\sum_{l\in\mathcal{S}}H(X_{l}|ZX_{\llbracket
1,l-1\rrbracket\cap\mathcal{S}})+N\delta^{*}_{\mathcal{L}}(N)}\right)^{1/2}$
$\displaystyle\stackrel{{\scriptstyle(h)}}{{\leq}}2/N+{{{\sqrt{{\displaystyle\sum_{\begin{subarray}{c}{\mathcal{S}\subseteq\mathcal{L}},{\mathcal{S}\neq\emptyset}\end{subarray}}}2^{\sum_{l\in\mathcal{S}}N(-\frac{\epsilon_{2}}{2}+\delta^{*}_{\mathcal{L}}(N))}}}}}$
$\displaystyle\stackrel{{\scriptstyle(i)}}{{\leq}}2/N+\sqrt{{2^{L}2^{-N\xi}}}\xrightarrow{N\to+\infty}0,$

where $(a)$ holds by the triangle inequality, $(b)$ holds by (19) and the data
processing inequality, $(c)$ holds by (17) and the triangle inequality, $(d)$
holds by (17), $(e)$ holds by Lemma 17 in Appendix B, $(f)$ holds by (18) and
because for any $\mathcal{S}\subseteq\mathcal{L}$,
$\delta^{*}_{\mathcal{S}}(N)\leq\delta^{*}_{\mathcal{L}}(N)$, $(g)$ holds by
(16) and the chain rule, $(h)$ holds because conditioning reduces entropy,
$(i)$ holds because $|\mathcal{S}|\geq 1$ and
$\epsilon_{2}=2(\delta^{*}_{\mathcal{L}}(N)+\xi)$. ∎

We now show that in each encoding block, the random variables induced by the
coding scheme approximate well the target distribution.

######  Lemma 10.

For Block $i\in\llbracket 1,k\rrbracket$,

$\displaystyle\mathbb{V}(\widetilde{p}_{X_{1:L,i}^{1:N}Z_{i}^{1:N}},q_{X_{1:L}^{1:N}Z^{1:N}})\leq\delta^{*}_{i}(N),$
(20)

where $\delta^{*}_{i}(N)\triangleq
L(\delta(N)+\delta^{*(0)}(N))(\frac{L^{i}-1}{L-1})+L^{i+1}\delta(N)$.

###### Proof.

We prove the result by induction. For $i=1$, we have

$\displaystyle\mathbb{V}(\widetilde{p}_{X_{1:L,1}^{1:N}Z_{1}^{1:N}},q_{X_{1:L}^{1:N}Z^{1:N}})$
$\displaystyle=\mathbb{V}(\widetilde{p}_{Z_{1}^{1:N}|X_{1:L,1}^{1:N}}\widetilde{p}_{X_{1:L,1}^{1:N}},q_{Z^{1:N}|X_{1:L}^{1:N}}q_{X_{1:L}^{1:N}})$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\mathbb{V}(\widetilde{p}_{X_{1:L,1}^{1:N}},q_{X_{1:L}^{1:N}})$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}\sum_{l\in\mathcal{L}}\mathbb{V}(\widetilde{p}_{X_{l,1}^{1:N}},q_{X_{l}^{1:N}})$
(21) $\displaystyle\stackrel{{\scriptstyle(c)}}{{\leq}}L\delta(N),$

where $(a)$ holds because
$q_{Z^{1:N}|X_{1:L}^{1:N}}=\widetilde{p}_{Z_{1}^{1:N}\lvert X_{1:L,1}^{1:N}}$,
$(b)$ holds by the triangle inequality and because
${(\widetilde{X}_{l,1}^{1:N})}_{l\in\mathcal{L}}$ are jointly independent, and
$({X_{l}^{1:N}})_{l\in\mathcal{L}}$ are jointly independent, $(c)$ holds by
the source resolvability codes used at the transmitters because
$\frac{|E_{l,1}|}{N}>H(X_{l})+\epsilon_{2}/2,l\in\mathcal{L}$.

Assume now that, for $i\in\llbracket 2,k-1\rrbracket$, (20) holds. For any
$l\in\mathcal{L}$ and $i\in\llbracket 2,k\rrbracket$, consider $\bar{E}_{l,i}$
distributed according to ${p^{unif}_{\bar{E}_{l}}}$, the uniform distribution
over $\\{0,1\\}^{r_{X_{l}}}$, and let $p_{\bar{X}_{l,i}^{1:N}}$ denote the
distribution of $\bar{X}_{l,i}^{1:N}\triangleq
e^{X_{l}}_{N}(\bar{E}_{l,i},E_{l,i})$. For $i\in\llbracket 1,k-1\rrbracket$,
we have

$\displaystyle\mathbb{V}(\widetilde{p}_{X_{1:L,i+1}^{1:N}Z_{i+1}^{1:N}},q_{X_{1:L}^{1:N}Z^{1:N}})$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\sum_{l\in\mathcal{L}}\mathbb{V}(\widetilde{p}_{X_{l,i+1}^{1:N}},q_{X_{l}^{1:N}})$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}\sum_{l\in\mathcal{L}}\mathbb{V}(\widetilde{p}_{X_{l,i+1}^{1:N}},p_{\bar{X}_{l,i+1}^{1:N}})+\mathbb{V}(p_{\bar{X}_{l,i+1}^{1:N}},q_{X_{l}^{1:N}})$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{\leq}}\sum_{l\in\mathcal{L}}\mathbb{V}(\widetilde{p}_{X_{l,i+1}^{1:N}},p_{\bar{X}_{l,i+1}^{1:N}})+\delta(N)$
$\displaystyle\stackrel{{\scriptstyle(d)}}{{\leq}}\sum_{l\in\mathcal{L}}\mathbb{V}(\widetilde{p}_{E_{l,i+1}},p^{unif}_{\bar{E}_{l}})+\delta(N)$
$\displaystyle\stackrel{{\scriptstyle(e)}}{{\leq}}\sum_{l\in\mathcal{L}}\left(\delta(N)+\mathbb{V}(\widetilde{p}_{E_{l,i+1}},q_{G_{X_{l}}({X^{1:N}_{l}})})\right.$
$\displaystyle\phantom{--}\left.+\mathbb{V}(q_{G_{X_{l}}({X^{1:N}_{l}})},p^{unif}_{\bar{E}_{l}})\right)$
$\displaystyle\stackrel{{\scriptstyle(f)}}{{=}}\sum_{l\in\mathcal{L}}\left(\delta(N)+\mathbb{V}(\widetilde{p}_{G_{X_{l}}({X^{1:N}_{l,i}})},q_{G_{X_{l}}({X^{1:N}_{l}})})\right.$
$\displaystyle\phantom{--}\left.+\mathbb{V}(q_{G_{X_{l}}({X^{1:N}_{l}})},p^{unif}_{\bar{E}_{l}})\right)$
$\displaystyle\stackrel{{\scriptstyle(g)}}{{\leq}}\sum_{l\in\mathcal{L}}\delta(N)+\mathbb{V}(\widetilde{p}_{{X}^{1:N}_{l,i}},q_{{X^{1:N}_{l}}})+\delta^{*(0)}(N)$
$\displaystyle\stackrel{{\scriptstyle(h)}}{{\leq}}\sum_{l\in\mathcal{L}}\delta(N)+\delta^{*}_{i}(N)+\delta^{*(0)}(N)$
$\displaystyle=L\left(\delta(N)+\delta^{*}_{i}(N)+\delta^{*(0)}(N)\right),$

where $(a)$ holds similar to (21), $(b)$ holds by the triangle inequality,
$(c)$ holds by the source resolvability codes used at the transmitters because
$\frac{|\bar{E}_{l,i}|+|E_{l,i}|}{N}=H(X_{l})+\epsilon_{2}/2,l\in\mathcal{L}$,
$(d)$ holds by the data processing inequality, $(e)$ holds by the triangle
inequality, $(f)$ holds because for any $l\in\mathcal{L}$,
$\widetilde{E}_{l,i+1}\triangleq G_{X_{l}}(X_{l,i}^{1:N})$ by Line $5$ of
Algorithm 3, $(g)$ holds by the data processing inequality and Lemma 9, $(h)$
holds by the induction hypothesis. ∎

Next, we show that the recycled randomness in Block $i\in\llbracket
2,k\rrbracket$ is almost independent from the channel outputs of Block $i-1$.

######  Lemma 11.

For $i\in\llbracket 2,k\rrbracket$, we have

$\displaystyle\mathbb{V}(\widetilde{p}_{E_{1:L,i}{Z}_{i-1}^{1:N}},\widetilde{p}_{E_{1:L,i}}\widetilde{p}_{{Z}_{i-1}^{1:N}})\leq\delta^{*(1)}_{i}(N).$

where $\delta^{*(1)}_{i}(N)\triangleq 4\delta_{i-1}^{*}(N)+2\delta^{*(0)}(N)$.

###### Proof.

We have

$\displaystyle\mathbb{V}(\widetilde{p}_{E_{1:L,i}{Z}_{i-1}^{1:N}},\widetilde{p}_{E_{1:L,i}}\widetilde{p}_{{Z}_{i-1}^{1:N}})$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\mathbb{V}(\widetilde{p}_{E_{{1:L,i}}Z_{i-1}^{1:N}},p^{unif}_{\bar{E}_{{1:L}}}\widetilde{p}_{Z_{i-1}^{1:N}})$
$\displaystyle\phantom{--}+\mathbb{V}(p^{unif}_{\bar{E}_{1:L}}\widetilde{p}_{Z_{i-1}^{1:N}},\widetilde{p}_{E_{1:L,i}}\widetilde{p}_{{Z}_{i-1}^{1:N}})$
$\displaystyle\leq
2\mathbb{V}(\widetilde{p}_{E_{{1:L,i}}Z_{i-1}^{1:N}},p^{unif}_{\bar{E}_{1:L}}\widetilde{p}_{Z_{i-1}^{1:N}})$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}2\left(\mathbb{V}(\widetilde{p}_{E_{1:L,i}Z_{i-1}^{1:N}},q_{G_{X_{1:L}}({X^{1:N}_{1:L}})Z^{1:N}})\right.$
$\displaystyle\phantom{--}\left.+\mathbb{V}(q_{G_{X_{1:L}}({X^{1:N}_{1:L})Z^{1:N}}},p^{unif}_{\bar{E}_{1:L}}q_{Z^{1:N}})\right.$
$\displaystyle\phantom{--}\left.+\mathbb{V}(p^{unif}_{\bar{E}_{1:L}}q_{Z^{1:N}},p^{unif}_{\bar{E}_{1:L}}\widetilde{p}_{Z^{1:N}_{i-1}})\right)$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{\leq}}2(\mathbb{V}(\widetilde{p}_{{X}_{1:L,i-1}^{1:N}Z_{i-1}^{1:N}},q_{{X}_{1:L}^{1:N}Z^{1:N}})+{\delta^{*(0)}(N)}$
$\displaystyle\phantom{--}+\mathbb{V}(q_{Z^{1:N}},\widetilde{p}_{Z_{i-1}^{1:N}}))$
$\displaystyle\stackrel{{\scriptstyle(d)}}{{\leq}}4\delta^{*}_{i-1}(N)+2{\color[rgb]{0,0,0}\delta^{*(0)}(N)},$

where $(a)$ and $(b)$ hold by the triangle inequality, $(c)$ holds by the data
processing inequality because $\widetilde{E}_{1:L,i}\triangleq
G_{X_{1:L}}(X_{1:L,i-1}^{1:N})$ by Line $5$ of Algorithm 3, and by Lemma 9,
$(d)$ holds by Lemma 10. ∎

Next, we show that the recycled randomness in Block $i\in\llbracket
2,k\rrbracket$ is almost independent of the channel outputs in Blocks $1$ to
$i-1$ considered jointly.

######  Lemma 12.

For $i\in\llbracket 2,k\rrbracket$, we have

$\mathbb{V}\left(\widetilde{p}_{E_{1:L,i}Z_{1:i-1}^{1:N}},\widetilde{p}_{E_{1:L,i}}\widetilde{p}_{Z_{1:i-1}^{1:N}}\right)\leq\delta_{i}^{*(2)}(N),$

where
$\delta_{i}^{*(2)}(N)\triangleq(2^{i-1}-1)(4\delta_{i-1}^{*}(N)+2\delta^{*(0)}(N))$.

###### Proof.

We prove the result by induction. The lemma is true for $i=2$ by Lemma 11.
Assume now that the lemma holds for $i\in\llbracket 2,k-1\rrbracket$. Then,
for $i\in\llbracket 3,k\rrbracket$, we have

$\displaystyle\mathbb{V}\left(\widetilde{p}_{Z_{1:i-1}^{1:N}E_{1:L,i}},\widetilde{p}_{Z_{1:i-1}^{1:N}}\widetilde{p}_{E_{1:L,i}}\right)$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\mathbb{V}\left(\widetilde{p}_{Z_{1:i-1}^{1:N}E_{1:L,i}},\widetilde{p}_{Z_{1:i-2}^{1:N}}\widetilde{p}_{Z_{i-1}^{1:N}E_{1:L,i}}\right).$
$\displaystyle\phantom{--}+\mathbb{V}\left(\widetilde{p}_{Z_{1:i-2}^{1:N}}\widetilde{p}_{Z_{i-1}^{1:N}E_{1:L,i}},\widetilde{p}_{Z_{1:i-2}^{1:N}}\widetilde{p}_{Z_{i-1}^{1:N}}\widetilde{p}_{E_{1:L,i}}\right)$
$\displaystyle\phantom{--}+\mathbb{V}\left(\widetilde{p}_{Z_{1:i-2}^{1:N}}\widetilde{p}_{Z_{i-1}^{1:N}}\widetilde{p}_{E_{1:L,i}},\widetilde{p}_{Z_{1:i-1}^{1:N}}\widetilde{p}_{E_{1:L,i}}\right)$
$\displaystyle=\mathbb{V}\left(\widetilde{p}_{Z_{1:i-1}^{1:N}E_{1:L,i}},\widetilde{p}_{Z_{1:i-2}^{1:N}}\widetilde{p}_{Z_{i-1}^{1:N}E_{1:L,i}}\right)$
$\displaystyle\phantom{--}+\mathbb{V}\left(\widetilde{p}_{Z_{i-1}^{1:N}E_{1:L,i}},\widetilde{p}_{Z_{i-1}^{1:N}}\widetilde{p}_{E_{1:L,i}}\right)$
$\displaystyle\phantom{--}+\mathbb{V}\left(\widetilde{p}_{Z_{1:i-2}^{1:N}}\widetilde{p}_{Z_{i-1}^{1:N}},\widetilde{p}_{Z_{1:i-1}^{1:N}}\right)$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}\delta^{*(1)}_{i}(N)+2\mathbb{V}\left(\widetilde{p}_{Z_{1:i-1}^{1:N}E_{1:L,i-1:i}},\widetilde{p}_{Z_{1:i-2}^{1:N}}\widetilde{p}_{Z_{i-1}^{1:N}E_{1:L,i-1:i}}\right)$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{=}}\delta^{*(1)}_{i}(N)+2\mathbb{V}\left(\widetilde{p}_{Z_{1:i-2}^{1:N}E_{1:L,i-1}}\widetilde{p}_{Z_{i-1}^{1:N}E_{1:L,i}|E_{1:L,i-1}},\right.$
$\displaystyle\phantom{--}\left.\widetilde{p}_{Z_{1:i-2}^{1:N}}\widetilde{p}_{Z_{i-1}^{1:N}E_{1:L,i-1:i}}\right)$
$\displaystyle=\delta^{*(1)}_{i}(N)+2\mathbb{V}\left(\widetilde{p}_{Z_{1:i-2}^{1:N}E_{1:L,i-1}},\widetilde{p}_{Z_{1:i-2}^{1:N}}\widetilde{p}_{E_{1:L,i-1}}\right)$
$\displaystyle\stackrel{{\scriptstyle(d)}}{{\leq}}\delta^{*(1)}_{i}(N)+2\delta_{i-1}^{*(2)}(N),$

where $(a)$ holds by the triangle inequality, $(b)$ holds by Lemma 11, $(c)$
holds by the Markov chain
$(\widetilde{E}_{1:L,i},\widetilde{Z}_{i-1}^{1:N})-\widetilde{E}_{1:L,i-1}-\widetilde{Z}_{1:i-2}^{1:N}$,
$(d)$ holds by the induction hypothesis. ∎

The following lemmas show that the channel outputs of all the blocks are
asymptotically independent, and that the target output distribution is well
approximated jointly over all blocks.

######  Lemma 13.

We have

$\mathbb{V}\left(\widetilde{p}_{Z_{1:k}^{1:N}},\prod_{i=1}^{k}\widetilde{p}_{Z_{i}^{1:N}}\right)\leq(k-1)\delta_{k}^{*(2)}(N),$

where $\delta_{k}^{*(2)}(N)$ is defined in Lemma 12.

######  Lemma 14.

For block $i\in\llbracket 1,k\rrbracket$, we have

$\mathbb{V}\left(\widetilde{p}_{Z_{1:k}^{1:N}},q_{Z^{1:kN}}\right)\leq(k-1)\delta_{k}^{*(2)}(N)+k\delta^{*}_{k}(N),$

where $\delta_{k}^{*(2)}(N)$ is defined in Lemma 12 and $\delta_{k}^{*}(N)$ is
defined in Lemma 10.

The proofs of Lemmas 13 and 14 are similar to the proofs of Lemmas 6 and 7,
respectively, and are thus omitted. Finally, the next lemma shows that the
encoding scheme of Section VI-A achieves the desired rate-tuple.

######  Lemma 15.

Let $\epsilon_{0}>0$. For $k$ large enough and any $l\in\mathcal{L}$, we have
$\displaystyle\lim_{{{N\rightarrow+\infty}}}R_{l}=I(X_{l};Z|X_{1:l-1})+\epsilon_{0}+2\xi$.

###### Proof.

Let $k$ be such that for any $l\in\mathcal{L}$ we have
$\frac{H(X_{l})}{k}<\epsilon_{0}.$ Then, by the definition of $\epsilon_{2}$,
for any $l\in\mathcal{L}$, we have

$\displaystyle R_{l}$ $\displaystyle=\frac{\sum_{i=1}^{k}|E_{l,i}|}{kN}$
$\displaystyle=\frac{N(H(X_{l})+\epsilon_{2})+(k-1)N(I(X_{l};ZX_{1:l-1})+\epsilon_{2})}{kN}$
$\displaystyle\leq\frac{H(X_{l})}{k}+I(X_{l};ZX_{1:l-1})+\epsilon_{2}$
$\displaystyle\leq\epsilon_{0}+I(X_{l};ZX_{1:l-1})+\epsilon_{2}$
$\displaystyle\xrightarrow{N\to+\infty}I(X_{l};ZX_{1:l-1})+\epsilon_{0}+2\xi.$

∎

##  VII Concluding Remarks

We showed that codes for MAC resolvability can be obtained solely from source
resolvability codes, used as black boxes, and two-universal hash functions.
The crux of our approach is randomness recycling implemented with distributed
hashing across a block-Markov coding scheme. Since explicit constructions for
source resolvability codes and two-universal hash functions are known, our
approach provides explicit codes to achieve the entire multiple access channel
resolvability region for arbitrary channels with binary input alphabets.

##  Appendix A An explicit coding scheme for source resolvability

Let $n\in\mathbb{N}$ and $N\triangleq 2^{n}$. Let
$G_{n}\triangleq\left[\begin{smallmatrix}1&0\\\\[3.00003pt]
1&1\end{smallmatrix}\right]^{\otimes n}$ be the source polarization matrix
defined in [21]. For any set $\mathcal{A}\subseteq\llbracket 1,N\rrbracket$
and any sequence $X^{1:N}$, let $X^{1:N}[\mathcal{A}]$ be the components of
$X^{1:N}$ whose indices are in $\mathcal{A}$. Next, consider a binary
memoryless source $(\mathcal{X},q_{X})$, where $|\mathcal{X}|=2$. Let
$X^{1:N}$ be distributed according to
$q_{X^{1:N}}\triangleq\prod_{i=1}^{N}q_{X}$, and define $A^{1:N}\triangleq
G_{n}X^{1:N}$. Define also for $\beta<1/2$, $\delta_{N}\triangleq
2^{-N^{\beta}}$, the sets

$\displaystyle\mathcal{V}_{X}$ $\displaystyle\triangleq\left\\{i\in\llbracket
1,N\rrbracket:H(A^{i}|A^{1:i-1})>1-\delta_{N}\right\\},$
$\displaystyle\mathcal{H}_{X}$ $\displaystyle\triangleq\left\\{i\in\llbracket
1,N\rrbracket:H(A^{i}|A^{1:i-1})>\delta_{N}\right\\}.$

Algorithm 4 Encoding algorithm for source resolvability

0: A vector $R$ of $|\mathcal{V}_{X}|$ uniformly distributed bits

1: Define $\widetilde{A}^{1:N}[\mathcal{V}_{X}]\triangleq R$

2: Define $\widetilde{A}^{j}$ according to $q_{A^{j}|A^{1:j-1}}$ for
$j\in\mathcal{V}_{X}^{c}\backslash\mathcal{H}_{X}^{c}$ and as
$\widetilde{A}^{j}\triangleq\displaystyle\operatornamewithlimits{argmax}_{a\in\\{0,1\\}}q_{A^{j}|A^{1:j-1}}\\!(a|a^{1:j-1}\\!)$
for $j\in\mathcal{H}_{X}^{c}$

3: Define $\widetilde{X}^{1:N}\triangleq\widetilde{A}^{1:N}G_{n}$

In Algorithm 4, the distribution of $\widetilde{X}^{1:N}$ is such that
$\lim_{N\to\infty}\mathbb{V}(\widetilde{p}_{X^{1:N}},q_{X^{1:N}})=0$ by [22,
23]. Moreover, the rate of $R$ is
$\frac{|\mathcal{V}_{X}|}{N}\xrightarrow{N\to+\infty}H(X)$ by [24, Lemma 1],
and the rate of randomness used in Line 2 is $0$ by [10, Lemma 20]. Hence,
Algorithm 4 achieves the source resolvability of $(\mathcal{X},q_{X})$.

##  Appendix B Supporting Lemmas

A function $f_{X}$ defined over a finite alphabet $\mathcal{X}$ is
subnormalized non-negative if $f_{X}(x)\geq 0,\forall x\in\mathcal{X}$ and
$\sum_{x\in\mathcal{X}}f_{X}(x)\leq 1$. Additionally, for a subnormalized non-
negative function $f_{XY}$ defined over a finite alphabet
$\mathcal{X}\times\mathcal{Y}$, its marginals are defined as
$f_{X}(x)\triangleq\sum_{y\in\mathcal{Y}}f_{XY}(x,y),\forall x\in\mathcal{X}$
and $f_{Y}(y)\triangleq\sum_{x\in\mathcal{X}}f_{XY}(x,y),\forall
y\in\mathcal{Y}$, similar to probability distributions.

######  Lemma 16 ([25],[26, Lemma 2]).

Define $\mathcal{A}\triangleq\llbracket 1,A\rrbracket$. Let
$(\mathcal{T}_{a})_{a\in\mathcal{A}}$ be $A$ finite alphabets and define for
$\mathcal{S}\subseteq\mathcal{A}$,
$\mathcal{T}_{\mathcal{S}}\triangleq\bigtimes_{a\in\mathcal{S}}\mathcal{T}_{a}$.
Consider the random variables
$T^{1:N}_{\mathcal{A}}\triangleq({T}^{1:N}_{a})_{a\in\mathcal{A}}$ and
$Z^{1:N}$ defined over $\mathcal{T}_{\mathcal{A}}^{N}\times\mathcal{Z}^{N}$
with probability distribution
$q_{T^{1:N}_{\mathcal{A}}Z^{1:N}}\triangleq\prod_{i=1}^{N}q_{T_{\mathcal{A}}Z}$.
For any $\epsilon>0$, there exists a subnormalized non-negative function
$w_{T^{1:N}_{\mathcal{A}}Z^{1:N}}$ defined over
$\mathcal{T}^{N}_{\mathcal{A}}\times\mathcal{Z}^{N}$ such that
$\mathbb{V}(q_{T^{1:N}_{\mathcal{A}}Z^{1:N}},w_{T^{1:N}_{\mathcal{A}}Z^{1:N}})\leq\epsilon$
and

$\displaystyle H_{\infty}(w_{T^{1:N}_{\mathcal{S}}Z^{1:N}}|q_{Z^{1:N}})\geq
NH({T_{\mathcal{S}}}|Z)-N\delta_{\mathcal{S}}(N),\forall\mathcal{S}\subseteq\mathcal{A},$

where
$\delta_{\mathcal{S}}(N)\triangleq\log(\lvert\mathcal{T}_{\mathcal{S}}\rvert+3)\sqrt{\frac{2}{N}(A-\log\epsilon)}$,
and we have defined the min-entropy as in [27, 28], i.e.,

$\displaystyle H_{\infty}(w_{T^{1:N}_{\mathcal{S}}Z^{1:N}}|q_{Z^{1:N}})$
$\displaystyle\triangleq-\log\\!\\!\\!\displaystyle\max_{\begin{subarray}{c}{t^{1:N}_{\mathcal{S}}\in\mathcal{T}^{N}_{\mathcal{S}}}\\\
z^{1:N}\in\textup{supp}(q_{Z^{1:N}})\end{subarray}}\\!\\!\frac{w_{T^{1:N}_{\mathcal{S}}Z^{1:N}}(t^{1:N}_{\mathcal{S}},z^{1:N})}{q_{Z^{1:N}}(z^{1:N})}.$

######  Lemma 17 ([25],[26, Lemma 1]).

Consider a sub-normalized non-negative function $p_{X_{\mathcal{L}}Z}$ defined
over $\bigtimes_{l\in\mathcal{L}}\mathcal{X}_{l}\times\mathcal{Z}$, where
$X_{\mathcal{L}}\triangleq(X_{l})_{l\in\mathcal{L}}$ and, $\mathcal{Z}$,
$\mathcal{X}_{l}$, $l\in\mathcal{L}$, are finite alphabets. For
$l\in\mathcal{L}$, let
$F_{l}:\\{0,1\\}^{n_{l}}\longrightarrow\\{0,1\\}^{r_{l}}$, be uniformly chosen
in a family $\mathcal{F}_{l}$ of two-universal hash functions. Define
$s_{\mathcal{L}}\triangleq\prod_{l\in\mathcal{L}}|\mathcal{F}_{l}|$, and for
any $\mathcal{S}\subseteq\mathcal{L}$, define
$r_{\mathcal{S}}\triangleq\sum_{i\in\mathcal{S}}r_{i}$. Define also
${F}_{\mathcal{L}}\triangleq(F_{l})_{l\in\mathcal{L}}$ and
$F_{\mathcal{L}}(X_{\mathcal{L}})\triangleq\left(F_{l}(X_{l})\right)_{l\in\mathcal{L}}.$
Then, for any $q_{Z}$ defined over $\mathcal{Z}$ such that
$\textup{supp}(q_{Z})\subseteq\textup{supp}(p_{Z})$, we have

$\displaystyle\mathbb{V}({{p}_{F_{\mathcal{L}}(X_{\mathcal{L}}),F_{\mathcal{L}},Z}},p_{U_{\mathcal{K}}}p_{U_{\mathcal{F}}}p_{Z})$
$\displaystyle\leq{{{\sqrt{{\displaystyle\sum_{\begin{subarray}{c}{\mathcal{S}\subseteq\mathcal{L}},{\mathcal{S}\neq\emptyset}\end{subarray}}}2^{r_{\mathcal{S}}-H_{\infty}(p_{X_{\mathcal{S}}Z}|q_{Z})}}}}},$

where $p_{U_{\mathcal{K}}}$ and ${\color[rgb]{0,0,0}p_{U_{\mathcal{F}}}}$ are
the uniform distributions over $\llbracket 1,2^{r_{{\mathcal{L}}}}\rrbracket$
and $\llbracket 1,{s_{{\mathcal{L}}}}\rrbracket$, respectively.

##  Appendix C Proof of Lemma 1

The proof is similar to [16]. We have

$\displaystyle I(XY;Z)$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}I(XUV;Z)$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}I(U;Z)+I(X;Z\lvert
U)+I(V;Z\lvert UX),$

where $(a)$ holds because $I(XUV;Z)\geq I(XY;Z)$ since $Y=f(U,V)$, and
$I(XUV;Z)\leq I(XY;Z)$ since $(X,U,V)-(X,Y)-Z$ forms a Markov chain, $(b)$
holds by the chain rule.

We know by [16, Lemma 6] that $I(X;ZU)$ is a continuous function of
$\epsilon$, hence so is

$\displaystyle R_{1}=I(X;Z|U)=I(X;ZU),$

where the last equality holds by the independence between $X$ and $U$. Then,
$I(X;Z)$ and $I(X;Z|Y)$ are in the image of $R_{1}$ by $\eqref{lem1eqn1}$, and
hence, using $I(X;Z)\leq I(X;YZ)=I(X;Z|Y)$, $[I(X;Z),I(X;Z|Y)]$ is also in the
image of $R_{1}$ by continuity.

## References

  * [1] R. Sultana and R. Chou, “Explicit low-complexity codes for multiple access channel resolvability,” in _Proc. of the Annual Allerton Conf. on Communication, Control, and Computing_ , 2019, pp. 116–123.
  * [2] ——, “Explicit construction of multiple access channel resolvability codes from source resolvability codes,” in _Proc. of IEEE Int. Symp. Inf. Theory_ , 2020.
  * [3] Y. Steinberg, “Resolvability theory for the multiple-access channel,” _IEEE Trans. Inf. Theory_ , vol. 44, no. 2, pp. 472–487, 1998.
  * [4] T. S. Han and S. Verdú, “Approximation theory of output statistics,” _IEEE Transactions on Information Theory_ , vol. 39, no. 3, pp. 752–772, 1993\.
  * [5] A. Pierrot and M. Bloch, “Strongly secure communications over the two-way wiretap channel,” _IEEE Trans. Inform. Forensics Sec_ , vol. 6, no. 3, pp. 595–605, 2011.
  * [6] M. Yassaee and M. Aref, “Multiple access wiretap channels with strong secrecy,” in _Proc. of IEEE Inf. Theory Workshop 2010_ , pp. 1–5.
  * [7] M. Frey, I. Bjelakovic, and S. Stanczak, “The MAC resolvability region, semantic security and its operational implications,” _arXiv preprint arXiv:1710.02342_ , 2017.
  * [8] M. Bloch and J. Kliewer, “Strong coordination over a line network,” in _Proc. of IEEE Int. Symp. Inf. Theory_ , 2013, pp. 2319–2323.
  * [9] M. Bloch, L. Luzzi, and J. Kliewer, “Strong coordination with polar codes,” in _Proc. of the Annual Allerton Conf. on Communication, Control, and Compputing_ , 2012, pp. 565–571.
  * [10] R. Chou, M. Bloch, and J. Kliewer, “Empirical and strong coordination via soft covering with polar codes,” _IEEE Trans. Inf. Theory_ , vol. 64, no. 7, pp. 5087–5100, 2018.
  * [11] M. Hayashi and R. Matsumoto, “Secure multiplex coding with dependent and non-uniform multiple messages,” _IEEE Trans. Inf. Theory_ , vol. 62, no. 5, pp. 2355–2409, 2016.
  * [12] R. Amjad and G. Kramer, “Channel resolvability codes based on concatenation and sparse linear encoding,” in _Proc. of IEEE Int. Symp. Inf. Theory_ , 2015, pp. 2111–2115.
  * [13] R. Chou, M. Bloch, and J. Kliewer, “Low-complexity channel resolvability codes for the symmetric multiple-access channel,” in _Proc. of IEEE Inf. Theory Workshop_ , 2014, pp. 466–470.
  * [14] T. Han, “Information-spectrum methods in information theory volume 50 of,” _Applications of Mathematics_ , 2003.
  * [15] S. Vadhan, “Pseudorandomness,” _Foundations and Trends® in Theoretical Computer Science_ , vol. 7, no. 1–3, pp. 1–336, 2012.
  * [16] A. Grant, B. Rimoldi, R. Urbanke, and P. Whiting, “Rate-splitting multiple access for discrete memoryless channels,” _IEEE Trans. Inf. Theory_ , vol. 47, no. 3, pp. 873–890, 2001.
  * [17] J. L. Carter and M. N. Wegman, “Universal classes of hash functions,” _Journal of computer and system sciences_ , vol. 18, no. 2, pp. 143–154, 1979\.
  * [18] R. Chou, M. R. Bloch, and J. Kliewer, “Polar coding for empirical and strong coordination via distribution approximation,” in _Proc. of IEEE Int. Symp. Inf. Theory_ , 2015, pp. 1512–1516.
  * [19] J. Edmonds, “Submodular functions, matroids, and certain polyhedra,” in _Combinatorial Optimization_. Springer, 2003, pp. 11–26.
  * [20] R. Chou and A. Yener, “Polar coding for the multiple access wiretap channel via rate-splitting and cooperative jamming,” _IEEE Trans. Inf. Theory_ , vol. 64, no. 12, pp. 7903–7921, 2018.
  * [21] E. Arikan, “Source polarization,” in _Proc. of IEEE Int. Symp. Inf. Theory_ , 2010, pp. 899–903.
  * [22] R. Chou and M. Bloch, “Polar coding for the broadcast channel with confidential messages: A random binning analogy,” _IEEE Trans. Inf. Theory_ , vol. 62, no. 5, pp. 2410–2429, 2016.
  * [23] ——, “Using deterministic decisions for low-entropy bits in the encoding and decoding of polar codes,” in _Proc. of the Annual Allerton Conf. on Communication, Control, and Compputing_ , 2015, pp. 1380–1385.
  * [24] R. Chou, M. Bloch, and E. Abbe, “Polar coding for secret-key generation,” _IEEE Trans. Inf. Theory_ , vol. 61, no. 11, pp. 6213–6237, 2015.
  * [25] R. Chou, “Secret sharing over a public channel from correlated random variables,” in _Proc. of IEEE Int. Symp. Inf. Theory_ , 2018, pp. 991–995.
  * [26] ——, “Distributed secret sharing over a public channel from correlated random variables,” _arXiv preprint arXiv:2110.10307_ , 2021.
  * [27] R. Renner, “Security of quantum key distribution,” _International Journal of Quantum Information_ , vol. 6, no. 01, pp. 1–127, 2008.
  * [28] S. Watanabe and M. Hayashi, “Non-Asymptotic Analysis of Privacy Amplification via Rényi Entropy and Inf-Spectral Entropy,” in _Proc. of IEEE Int. Symp. Inf. Theory_ , 2013, pp. 2715–2719.