1

Interactive Communication for Data Exchange

arXiv:1601.03617v3 [cs.IT] 11 Nov 2017

Himanshu Tyagi, Member, IEEE, Pramod Viswanath, Fellow, IEEE, and Shun Watanabe, Member, IEEE

Abstract—Two parties observing correlated data seek to exchange their data using interactive communication. How many
bits must they communicate? We propose a new interactive
protocol for data exchange which increases the communication
size in steps until the task is done. We also derive a lower bound
on the minimum number of bits that is based on relating the
data exchange problem to the secret key agreement problem.
Our single-shot analysis applies to all discrete random variables
and yields upper and lower bounds of a similar form. In fact, the
bounds are asymptotically tight and lead to a characterization
of the optimal rate of communication needed for data exchange
for a general source sequence such as a mixture of IID random
variables as well as the optimal second-order asymptotic term in
the length of communication needed for data exchange for IID
random variables, when the probability of error is fixed. This
gives a precise characterization of the asymptotic reduction in the
length of optimal communication due to interaction; in particular,
two-sided Slepian-Wolf compression is strictly suboptimal.

I. I NTRODUCTION
Random correlated data (X, Y ) is distributed between two
parties with the first observing X and the second Y . What
is the optimal communication protocol for the two parties
to exchange their data? We allow (randomized) interactive
communication protocols and a nonzero probability of error.
This basic problem was introduced by El Gamal and Orlitsky
in [23] where they presented bounds on the average number of
bits of communication needed by deterministic protocols for
data exchange without error1 . When interaction is not allowed,
a simple solution is to apply Slepian-Wolf compression [29]
for each of the two one-sided data transfer problems. The
resulting protocol was shown to be of optimal rate, even
in comparison with interactive protocols, when the underlying observations are independent and identically distributed
(IID) by Csiszár and Narayan in [8]. They considered a
multiterminal version of this problem, namely the problem
of attaining omniscience, and established a lower bound on
the rate of communication to show that interaction does not
help in improving the asymptotic rate of communication if
the probability of error vanishes to 0. However, interaction
is known to be beneficial in one-sided data transfer (cf.
[24], [38], [39], [9]). Can interaction help to reduce the
communication needed for data exchange, and if so, what is
H. Tyagi is with the Department of Electrical Communication Engineering, Indian Institute of Science, Bangalore 560012, India. Email:
htyagi@ece.iisc.ernet.in
P. Viswanath is with the Department of Electrical and Computer Engineering, University of Illinois, Urbana-Champaign, IL 61801, USA. Email:
{pramodv}@illinois.edu
S. Watanabe is with the Department of Computer and Information Sciences,
Tokyo University of Agriculture and Technology, Tokyo 184-8588, Japan.
Email: shunwata@cc.tuat.ac.jp
1 They also illustrated the advantage of using randomized protocols when
error is allowed

the minimum length of interactive communication needed for
data exchange?
We address the data exchange problem, illustrated in Figure 1, and provide answers to the questions raised above. We
provide a new approach for establishing converse bounds for
problems with interactive communication that relates efficient
communication to secret key agreement and uses the recently
established conditional independence testing bound for the
length of a secret key [35]. Furthermore, we propose an
interactive protocol for data exchange which matches the
performance of our lower bound in several asymptotic regimes.
As a consequence of the resulting single-shot bounds, we
obtain a characterization of the optimal rate of communication
needed for data exchange for a general sequence (Xn , Yn )
such as a mixture of IID random variables as well as the
optimal second-order asymptotic term in the length of communication needed for data exchange for the IID random
variables (X n , Y n ), first instance of such a result in source
coding with interactive communication2 . This in turn leads to
a precise characterization of the gain in asymptotic length of
communication due to interaction.
Related work: The role of interaction in multiparty data
compression has been long recognized. For the data exchange
problem, this was first studied in [23] where interaction was
used to facilitate data exchange by communicating optimally
few bits in a single-shot setup with zero error. In a different
direction, [9], [38], [39] showed that interaction enables a
universal variable-length coding for the Slepian-Wolf problem
(see, also, [10] for a related work on universal encoding). Furthermore, it was shown in [38] that the redundancy in variablelength Slepian-Wolf coding with known distribution can be
improved by interaction. In fact, the first part of our protocol is
essentially the same as the one in [38] (see, also, [4]) wherein
the length of the communication is increased in steps until the
second√party can decode. In [38], the step size was chosen to
be O( n) for the universal scheme and roughly O(n1/4 ) for
the known distribution case. We recast this protocol in an information spectrum framework (in the spirit of [16]) and allow
for a flexible choice of the step size. By choosing this step size
appropriately, we obtain exact asymptotic results in various
regimes. Specifically, the optimal choice of this step size ∆ is
given by the square root
√ of the essential length of the spectrum
of PX|Y , i.e., ∆ = λmax − λmin where λmax and λmin are
large probability upper and lower bounds, respectively, for√the
random variable h(X|Y ) = − log PX|Y (X|Y ). The O( n)
choice for the universal case of [38] follows as a special case
since for the universal setup with IID source h(X n |Y n ) can
vary over an interval of length O(n). Similarly, for a given
2 In a different context, recently [2] showed that the second-order asymptotic term in the size of good channel codes can be improved using feedback.

2

Y

X

1

⇧
Ŷ

1

X̂

Fig. 1: The data exchange problem.
n
n
IID source, h(X
√ |Y ) can essentially vary over an interval
of length O( n) for which the choice of ∆ = O(n1/4 )
in [38] is appropriate by our general principle. While the
optimal choice of ∆ (upto the order) was identified in [38]
for special cases, the optimality of this choice was not shown
there. Our main contribution is a converse which shows that
our achieved length of communication is optimal in several
asymptotic regimes. As a by-product, we obtain a precise
characterization of gain due to interaction, one of the few such
instances available in the literature. Drawing on the techniques
introduced in this paper, the much more involved problem of
simulation of interactive protocols was addressed in [33], [34].
Organization: The remainder of this paper is organized
as follows: We formally describe the data exchange problem
in Section II. Our results are summarized in Section III. Section IV contains our single-shot achievability scheme, along
with the necessary prerequisites to describe it, and Section V
contains our single-shot converse bound. The strong converse
and second-order asymptotics for the communication length
and the optimal rate of communication for general sources are
obtained as a consequence of single-shot bounds in Section VI
and VII, respectively. The final section contains a discussion
of our results and extensions to the error exponent regime.

II. P ROBLEM FORMULATION
Let the first and the second party, respectively, observe discrete random variables X and Y taking values in finite sets X
and Y. The two parties wish to know each other’s observation
using interactive communication over a noiseless (error-free)
channel. The parties have access to local randomness (private
coins) UX and UY and shared randomness (public coins) U
such that the random variables UX , UY , U are finite-valued
and mutually independent and independent jointly of (X, Y ).
For simplicity, we resrict to tree-protocols (cf. [20]). A treeprotocol π consists of a binary tree, termed the protocol-tree,
with the vertices labeled by 1 or 2. The protocol starts at the
root and proceeds towards the leaves. When the protocol is
at vertex v with label iv ∈ {1, 2}, party iv communicates a
bit bv based on its local observations (X, UX , U ) for iv = 1
or (Y, UY , U ) for iv = 2. The protocol proceeds to the leftor right-child of v, respectively, if bv is 0 or 1. The protocol
terminates when it reaches a leaf, at which point each party
produces an output based on its local observations and the
bits communicated during the protocol, namely the transcript
Π = π(X, Y, UX , UY , U ). Figure 2 shows an example of a
protocol tree.
The length of a protocol π, denoted |π|, is the maximum
accumulated number of bits transmitted in any realization of
the protocol, namely the depth of the protocol tree.
Definition 1. For 0 ≤ ε < 1, a protocol π attains εdata exchange (ε-DE) if there exist functions Ŷ and X̂ of

2

2
1

2

Fig. 2: A two-party protocol tree.
(X, Π, UX , U ) and (Y, Π, UX , U ), respectively, such that
P(X̂ = X, Ŷ = Y ) ≥ 1 − ε.

(1)

The minimum communication for ε-DE Lε (X, Y ) is the infimum of lengths of protocols3 that attain ε-DE, i.e., Lε (X, Y )
is the minimum number of bits that must be communicated by
the two parties in order to exchange their observed data with
probability of error less than ε.
Protocols with 2 rounds of communication Π1 and Π2 which
are functions of only X and Y , respectively, are termed simple
protocols. We denote by Lsε (X, Y ) the minimum communication for ε-DE by a simple protocol.
III. S UMMARY OF RESULTS
To describe our results, denote by h(X) = − log PX (X)
and h(X|Y ) = − log PX|Y (X|Y ), respectively, the entropy
density of X and the conditional entropy density of X given
Y . Also, pivotal in our results is a quantity we call the sum
conditional entropy density of X and Y defined as
h(X4Y ) := h(X|Y ) + h(Y |X).
An interactive data exchange protocol. Our data exchange
protocol is based on an interactive version of the Slepian-Wolf
protocol where the length of the communication is increased
in steps until the second party decodes the data of the first.
Similar protocols have been proposed earlier for distributed
data compression in [10], [38], for protocol simulation in [4],
and for secret key agreement in [17], [16].
In order to send X to an observer of Y , a single-shot version
of the Slepian-Wolf protocol was proposed in [22] (see, also,
[13, Lemma 7.2.1]). Roughly speaking, this protocol simply
hashes X to as many bits as the right most point in the
spectrum4 of PX|Y . The main shortcoming of this protocol for
our purpose is that it sends the same number of bits for every
realization of (X, Y ). However, we would like to use as few
bits as possible for sending X to party 2 so that the remaining
bits can be used for sending Y to party 1. Note that once X
is recovered by party 2 correctly, it can send Y to Party 1
without error using, say, Shannon-Fano-Elias coding (eg. see
[5, Section 5]); the length of this second communication is
3 By derandomizing (1), it is easy to see that local and shared randomness
does not help, and deterministic protocols attain Lε (X, Y ).
4 Spectrum of a distribution P
X refers, loosely, to the distribution of the
random variable − log PX (X).

3

dh(Y |X)e bits. Our protocol accomplishes the first part above
using roughly h(X|Y ) bits of communication.
Specifically, in order to send X to Y we use a spectrum
slicing technique introduced in [13] (see, also, [17], [16]). We
divide the support [λmin , λmax ] of spectrum of PX|Y into N
slices size ∆ each; see Figure 3 for an illustration.

Specifically, the “excess” randomness generated when the
parties observing X and Y share a communication Π can
be extracted as a secret key independent of Π using the
leftover hash lemma [19], [28]. Thus, denoting by Sε (X, Y )
the maximum length of secret key and by H the length of the
common randomness (cf. [1]) generated by the two parties
during the protocol, we get

Bits used
by Protocol 1

H − Lε (X, Y ) ≤ Sε (X, Y ).

Bits used
by Slepian-Wolf

min

i

h(X | Y )

max

Fig. 3: Spectrum slicing in Protocol 1.
The protocol begins with the left most slice and party 1
sends λmin + ∆ hash bits to party 2. If party 2 can find a
unique x that is compatible with the received hash bits and
h(x|Y ) is within the current slice of conditional information
spectrum, it sends back an ACK and the protocol stops. Else,
party 2 sends back a NACK and the protocol now moves to
the next round, in which Party 1 sends additional ∆ hash bits.
The parties keep on moving to the next slice until either party
2 sends an ACK or all slices are covered. We will show that
this protocol is reliable and uses no more than h(X|Y ) + ∆ +
N bits of communication for each realization of (X, Y ). As
mentioned above, once party 2 gets X, it sends back Y using
h(Y |X)+1 bits, thereby resulting in an overall communication
of h(X4Y ) + ∆ + N + 1 bits. In our applications, we shall
choose N and ∆ to be of negligible order in comparison with
the tail bounds for h(X4Y ). Thus, we have the following
upper bound on Lε (X, Y ). (The statement here is rough; see
Theorem 2 below for a precise version.)
Result 1 (Rough statement of the single-shot upper bound).
For every 0 < ε < 1,
Lε (X, Y ) . inf{γ : P (h(X4Y ) > γ) ≤ ε}.
A converse bound. Our next result, which is perhaps the
main contribution of this paper, is a lower bound on Lε (X, Y ).
This bound is derived by connecting the data exchange problem to the two-party secret key agreement problem. For an
illustration of our approach in the case of IID random variables
X n and Y n , note that the optimal rate of a secret key that can
be generated is given by I(X ∧ Y ), the mutual information
between X and Y [21], [1]. Also, using a privacy amplification
argument (cf. [3], [27]), it can be shown that a data exchange
protocol using nR bits can yield roughly n(H(XY ) − R) bits
of secret key. Therefore, I(X ∧Y ) exceeds H(XY )−R, which
further gives
R ≥ H(X|Y ) + H(Y |X).
This connection between secret key agreement and data exchange was noted first in [8] where it was used for designing
an optimal rate secret key agreement protocol. Our converse
proof is, in effect, a single-shot version of this argument.

Next, we apply the recently established conditional independence testing upper bound for Sε (X, Y ) [35], [36], which
follows by reducing a binary hypothesis testing problem to
secret key agreement. However, the resulting lower bound
on Lε (X, Y ) is good only when the spectrum of PXY is
concentrated. Heuristically, this slack in the lower bound arises
since we are lower bounding the worst-case communication
complexity of the protocol for data exchange – the resulting
lower bound need not apply for every (X, Y ) but only for
a few realizations of (X, Y ) with probability greater than ε.
To remedy this shortcoming, we once again take recourse to
spectrum slicing and show that there exists a slice of the
spectrum of PXY where the protocol requires sufficiently large
number of bits; Figure 4 illustrates this approach. The resulting
lower bound on Lε (X, Y ) is stated below roughly, and a
precise statement is given in Theorem 4.
Lower bound
without
slicing
min

L✏

min

Upper bound
with
slicing
H✏
i+

with
slicing
i

L✏

i

h(XY )

without
slicing
max

H✏

max

Fig. 4: Bounds on secret key length leading to the converse.
Here Lε abbreviates Lε (X, Y ) and Hε denotes the ε-tail of
h(X4Y ).
Result 2 (Rough statement of the single-shot lower bound).
For every 0 < ε < 1,
Lε (X, Y ) & inf{γ : P (h(X4Y ) > γ) ≤ ε}.
Note that the upper and the lower bounds for Lε (X, Y )
in the two results above appear to be of the same form
(upon ignoring a few error terms). In fact, the displayed term
dominates asymptotically and leads to tight bounds in several
asympotitic regimes. Thus, the imprecise forms above capture
the spirit of our bounds.
Asymptotic optimality. The single-shot bounds stated
above are asymptotically tight up to the first order term for any
sequence of random variables (Xn , Yn ), and up to the second
order term for a sequence of IID random variables (X n , Y n ).
Specifically, consider a general source sequence (X, Y) =
{(Xn , Yn )}∞
n=1 . We are interested in characterizing the minimum asymptotic rate of communication for asymptotically
error-free data exchange, and seek its comparison with the
minimum rate possible using simple protocols.

4

Definition 2. The minimum rate of communication for data
exchange R∗ is defined as
1
R (X, Y) = inf lim sup Lεn (Xn , Yn ),
εn n→∞ n
∗

where the infimum is over all εn → 0 as n → ∞. The
corresponding minimum rate for simple protocols is denoted
by Rs∗ .
Denote by H(X4Y), H(X|Y), and H(Y|X), respectively, the lim sup in probability of random variables
h(Xn 4Yn ), h(Xn |Yn ), and h(Yn |Xn ). The quantity H(X|Y)
is standard in information spectrum method [14], [13] and
corresponds to the asymptotically minimum rate of communication needed to send Xn to an observer of Yn [22] (see, also,
[13, Lemma 7.2.1]). Thus, a simple communication protocol
of rate H(X|Y) + H(Y|X) can be used to accomplish data
exchange. In fact, a standard converse argument can be used
to show the optimality of this rate for simple communication.
Therefore, when we restrict ourselves to simple protocols, the
asymptotically minimum rate of communication needed is
Rs∗ (X, Y) = H(X|Y) + H(Y|X).
As an illustration, consider the case when (Xn , Yn ) are gener(1)
ated by a mixture of two n-fold IID distributions PX n Y n and
(2)
PX n Y n . For this case, the right-side above equals (cf. [13])
max{H(X (1) | Y (1) ), H(X (2) | Y (2) )}

+ max{H(Y (1) | X (1) ), H(Y (2) | X (2) )}.

Can we improve this rate by using interactive communication?
Using our single-shot bounds for Lε (X, Y ), we answer this
question in the affirmative.
Result 3 (Min rate of communication for data exchange).
For a sequence of sources (X, Y) = {(Xn , Yn )}∞
n=1 ,
R∗ (X, Y) = H(X4Y).

For the mixture of IID example above,
H(X4Y) = max{H(X (1) | Y (1) ) + H(Y (1) | X (1) ),
H(X (2) | Y (2) ) + H(Y (2) | X (2) )},

and therefore, simple protocols are strictly suboptimal in
general. Note that while the standard information spectrum
techniques suffice to prove the converse when we restrict to
simple protocols, their extension to interactive protocols is
unclear and our single-shot converse above is needed.
Turning now to the case of IID random variables, i.e. when
Xn = X n = (X1 , ..., Xn ) and Yn = Y n = (Y1 , ..., Yn ) are
n-IID repetitions of random variables (X, Y ). For brevity,
denote by R∗ (X, Y ) the corresponding minimum rate of
communication for data exchange, and by H(X4Y ) and V ,
respectively, the mean and the variance of h(X4Y ). Earlier,
Csiszár and Narayan [8] showed that R∗ (X, Y ) = H(X4Y ).
We are interested in a finer asymptotic analysis than this first
order characterization.
In particular, we are interested in characterizing the asymptotic behavior of Lε (X n , Y n ) up to the second-order term, for

every fixed ε in (0,1). We need the following notation:
1
Lε (X n , Y n ), 0 < ε < 1.
n
Note that R∗ (X, Y ) = supε∈(0,1) Rε∗ (X, Y ). Our next result
shows that Rε∗ (X, Y ) does not depend on ε and constitutes a
strong converse for the result in [8].
Rε∗ (X, Y ) = lim

n→∞

Result 4 (Strong converse). For every 0 < ε < 1,
Rε∗ (X, Y ) = H(X4Y ).
In fact, this result follows from a general result characterizing the second-order asymptotic term5 .
Result 5 (Second-order asymptotic behavior). For every
0 < ε < 1,
√
√
Lε (X n , Y n ) = nH(X4Y ) + nV Q−1 (ε) + o( n),
where Q(a) is the tail probability of the standard Gaussian
distribution and V is the variance of the sum conditional
entropy density h(X4Y ).
While simple protocols are optimal for the first-order term
for IID observations, Example 1 in Section VII exhibits the
strict suboptimality of simple protocols for the second-order
term.
IV. A SINGLE - SHOT DATA EXCHANGE PROTOCOL
We present a single-shot scheme for two parties to exchange
random observations X and Y . As a preparation for our
protocol, we consider the restricted problem where only the
second party observing Y seeks to know the observation X
of the first party. This basic problem was introduced in the
seminal work of Slepian and Wolf [29] for the case where
the underlying data is IID where a scheme with optimal rate
was given. A single-shot version of the Slepian-Wolf scheme
was given in [22] (see, also, [13, Lemma 7.2.1]). which we
describe below.
Using the standard “random binning” and “typical set”
decoding argument, it follows that there exists an l-bit communication Π1 = Π1 (X) and a function X̂ of (Π1 , Y ) such
that


P X 6= X̂ ≤ P (h(X|Y ) > l − η) + 2−η .
(2)
In essence, the result of [22] shows that we can send X to
Party 2 with a probability of error less than ε using roughly
as many bits as the ε-tail of h(X|Y ). However, the proposed
scheme uses the same number of bits for every realization
of (X, Y ). In contrast, we present an interactive scheme that
achieves the same goal and uses roughly h(X|Y ) bits when
the underlying observations are (X, Y )
While the bound in (2) can be used to establish the
asymptotic rate optimality of the Slepian-Wolf scheme even
for general sources, the number of bits communicated can be
reduced for specific realizations of X, Y . This improvement is
achieved using an interactive protocol with an ACK − NACK
5 Following the pioneering work of Strassen [30], study of these secondorder terms in coding theorems has been revived recently by Hayashi [15],
[18] and Polyanskiy, Poor, and Verdú [26].

5

feedback which halts as soon as the second party decodes
first’s observation; this protocol is described in the next
subsection. A similar scheme was introduced by Feder and
Shulman in [10], a variant of which was shown to be of least
average-case complexity for stationary sources by Yang and
He in [38], requiring H(X | Y ) bits on average. Another
variant of this scheme has been used recently in [16] to
generate secret keys of optimal asymptotic length upto the
second-order term.
A. Interactive Slepian-Wolf Compression Protocol
We begin with an interactive scheme for sending X to an
observer of Y , which hashes (bins) X into a few values as
in the scheme of [22], but unlike that scheme, increases the
hash-size gradually, starting with λ1 = λmin and increasing the
size ∆-bits at a time until either X is recovered or λmax bits
have been sent. After each transmission, Party 2 sends either
an ACK-NACK feedback signal; the protocol stops when an
ACK symbol is received.
As mentioned in the introduction, we rely on spectrum
slicing. Our protocol focuses on the “essential spectrum” of
h(X|Y ), i.e., those values of (X, Y ) for which h(X|Y ) ∈
(λmin , λmax ). For λmin , λmax , ∆ > 0 with λmax > λmin , let
N=

λmax − λmin
,
∆

(3)

and
λi = λmin + (i − 1)∆, 1 ≤ i ≤ N.

(4)

Further, let
n
o
T0 = (x, y) : hPX|Y (x|y) ≥ λmax or hPX|Y (x|y) < λmin ,
(5)
and for 1 ≤ i ≤ N , let Ti denote the ith slice of the spectrum
given by
n
o
Ti = (x, y) : λi ≤ hPX|Y (x|y) < λi + ∆ .
(6)
Note that T0 corresponds to the complement of the “typical
set.” Finally, let Hl (X ) denote the set of all mappings h :
X → {0, 1}l .
Our protocol for transmitting X to an observer of Y is described in Protocol 1. The lemma below bounds the probability
of error for Protocol 1 when (x, y) ∈ Ti , 1 ≤ i ≤ N .
Theorem 1 (Interactive Slepian-Wolf). Protocol 1 with l =
λmin + ∆ + η sends at most (h (X|Y ) + ∆ + N + η) bits when
the observations are (X, Y ) ∈
/ T0 and has probability of error
less than


P X̂ 6= X ≤ PXY (T0 ) + N 2−η .
Note that when T0 is chosen to be of small probability,
Protocol 1 sends essentially the same number of bits in the
worst-case as the Slepian-Wolf protocol.
B. Interactive protocol for data exchange
Returning to the data exchange problem, our protocol for
data exchange builds upon Protocol 1 and uses it to first

Protocol 1: Interactive Slepian-Wolf compression
Input: Observations X and Y , uniform public
randomness U , and parameters l, ∆
Output: Estimate X̂ of X at party 2
Both parties use U to select h1 uniformly from Hl (X )
Party 1 sends Π1 = h1 (X)
if Party 2 finds a unique x ∈ T1 with hash value
h1 (x) = Π1 then
set X̂ = x
send back Π2 = ACK
else
send back Π2 = NACK
while 2 ≤ i ≤ N and party 2 did not send an ACK do
Both parties use U to select hi uniformly from
H∆ (X ), independent of h1 , ..., hi−1
Party 1 sends Π2i−1 = hi (X)
if Party 2 finds a unique x ∈ Ti with hash value
hj (x) = Π2j−1 , ∀ 1 ≤ j ≤ i then
set X̂ = x
send back Π2i = ACK
else
if More than one such x found then
protocol declares an error
else
send back Π2i = NACK
Reset i → i + 1
if No X̂ found at party 2 then
Protocol declares an error

transmit X to the second party (observing Y ). Once Party 2
has recovered X correctly, it sends Y to Party 1 without error
using, say, Shannon-Fano-Elias coding (eg. see [5, Section
5]); the length of this second communication is dh(Y |X)e
bits. When the accumulated number of bits communicated
in the protocol exceeds a prescribed length lmax , the parties
abort the protocol and declare an error.6 Using Theorem 1,
the probability of error of the combined protocol is bounded
above as follows.
Theorem 2 (Interactive data exchange protocol). Given
λmin , λmax , ∆, η > 0 and for N in (3), there exists a protocol
for data exchange of length lmax such that


P X 6= X̂ or Y 6= Ŷ
≤ P (h(X4Y ) + ∆ + N + η + 1 > lmax )
+ PXY (T0 ) + N 2−η .

Thus, we attain ε-DE using a protocol of length
lmax = λε + ∆ + N + η + 1,
where λε is the ε-tail of h(X4Y ). Note that using the
noninteractive Slepian-Wolf protocol on both sides will require
roughly as many bits of communication as the sum of ε-tails
of h(X|Y ) and h(Y |X), which, in general, is more than the
6 Alternatively, we can use the (noninteractive) Slepian-Wolf coding by
setting the size of hash as lmax − (h(X|Y ) + ∆ + N + η).

6

ε-tail of h(X|Y ) + h(Y |X).
C. Proof of Theorem 1
The theorem follows as a corollary of the following observation.
Lemma 3 (Performance of Protocol 1). For (x, y) ∈ Ti ,
1 ≤ i ≤ N , denoting by X̂ = X̂(x, y) the estimate of x at
Party 2 at the end of the protocol (with the convention that
X̂ = ∅ if an error is declared), Protocol 1 sends at most
(l + (i − 1)∆ + i) bits and has probability of error bounded
above as follows:


P X̂ 6= x | X = x, Y = y ≤ i2λmin +∆−l .
Proof. Since (x, y) ∈ Ti , an error occurs if there exists a
x̂ 6= x such that (x̂, y) ∈ Tj and Π2k−1 = h2k−1 (x̂) for
1 ≤ k ≤ j for some j ≤ i. Therefore, the probability of error
is bounded above as


P X̂ 6= x | X = x, Y = y
≤

i X
X
j=1 x̂6=x

P (h2k−1 (x) = h2k−1 (x̂), ∀ 1 ≤ k ≤ j)

× 1 (x̂, y) ∈ Tj
≤
=



i X
X


1
1 (x̂, y) ∈ Tj
l+(j−1)∆
2
j=1 x̂6=x

i X
X

1
|{x̂ | (x̂, y) ∈ Tj }|
l+(j−1)∆
2
j=1 x̂6=x

≤ i2λmin −l+∆ ,
where we have used the fact that log |{x̂ | (x̂, y) ∈ Tj }| ≤
λj + ∆. Note that the protocol sends l bits in the first transmission, and ∆ bits and 1-bit feedback in every subsequent
transmission. Therefore, no more than (l + (i − 1)∆ + i) bits
are sent.
V. C ONVERSE BOUND
Our converse bound, while heuristically simple, is technically involved. We first state the formal statement and provide
the high level ideas underlying the proof; the formal proof will
be provided later.
Our converse proof, too, relies on spectrum slicing to
find the part of the spectrum of PXY where the protocol
communicates large number of bits. As in the achievability
part, we shall focus on the “essential spectrum” of h(XY ).
Given λmax , λmin , and ∆ > 0, let N be as in (3) and the
set T0 be as in (5), with hPX|Y (x|y) replaced by hPXY (xy)
in those definitions.
Theorem 4. For 0 ≤ ε < 1, 0 < η < 1 − ε, and parameters
∆, N as above, the following lower bound on Lε (X, Y ) holds
for every γ > 0:


1
Lε (X, Y ) ≥ γ + 3 log Pγ − ε − PXY (T0 ) −
N +
1
+ log(1 − 2η) − ∆ − 6 log N − 4 log − 1,
η

where Pγ := PXY (h(X4Y ) > γ).
Thus, a protocol attaining ε-DE must communicate roughly
as many bits as ε-tail of h(X4Y ).
The main idea is to relate data exchange to secret key
agreement, which is done in the following two steps:
1) Given a protocol π for ε-DE of length l, use the leftover
hash lemma to extract an ε-secret key of length roughly
λmin − l.
2) The length of the secret key that has been generated
is bounded above by Sε (X, Y ), the maximum possible
length of an ε-secret key. Use the conditional independence testing bound in [35], [36] to further upper bound
Sε (X, Y ), thereby obtaining a lower bound for l.
This approach leads to a loss of λmax − λmin , the length of
the spectrum of PXY . However, since we are lower bounding
the worse-case communication complexity, we can divide the
spectrum into small slices of length ∆, and show that there is a
slice where the communication is high enough by applying the
steps above to the conditional distribution given that (X, Y )
lie in a given slice. This reduces the loss from λmax − λmin
to ∆.
A. Review of two party secret key agreement
Consider two parties with the first and the second party,
respectively, observing the random variable X and Y . Using
an interactive protocol Π and their local observations, the
parties agree on a secret key. A random variable K constitutes
a secret key if the two parties form estimates that agree
with K with probability close to 1 and K is concealed, in
effect, from an eavesdropper with access to communication
Π. Formally, let Kx and Ky , respectively, be randomized
functions of (X, Π) and (Y, Π). Such random variables Kx
and Ky with common range K constitute an ε-secret key (εSK) if the following condition is satisfied:
1
(2)
PKx Ky Π − Punif × PΠ
2

≤ ε,

where
(2)

Punif (kx , ky ) =

1(kx = ky )
|K|

,

and k·k is the variational distance. The condition above ensures
both reliable recovery, requiring P (Kx 6= Ky ) to be small, and
information theoretic secrecy, requiring the distribution of Kx
(or Ky ) to be almost independent of the communication Π and
to be almost uniform. See [35] for a discussion on connections
between the combined condition above and the usual separate
conditions for recovery and secrecy.
Definition 3. Given 0 ≤ ε < 1, the supremum over lengths
log |K| of an ε-SK is denoted by Sε (X, Y ).
A key tool for generating secret keys is the leftover hash
lemma [19], [28] which, given a random variable X and an lbit eavesdropper’s observation Z, allows us to extract roughly
Hmin (PX ) − l bits of uniform bits, independent of Z. Here
Hmin denotes the min-entropy and is given by
Hmin (PX ) = sup log
x

1
.
PX (x)

7

Formally, let F be a 2-universal family of mappings f : X →
K, i.e., for each x0 6= x, the family F satisfies
1
1 X
1(f (x) = f (x0 )) ≤
.
|F|
|K|
f ∈F

Lemma 5 (Leftover Hash). Consider random variables X
and Z taking values in a countable set X and a finite set Z,
respectively. Let S be a random seed such that fS is uniformly
distributed over a 2-universal family F. Then, for K = fS (X)
q
kPKZS − Punif PZS k ≤ |K||Z|2−Hmin (PX ) ,
where Punif is the uniform distribution on K.
The version above is a straightforward modification of the
leftover hash lemma in, for instance, [27] and can be derived
in a similar manner (see Appendix B of [16]).
Next, we recall the conditional independence testing upper
bound on Sε (X, Y ), which was established in [35], [36].
In fact, the general upper bound in [35], [36] is a singleshot upper bound on the secret key length for a multiparty
secret key agreement problem with side information at the
eavesdropper. Below, we recall a specialization of the general
result for the two party case with no side information at the
eavesdropper. In order to state the result, we need the following
concept from binary hypothesis testing.
Consider a binary hypothesis testing problem with null
hypothesis P and alternative hypothesis Q, where P and Q are
distributions on the same alphabet V. Upon observing a value
v ∈ V, the observer needs to decide if the value was generated
by the distribution P or the distribution Q. To this end, the
observer applies a stochastic test T, which is a conditional
distribution on {0, 1} given an observation v ∈ V. When
v ∈ V is observed, the test T chooses the null hypothesis
with probability T(0|v) and the alternative hypothesis with
probability T (1|v) = 1 − T (0|v). For 0 ≤ ε < 1, denote by
βε (P, Q) the infimum of the probability of error of type II
given that the probability of error of type I is less than ε, i.e.,
βε (P, Q) :=

inf

T : P[T]≥1−ε

Q[T],

(7)

where
P[T]

=

X

P(v)T(0|v),

v

Q[T]

=

X

Q(v)T(0|v).

v

The following upper bound for Sε (X, Y ) was established
in [35], [36].
Theorem 6 (Conditional independence testing bound).
Given 0 ≤ ε < 1, 0 < η < 1 − ε, the following bound
holds:

Sε (X, Y ) ≤ − log βε+η PXY , QX QY + 2 log(1/η),
for all distributions QX and QY on on X and Y, respectively.
We close by noting a further upper bound for βε (P, Q),
which is easy to derive (cf. [25]).

Lemma 7. For every 0 ≤ ε ≤ 1 and λ,
 


P (X)
<λ −ε
,
− log βε (P, Q) ≤ λ − log P log
Q (X)
+
where (x)+ = max{0, x}.
B. Converse bound for almost uniform distribution
First, we consider a converse bound under the almost
uniformity assumption. Suppose that there exist λmin and λmax
such that
λmin ≤ − log PXY (x, y) ≤ λmax ,

∀(x, y) ∈ supp(PXY ),

(8)

where supp(PXY ) denotes the support of PXY . We call such
a distribution PXY an almost uniform distribution with margin
∆ = (λmax − λmin ).
Theorem 8. Let PXY be almost uniform with margin ∆.
Given 0 ≤ ε < 1, for every 0 < η < 1−ε, and all distributions
QX and QY , it holds that
Lε (X, Y )
2

PXY (X, Y )
≥γ
≥ γ + log P − log
QX (X) QY (Y )

!

!
− ε − 2η

+

1
− ∆ − 4 log − 1.
η
Remark 1. If ∆ ≈ 0 (the almost uniform case), the bound
above yields Result 2 upon choosing QX = PX and QY =
PY .
Proof. Given a protocol π of length l that attains ε-DE,
using Lemma 5 we can generate an (ε + η)-SK that is almost
independent of Π and takes values in K with
log |K| ≥ λmin − l − 2 log(1/η) − 1.
Also, by Theorem 6
log |K| ≤ − log βε+2η (PXY , QX QY ) + 2 log(1/η),
which along with the inequality above and Lemma 7 yields
 


PXY (X, Y )
l ≥ λmin + log P log
< λ − ε − 2η
QX (X) QY (Y )
+
− λ − 4 log(1/η) − 1.
The claimed bound follows upon choosing λ = λmax − γ and
using assumption (8).
C. Converse bound for all distributions
The shortcoming of Theorem 8 is the ∆-loss, which is
negligible only if λmax ≈ λmin . To circumvent this loss, we
divide the spectrum of PXY into slices such that, conditioned
on any slice, the distribution is almost uniform with a small
margin ∆. To lower bound the worst-case communication
complexity of a given protocol, we identify a particular slice
where appropriately many bits are communicated; the required
slice is selected using Lemma 9 below.

8

Given λmax , λmin , and ∆ > 0, let N be as in (3), T0
be as in (5), and λi and Ti , too, be as defined there, with
hPX|Y (x|y) replaced by hPXY (xy) in those definitions. Let
random variable J take the value j when {(X, Y ) ∈ Tj }. For
a protocol Π attaining ε-DE, denote
Ecorrect := {X = X̂, Y = Ŷ },
Eγ := {h(X4Y ) ≥ γ},

(9)

Ej := Ecorrect ∩ T0c ∩ Eγ ∩ {J = j},

Pγ := PXY (Eγ ) .

1 ≤ j ≤ N,

Lemma 9. There exists an index 1 ≤ j ≤ N such that
PJ (j) > 1/N 2 and


1
.
PXY |J (Ej | j) ≥ Pγ − ε − PXY (T0 ) −
N
Proof. Let J1 be the set of indices 1 ≤ j ≤ N such that
PJ (j) > 1/N 2 , and let J2 = {1, ..., N } \ J1 . Note that
PJ (J2 ) ≤ 1/N . Therefore,
T0c

Pγ − ε − PXY (T0 ) ≤ P (Ecorrect ∩
∩ Eγ )
X
≤
PJ (j) PXY |J (Ej | j) + PJ (J2 )
j∈J1

≤ max PXY |J (Ej | j) +
j∈J1

1
.
N

Thus, the maximizing j ∈ J1 on the right satisfies the claimed
properties.
We now state our main converse bound.
Theorem 10 (Single-shot converse). For 0 ≤ ε < 1, 0 < η <
1 − ε, and parameters ∆, N as above, the following lower
bound on Lε (X, Y ) holds:


1
Lε (X, Y ) ≥ γ + 3 log Pγ − ε − PXY (T0 ) −
N +
1
+ log(1 − 2η) − ∆ − 6 log N − 4 log − 1.
η
Proof. Let j satisfy the properties stated in Lemma 9. The
basic idea is to apply Theorem 8 to PXY |Ej , where PXY |Ej
denotes the conditional distributions on X, Y given the event
Ej .
First, we have
PXY |Ej (x, y) ≥ PXY (x, y) .

(10)

Furthermore, denoting α = Pγ − ε − PXY (T0 ) − 1/N and
noting PJ (j) > 1/N 2 , we have for all (x, y) ∈ Ej that

1
PXY |Ej (x, y) ≤ PXY |J=j (x, y)
(11)
α
2
N
≤
PXY (x, y) ,
(12)
α
where PXY |J=j denotes the conditional distributions on X, Y
given {J = j}. Thus, (10) and (12) together imply, for all
(x, y) ∈ Ej ,
λj + log α − 2 log N ≤ − log PXY |Ej (x, y) ≤ λj + ∆,
i.e., PXY |Ej is almost uniform with margin ∆−log α+2 log N

(cf. (8)). Also, note that (12) implies


PXY |Ei (X, Y )2
PXY |Ej − log
≥ γ + 2 log α − 4 log N
PX (X) PY (Y )
!
2
PXY (X, Y )
≥ PXY |Ej − log
≥γ
PX (X) PY (Y )
= PXY |Ei (Eγ )
= 1,
where the final equality holds by the definition of Eγ in (9).
Moreover,


PXY |Ej X = X̂, Y = Ŷ = 1.
Thus, the proof is completed by applying Theorem 8 to
PXY |Ej with QX = PX and QY = PY , and ∆ − log α +
2 log N in place of ∆.
D. Converse bound for simple communication protocol
We close by noting a lower bound for the length of
communication when we restrict to simple communication.
For simplicity assume that the joint distribution PXY is
indecomposable, i.e., the maximum common function of X
and Y is a constant (see [12]) and the parties can’t agree
on even a single bit without communicating (cf. [37]). The
following bound holds by a standard converse argument using
the information spectral method (cf. [13, Lemma 7.2.2]).
Proposition 11. For 0 ≤ ε < 1, we have
Lsε (X, Y )

≥ inf l1 + l2 : ∀δ > 0,




P h(X|Y ) > l1 + δ or h(Y |X) > l2 + δ ≤ ε + 2 · 2−δ .
Proof: Since randomization (local or shared) does not
help in improving the length of communication (cf. [20, Chapter 3]) we can restrict to deterministic protocols. Then, since
PXY is indecomposible, both parties have to predetermine the
lengths of messages they send; let l1 and l2 , respectively, be
the length of message sent by the first and the second party.
For δ > 0, let
n
o
T1 := (x, y) : − log PX|Y (x|y) ≤ l1 + δ ,
n
o
T2 := (x, y) : − log PY |X (y|x) ≤ l2 + δ ,
and T := T1 ∩ T2 . Let A1 and A2 be the set of all (x, y) such
that party 2 and party 1 correctly recover x and y, respectively,
and let A := A1 ∩ A2 . Then, for any simple communication
protocol that attains ε-DE, we have
PXY (T c ) = PXY (T c ∩ Ac ) + PXY (T c ∩ A)

≤ PXY (Ac ) + PXY (T1c ∩ A) + PXY (T2c ∩ A)

≤ ε + PXY (T1c ∩ A1 ) + PXY (T2c ∩ A2 )
≤ ε + 2 · 2−δ ,

where the last inequality follows by a standard argument

9

∆=

(cf. [13, Lemma 7.2.2]) as follows:
X
PXY (T1c ∩ A1 ) ≤
PY (y) PX|Y (T1c ∩ A1 |y)

=N

η = ∆,

y

≤

X

≤

X

≤

X

y

y

PY (y) |{x : (x, y) ∈ A1 }|2−l1 −δ

lmax = n(H(X4Y) + δ) + 3∆ + 1
√
= n(H(X4Y) + δ) + O( n),

PY (y) |{x : (x, y) ∈ A1 }|2−l1 −δ
PY (y) 2−δ

y

= 2−δ ,
and similarly for PXY (T2c ∩ A2 ); the desired bound follows.

While the best rate of communication required for two
parties to exchange their data is known [8], and it can be
attained by simple (noninteractive) Slepian-Wolf compression
on both sides, the problem remains unexplored for general
sources. In fact, the answer is completely different in general
and simple Slepian-Wolf compression is suboptimal.
Formally, let (Xn , Yn ) with joint distribution7 PXn Yn be a
sequence of sources. We need the following concepts from the
information spectrum method; see [13] for a detailed account.
For random variables (X, Y) = {(Xn , Yn )}∞
n=1 , the the inf
entropy rate H(XY) and the sup entropy rate H(XY) are
defined as follows:




1
H(XY) = sup α | lim P
h(Xn Yn ) < α = 0 ,
n→∞
n




1
h(Xn Yn ) > α = 0 ;
H(XY) = inf α | lim P
n→∞
n
the sup-conditional entropy rate H(X|Y) is defined analogously by replacing h(Xn Yn ) with h(Xn |Yn ). To state our result, we also need another quantity defined by a limit-superior
in probability, namely the sup sum conditional entropy rate,
given by
H(X4Y)




1
h(Xn 4Yn ) > α = 0 .
= inf α | lim P
n→∞
n

=

R∗ (X, Y) = H(X4Y).

Proof. The claim follows from Theorems 2 and 10 on
choosing the spectrum slicing parameters λmin , λmax , and ∆
appropriately.
Specifically, using Theorem 2 with
λmax = n(H(X, Y) + δ),
7 The

distributions PXn Yn need not satisfy the consistency conditions.

λmin = n(H(X, Y) − ∆),

λmax = n(H(X, Y) + ∆),

γ = n(H(X4Y) − δ)
for arbitrarily fixed δ > 0, we get for n sufficiently large that
Lεn (Xn , Yn ) ≥ n(H(X4Y) − δ) + o(n).
Since δ > 0 is arbitrary, the proof is complete.
VII. S TRONG CONVERSE AND SECOND - ORDER
ASYMPTOTICS

We now turn to the case of IID observations (X n , Y n ) and
establish the second-order asymptotic term in Lε (X n , Y n ).
Theorem 13. For every 0 < ε < 1,
√
√
Lε (X n , Y n ) = nH(X4Y ) + nV Q−1 (ε) + o( n).
Proof. As before, we only need to choose appropriate
parameters in Theorems 2 and 10. Let T denote the third
central moment of the random variable h(X4Y ).
For the achievability part, note that for IID random
√ variables
(X n , Y n ) the spectrum of PX n Y n has width O( n). Therefore, the parameters ∆ and N can be O(n1/4 ). Specifically, by
standard measure concentration bounds (for bounded random
variables), for every δ > 0 √
there exists a constant c such √
that
with λmax = nH(XY ) + c n and λmin = nH(XY ) − c n,
P ((X n , Y n ) ∈ T0 ) ≤ δ.

The result below characterizes R∗ (X, Y) (see Definition 2).

λmin = n(H(X, Y) − δ),

where δ > 0 is arbitrary, we get a communication protocol of
rate H(X4Y) + δ + O(n−1/2 ) attaining εn -DE with εn → 0.
Since δ > 0 is arbitrary, R∗ (X, Y) ≤ H(X4Y).
For the other direction, given a sequence of protocols
attaining εn -DE with εn → 0. Let

and so, N = O(n). Using Theorem 10 with

VI. G ENERAL SOURCES

Theorem 12. For a sequence of sources (X, Y)
{(Xn , Yn )}∞
n=1 ,

p
λmax − λmin

For
λn = nH(X4Y ) +

√

nV Q

−1


ε − 2δ −

T3

√
2V 3/2 n


,

√
choosing ∆ = N = η = 2cn1/4 , and lmax = λn + 3∆ + 1
in Theorem 2, we get a protocol of length lmax satisfying
!
n


X
P X 6= X̂, or Y 6= Ŷ ≤ P
h(Xi 4Yi ) > λn + 2δ,
i=1

for n sufficiently large. Thus, the Berry-Esséen theorem
(cf. [11]) and the observation above gives a protocol of length
lmax attaining ε-DE. Therefore, using the Taylor approximation of Q(·) yields the achievability of the claimed protocol
length; we skip the details of this by-now-standard argument
(see, for instance, [26]).

10

Similarly, the converse follows by Theorem 10 and the
Berry-Esséen theorem upon choosing λmax , λmin , and N as in
the proof of converse part of Theorem 12 when λn is chosen
to be


√
T3
1
√
λn = nH(X4Y ) + nV Q−1 ε − 2 −
N
2V 3/2 n
√
= nH(X4Y ) + nV Q−1 (ε) + O(log n),
where the final equality is by the Taylor approximation of
Q(·).
In the previous section, we saw that interaction is necessary
to attain the optimal first order asymptotic term in Lε (Xn , Yn )
for a mixture of IID random variables. In fact, even for IID
random variables interaction is needed to attain the correct
second order asymptotic term in Lε (X n , Y n ), as shown by
the following example.
Example 1. Consider random variables X and Y with an
indecomposable joint distribution PXY such that the matrix
V = Cov([− log PX|Y (X|Y ) , − log PY |X (Y |X)])
V is nonsingular. For IID random variables (X n , Y n ) with
common distribution PXY , using Proposition 11 and a multidimensional Berry-Esséen theorem (cf. [31]), we get that
the second-order asymptotic term for the minimum length of
simple communication for ε-DE is given by8
√
√
Lsε (X n , Y n ) = nH(X4Y ) + nDε + o( n),
where
n
o
Dε := inf r1 + r2 : P (Z1 ≤ r1 , Z2 ≤ r2 ) ≥ 1 − ε ,
for Gaussian vector Z = [Z1 , Z2 ] with mean [0, 0] and
covariance matrix V. Since V is nonsingular,9 we have
n


o
√
V Q−1 (ε) = inf r : P Z1 + Z2 ≤ r ≥ 1 − ε
< Dε .
Therefore, Lε (X n , Y n ) has strictly smaller second order term
than Lsε (X n , Y n ), and interaction is necessary for attaining
the optimal second order term in Lε (X n , Y n ).
VIII. D ISCUSSION
We have presented an interactive data exchange protocol and
a converse bound which shows that, in a single-shot setup, the
parties can exchange data using roughly h(X∆Y ) bits when
the parties observe X and Y . Our analysis is based on the
information spectrum approach. In particular, we extend this
approach to enable handling of interactive communication. A
key step is the spectrum slicing technique which allows us to
split a nonuniform distribution into almost uniform “spectrum
slices”. Another distinguishing feature of this work is our
converse technique which is based on extracting a secret key
from the exchanged data and using an upper bound for the
8 The achievability part can be derived by a slight modification of the
arguments in [22],[13, Lemma 7.2.1].
9 For instance, when X is uniform random variable on {0, 1} and Y is
connected to X via a binary symmetric channel, the covariance matrix V is
singular and interaction does not help.

rate of this secret key. In effect, this falls under the broader
umbrella of common randomness decomposition methodology
presented in [32] that studies a distributed computing problem
by dividing the resulting common randomness into different
independent components with operational significance. As a
consequence, we obtain both the optimal rate for data exchange for general sources as well as the precise second-order
asymptotic term for IID observations (which in turn implies a
strong converse). Interestingly, none of these optimal results
can be obtained by simple communication and interaction is
necessary, in general. Note that our proposed scheme uses
O(n1/4 ) rounds of interaction; it remains open if fewer rounds
of interaction will suffice.
Another asymptotic regime, which was not considered in
this paper, is the error exponent regime where we seek to characterize the largest possible rate of exponential decay of error
probability with blocklength for IID observations. Specifically,
denoting by Perr (l|X, Y ) the least probability of error ε that
can be attained for data exchange by communicating less than
l bits, i.e.,
Perr (l|X, Y ) := inf{ε : Lε (X, Y ) ≤ l},
we seek to characterize the limit of

1
− log Perr 2nR |X n , Y n .
n
The following result is obtained using a slight modification
of our single-shot protocol for data exchange where the slices
of the spectrum Ti in (6) are replaced with type classes and
the decoder is replaced by a special case of the α-decoder
introduced in [6]. For a fixed rate R ≥ 0, our modified protocol
enables data exchange, with large probability, for every (x, y)
with joint type PX Y such that (roughly)
R > H(X4Y ).
The converse part follows from the strong converse of Result 4,
together with a standard measure change argument (cf. [7]).
The formal proof is given in Appendix A.
Result 6 (Error Exponent Behaviour). For a given rate R >
H(X4Y ), define


Er (R) := min D(QX Y kPXY ) + |R − H(X4Y )|+
QX Y

and
Esp (R) :=

inf

QX Y ∈Q(R)

D(QX Y kPXY ),

where |a|+ = max{a, 0} and

Q(R) := QX Y : R < H(X4Y ) .
Then, it holds that

1
lim inf − log Perr 2nR |X n , Y n ≥ Er (R)
n→∞
n
and that

1
lim sup − log Perr 2nR |X n , Y n ≤ Esp (R).
n
n→∞
Er (R) and Esp (R), termed the random coding exponent
and the sphere-packing exponent, may not match in general.

11

However, when R is sufficiently close to H(X4Y ), the two
bounds can be shown to coincide. In fact, in Appendix B we
exhibit an example where the optimal error exponent attained
by interactive protocols is strictly larger than that attained by
simple communication. Thus, in the error exponent regime,
too, interaction is strictly necessary.

following bound holds:
n
o
Nh (X X̂ Y )
≤
exp
−n(R
−
H(
X̂|X
Y
)
−
δ
)
,
n
φ(P
)
X̂ Y
|TXn Y |
(13)
where
δn = |X |2 |Y|

A PPENDIX
A. Achievability Proof of Result 6
In this appendix, we consider the error exponent and prove
Result 6. We use the method of types. The type of a sequence x
is denoted by Px . For a given type PX , the set of all sequences
of type PX is denoted by TXn . The set of all types on alphabet
X is denoted by Pn (X ). We use similar notations for joint
types and conditional types. For a pair (x, y) with joint type
PX Y , we denote H(x4y) = H(X4Y ). We refer the reader
to [7] for basic results on the method of type.
Fix R > 0 as the rate of communication exchanged (by
both the parties), but without adding the rate contributed
by ACK-NACK messages exchanged. We consider r rounds
R
protocol, where r = d ∆
e for a fixed ∆ > 0. Let Ri = i∆
for i = 1, . . . , r. Basic idea of the protocol is the same as
our single-shot protocol, i.e., we increment the hash size in
steps. However, when we consider the error exponent regime,
to reduce the contribution of “binning error” to the error
exponent, we need a more carefully designed protocol.
For a given joint type PX Y , the key modification we make
is to delay the start of communication by Party 2 (which started
once Ri > H(X|Y ) was satisfied). Heurisitcally, once Party 2
can decode x correctly, he can send y to Party 1 without error
by using roughly10 nH(Y |X) bits, where PX Y = Pxy . Thus,
the budget Party 1 can use is R−H(Y |X), which is larger than
H(X|Y ) when R > H(X4Y ). Therefore, allowing Party 1
to communicate more before Party 2 starts may reduce the
binning error probability.
Motivated by this reason, we assign the timing of decoding
to each joint type as follows:

φ(PX Y ) := min i : 1 ≤ i ≤ r, Ri ≥ R − H(Y |X) − ∆

= max i : 1 ≤ i ≤ r, Ri < R − H(Y |X)
if R − H(Y |X) − ∆ > 0, and φ(PX Y ) = 0 is R − H(Y |X) −
∆ ≤ 0.
For given hash functions h = (h1 , . . . , hr ) with hi : X n →
{1, . . . , 2dn∆e }, let Nh (X X̂ Y ) denote, for each joint type
PX X̂ Y , the number of pairs (x, y) ∈ TXn Y such that for some
x̂ 6= x with Pxx̂y = PX X̂ Y , the relations
hi (x) = hi (x̂), i = 1, . . . , φ(PX̂ Y )
hold. The next result is a slight modification of a lemma in
[6, Section 3]; the proof is almost the same and is omitted.
Lemma 14. There exist hash functions h = (h1 , . . . , hr ) such
that for every joint type PX X̂ Y such that φ(PX̂ Y ) 6= 0, the
10 Since Party 2 has to send the joint type P
X Y to Party 1, additional
|X ||Y| log(n + 1) bits are needed.

log(n + 1)
.
n

For the decoder, we use the minimum sum conditional
entropy decoder, which is a kind of α-decoder introduced in
[6].
Our protocol is described in Protocol 2.
Protocol 2: Type-based interactive data exchange protocol
Input: Observations X n and Y n , parameter ∆, and rate
R
Output: Estimate X̂ n of X n at Party 2 and Ŷ n of Y n at
Party 1
while 1 ≤ i ≤ N and Party 2 did not send an ACK do
Party 1 sends Π2i−1 = hi (X n )
if for Y n = y, Party 2 finds a unique x such that
φ(Pxy ) = i, hj (x) = Π2j−1 , ∀ 1 ≤ j ≤ i, and
H(x4y) ≤ H(x̂4y) for every x̂ 6= x satisfying
hj (x̂) = Π2j−1 , ∀ 1 ≤ j ≤ i then
set X̂ n = x
send back Π2i = ACK
else
if More than one such x found then
protocol declares an error
else
send back Π2i = NACK
Reset i → i + 1
if No X̂ n found at Party 2 then
Protocol declares an error
Party 2 send the joint type PX Y of (X̂ n , Y n ) = (x, y),
and send the index of y among TYn|X (x).

The achievability part of Result 6 can be seen as follows. Fix
a joint type PX Y . If φ(PX Y ) = 0, then an error occurs whenever (x, y) ∈ TXn Y . We also note that R − H(Y |X) − ∆ ≤ 0
implies |R − H(X4Y ) − ∆|+ = 0. Thus, the probability of
this kind of error is upper bounded by
X
exp{−n[D(PX Y kPXY )
P
∈Pn (X ×Y)
XY
φ(P
)=0
XY

+ |R − H(X4Y ) − ∆|+ ]}. (14)
Next, consider the case when φ(PX Y ) ≥ 1. For given conditional type PX̂|X Y , a sequence x̂ with (x, x̂, y) ∈ TXn X̂ Y
causes an error when
1) φ(PX̂ Y ) ≤ φ(PX Y ),
2)
hi (x̂) = hi (x), i = 1, . . . , φ(PX̂ Y )

12

3)

B. An Example Such That Interaction Improves Error Exponent

H(X̂4Y ) ≤ H(X4Y ).

Consider the following source: X and Y are both binary,
and PXY is given by

Also note that φ(PX Y ) = i implies
H(Y |X) < R − Ri ,
i.e., once x is recovered correctly, y can be sent without an
error. Thus, the error probability of this kind is upper bounded
by
X
exp{−nD(PX Y kPXY )}
∈Pn (X ×Y)
P
XY
φ(P
)≥1
XY

X
P
X̂|X Y
H(X̂4Y )≤H(X4Y )

≤

X
P
∈Pn (X ×Y)
XY
φ(P
)≥1
XY

1
,
3
that is, X and Y are connected by a Z-channel. To evaluate Esp (R), without loss of generality, we can assume that
QX Y (0, 1) = 0 (since otherwise D(QX Y kPXY ) = ∞). Let
us consider the following parametrization:
PXY (0, 0) = PXY (1, 0) = PXY (1, 1) =

QX Y (0, 0) = u, QX Y (1, 0) = 1 − u − v, QX Y (1, 1) = v,

Nh (X X̂ Y )
|TXn Y |

where 0 ≤ u, v ≤ 1. Then, we have
D(QX Y kPXY ) = log 3 − H({u, 1 − u − v, v})
X

exp{−nD(PX Y kPXY )}

and

P

H(X|Y ) + H(Y |X)

X̂|X Y
H(X̂4Y )≤H(X4Y )

= κ(u, v)

+

exp{−n|Rφ(PX̂Y ) − H(X̂|X Y ) − δn | }
X
≤
exp{−nD(PX Y kPXY )}
∈Pn (X ×Y)
P
XY
φ(P
)≥1
XY

P
X̂|X Y
H(X̂4Y )≤H(X4Y )

exp{−n|R − H(Y |X̂) − H(X̂|Y ) − ∆ − δn |+ }
X
X
=
exp{−nD(PX Y kPXY )}

P
X̂|X Y
H(X̂4Y )≤H(X4Y )

exp{−n|R − H(X̂4Y ) − ∆ − δn |+ }
X
≤
exp{−nD(PX Y kPXY )}
P
∈Pn (X ×Y)
XY
)≥1
φ(P
XY

X
P
X̂|X Y
H(X̂4Y )≤H(X4Y )

exp{−n|R − H(X4Y ) − ∆ − δn |+ }
X
2
≤
exp{−nD(PX Y kPXY )}(n + 1)|X | |Y|
P
∈Pn (X ×Y)
XY
φ(P
)≥1
XY

+

exp{−n|R − H(X4Y ) − ∆ − δn | }.
Thus, by combining this with (14), the total error probability
is upper bounded by
(n + 1)|X |

2

|Y|+|X ||Y|

exp{−n min [D(PX Y kPXY )
PX Y

+ |R − H(X4Y ) − ∆ − δn |+ ]}.
Since ∆ can be taken arbitrarily small, and the number of
bits needed to send ACK-NACK is at most r.11 Consequently,
Protocol 2 attains the exponent given in Result 6.

11 Our

:= (1 − v)h

P

exp{−n|R − H(Y |X̂) − H(X̂|X Y ) − ∆ − δn |+ }
X
X
≤
exp{−nD(PX Y kPXY )}

P
∈Pn (X ×Y)
XY
)≥1
φ(P
XY



X

X̂|X Y
H(X̂4Y )≤H(X4Y )

P
∈Pn (X ×Y)
XY
)≥1
φ(P
XY

(15)

type-based protocol uses only constant number of rounds of interaction (independent of n).

u
1−v




+ (1 − u)h

v
1−u


.

When the rate R is sufficiently close to H(X4Y ) =
κ(1/3, 1/3) = 4/3, the set Q(R) is not empty.12 Since (15)
and κ(u, v) are both symmetric with respect to u and v and
(15) and Q(R) are convex function and convex set, respectively, the optimal solution (u∗ , v ∗ ) in the infimum of Esp (R)
satisfies u∗ = v ∗ . Furthermore, since R > κ(1/3, 1/3), we
also have u∗ = v ∗ 6= 1/3.
Note that for R sufficiently close to H(X4Y ), Esp (R)
can be shown to equal Er (R). Thus, to show that a simple
communication is strictly suboptimal for error exponent, it
s
(R), where the latter
suffices to show that Esp (R) > Esp
s
quantity Esp (R) corresponds to the sphere packing bound for
error exponent using simple communication and is given by
s
Esp
(R) :=

max

inf

(R1 ,R2 ): QX Y ∈Qs (R1 ,R2 )
R1 +R2 ≤R

D(QX Y kPXY )

and

Qs (R1 , R2 ) := QX Y : R1 < H(X|Y ) or R2 < H(Y |X) .
Since the source is symmetric with respect to X and Y , for
s
evaluating Esp
(R) we can assume without loss of generality
†
v†
1
that R1 ≥ R2 . Let u† := u∗ and v † := 1−u
so that 1−u
† = 2.
2
†
Let QX
be the distribution that corresponds to (u† , v † ). Note
Y
†
that QX Y satisfies


v†
†
H(Y |X) = (1 − u )h
1 − u†


v∗
∗
> (1 − u )h
1 − u∗
R
≥
2
12 In

fact, we can check that

κ(z,z)
dz
z=1/3

= −1, and thus the function

κ(z, z) takes its maximum away from (1/3, 1/3).

13

s
which implies Esp (R) > Esp
(R).

≥ R2 ,
and so, Q†X Y ∈ Qs (R1 , R2 ). For this choice of Q†X Y , we
have
D(Q∗X Y

∗

∗

∗

∗

kPXY ) = log 3 − H({u , 1 − u − v , v })


v∗
∗
∗
= log 3 − h(1 − u ) − (1 − u )h
1 − u∗


v†
†
†
> log 3 − h(1 − u ) − (1 − u )h
1 − u†
= D(Q†X Y kPXY ),

[4] M. Braverman and A. Rao, “Information equals amortized communication,” in FOCS, 2011, pp. 748–757.
[5] T. M. Cover and J. A. Thomas, Elements of Information Theory. 2nd
edition. John Wiley & Sons Inc., 2006.
[6] I. Csiszár, “Linear codes for sources and source networks: Error exponents, universal coding,” IEEE Trans. Inf. Theory, vol. 28, no. 4, pp.
585–592, July 1982.
[7] I. Csiszár and J. Körner, Information theory: Coding theorems for
discrete memoryless channels. 2nd edition. Cambridge University Press,
2011.
[8] I. Csiszár and P. Narayan, “Secrecy capacities for multiple terminals,”
IEEE Trans. Inf. Theory, vol. 50, no. 12, pp. 3047–3061, December
2004.
[9] S. C. Draper, “Universal incremental slepian-wolf coding,” Proc. Conference on Communication, Control, and Computing (Allerton), October
2004.
[10] M. Feder and N. Shulman, “Source broadcasting with unknown amount
of receiver side information,” in ITW, Oct 2002, pp. 127–130.
[11] W. Feller, An Introduction to Probability Theory and its Applications,
Volume II. 2nd edition. John Wiley & Sons Inc., UK, 1971.
[12] P. Gács and J. Körner, “Common information is far less than mutual
information,” Problems of Control and Information Theory, vol. 2, no. 2,
pp. 149–162, 1973.
[13] T. S. Han, Information-Spectrum Methods in Information Theory [English Translation]. Springer, 2003.
[14] T. S. Han and S. Verdú, “Approximation theory of output statistics,”
IEEE Trans. Inf. Theory, vol. 39, no. 3, pp. 752–772, May 1993.
[15] M. Hayashi, “Second-order asymptotics in fixed-length source coding
and intrinsic randomness,” IEEE Trans. Inf. Theory, vol. 54, no. 10, pp.
4619–4637, Oct 2008.
[16] M. Hayashi, H. Tyagi, and S. Watanabe, “Secret key agreement: General
capacity and second-order asymptotics,” arXiv:1411.0735, 2014.
[17] ——, “Secret key agreement: General capacity and second-order asymptotics,” ISIT, 2014.
[18] M. Hayashi, “Information spectrum approach to second-order coding
rate in channel coding,” IEEE Trans. Inf. Theory, vol. 55, no. 11, pp.
4947–4966, Novemeber 2009.
[19] R. Impagliazzo, L. A. Levin, and M. Luby, “Pseudo-random generation from one-way functions,” Proc. Annual Symposium on Theory of
Computing, pp. 12–24, 1989.
[20] E. Kushilevitz and N. Nisan, Communication Complexity. New York,
NY, USA: Cambridge University Press, 1997.
[21] U. M. Maurer, “Secret key agreement by public discussion from common
information,” IEEE Trans. Inf. Theory, vol. 39, no. 3, pp. 733–742, May
1993.
[22] S. Miyake and F. Kanaya, “Coding theorems on correlated general
sources,” IIEICE Trans. Fundamental, vol. E78-A, no. 9, pp. 1063–
1070, September 1995.

R EFERENCES
[1] R. Ahlswede and I. Csiszár, “Common randomness in information theory
and cryptography–part i: Secret sharing,” IEEE Trans. Inf. Theory,
vol. 39, no. 4, pp. 1121–1132, July 1993.
[2] Y. Altuğ and A. B. Wagner, “Feedback can improve the second-order
coding performance in discrete memoryless channels,” ISIT, 2014.
[3] C. H. Bennett, G. Brassard, C. Crépeau, and U. M. Maurer, “Generalized
privacy amplification,” IEEE Trans. Inf. Theory, vol. 41, no. 6, pp. 1915–
1923, November 1995.
[23] A. Orlitsky and A. El Gamal, “Communication with secrecy constraints,”
STOC, pp. 217–224, 1984.
[24] A. Orlitsky, “Worst-case interactive communication i: Two messages are
almost optimal,” IEEE Trans. Inf. Theory, vol. 36, no. 5, pp. 1111–1126,
1990.
[25] Y. Polyanskiy, “Channel coding: non-asymptotic fundamental limits,”
Ph. D. Dissertation, Princeton University, 2010.
[26] Y. Polyanskiy, H. V. Poor, and S. Verdú, “Channel coding rate in the
finite blocklength regime,” IEEE Trans. Inf. Theory, vol. 56, no. 5, pp.
2307–2359, May 2010.
[27] R. Renner, “Security of quantum key distribution,” Ph. D. Dissertation,
ETH Zurich, 2005.
[28] R. Renner and S. Wolf, “Simple and tight bounds for information
reconciliation and privacy amplification,” in ASIACRYPT, 2005, pp. 199–
216.
[29] D. Slepian and J. Wolf, “Noiseless coding of correlated information
source,” IEEE Trans. Inf. Theory, vol. 19, no. 4, pp. 471–480, July
1973.
[30] V. Strassen, “Asymptotische abschätzungen in Shannon’s informationstheorie,” Third Prague Conf. Inf. Theory, pp. 689–723, 1962, English
translation: http://www.math.cornell.edu/∼pmlut/strassen.pdf.
[31] V. Y. F. Tan and O. Kosut, “On the dispersions of three network
information theory problems,” IEEE Trans. Inf. Theory, vol. 60, no. 2,
pp. 881–903, 2014.
[32] H. Tyagi, “Common randomness principles of secrecy,” Ph. D. Dissertation, Univeristy of Maryland, College Park, 2013.
[33] H. Tyagi, S. Venkatakrishnan, P. Viswanath, and S. Watanabe, “Information complexity density and simulation of protocols,” Proc. ACM
Conference on Innovations in Theoretical Computer Science (ITCS), pp.
381–391, 2016.
[34] ——, “Information complexity density and simulation of protocols,”
IEEE Trans. Inf. Theory, vol. 63, no. 11, pp. 6979–7002, Nov 2017.
[35] H. Tyagi and S. Watanabe, “A bound for multiparty secret key agreement
and implications for a problem of secure computing,” in EUROCRYPT,
2014, pp. 369–386.
[36] ——, “Converses for secret key agreement and secure computing,” IEEE
Trans. Inf. Theory, vol. 61, no. 9, pp. 4809–4827, Sept 2015.
[37] H. S. Witsenhausen, “On sequences of pairs of dependent random
variables,” Siam J. Appl. Math., vol. 28, no. 1, pp. 100–113, January
1975.
[38] E.-H. Yang and D.-K. He, “Interactive encoding and decoding for
one way learning: Near lossless recovery with side information at the
decoder,” Information Theory, IEEE Transactions on, vol. 56, no. 4, pp.
1808–1824, April 2010.
[39] E.-H. Yang, D.-K. He, T. Uyematsu, and R. W. Yeung, “Universal multiterminal source coding algorithms with asymptotically zero feedback:
fixed database case,” Information Theory, IEEE Transactions on, vol. 54,
no. 12, pp. 5575–5590, Dec. 2008.

