$\displaystyle\prod_{i=2}^{C}\frac{t_{D(m^{\prime})_{i}}(m^{\prime}_{i})}{p^{\prime}(m^{\prime}_{i}|xyD(m^{\prime})_{\leq
i})}$
$\displaystyle=\prod_{i=2}^{C}\frac{t_{D(m^{\prime})_{i}}(m^{\prime}_{i})}{\mathop{\mathbb{E}\/}_{p^{\prime}(m_{i}|xyD(m^{\prime})_{\leq
i})}[p^{\prime}(m^{\prime}_{i}|xyD(m^{\prime})_{\leq i},m_{i})]}$
$\displaystyle=\prod_{i=2}^{C}\frac{t_{D(m^{\prime})_{i}}(m^{\prime}_{i})}{\mathop{\mathbb{E}\/}_{p^{\prime}(m_{i}|xyD(m^{\prime})_{\leq
i})}[s_{m_{i}}(m^{\prime}_{i}|D(m^{\prime}_{i}))]}$
$\displaystyle=\prod_{i=2}^{C}\frac{t_{D(m^{\prime})_{i}}(m^{\prime}_{i})}{p^{\prime}(m_{i}=D(m^{\prime})_{i})\cdot
t_{D(m^{\prime})_{i}}(m^{\prime}_{i})+p^{\prime}(m_{i}\neq
D(m^{\prime})_{i})\cdot t^{\prime}_{D(m^{\prime})_{i}}(m^{\prime}_{i})}$
$\displaystyle=\prod_{i=2}^{C}\frac{1}{p^{\prime}(m_{i}=D(m^{\prime})_{i})+p^{\prime}(m_{i}\neq
D(m^{\prime})_{i})\cdot\frac{t^{\prime}_{D(m^{\prime})_{i}}(m^{\prime}_{i})}{t_{D(m^{\prime})_{i}}(m^{\prime}_{i})}}$
$\displaystyle\leq\prod_{i=2}^{C}\frac{1}{p^{\prime}(m_{i}=D(m^{\prime})_{i})}$
$\displaystyle\leq\prod_{i=2}^{C}\frac{1}{1-\exp(-\Omega(\beta^{2}L))}.$

So, we obtain the bound:

$\displaystyle\frac{q^{\prime}(xym^{\prime})}{p^{\prime}(xym^{\prime})}=\frac{q(xyD(m^{\prime}))}{p(xyD(m^{\prime}))}\cdot(1+2C\exp(-\Omega(\beta^{2}L))).$

Moreover, for all $xym^{\prime}$ in the support of $q^{\prime}$, we have

$\displaystyle q^{\prime}(xy|m^{\prime})$
$\displaystyle=\frac{q^{\prime}(xym^{\prime})}{q^{\prime}(m^{\prime})}$
$\displaystyle=\frac{q(xyD(m^{\prime}))\cdot\prod_{i=1}^{C}t_{D(m^{\prime})_{i}}(m^{\prime}_{i})}{q(D(m^{\prime}))\cdot\prod_{i=1}^{C}t_{D(m^{\prime})_{i}}(m^{\prime}_{i})}$
$\displaystyle=q(xy|D(m^{\prime})).$

Finally, since $q^{\prime}(xy|m^{\prime})=q(xy|D(m^{\prime}))$, we have

$\displaystyle\Big{|}\mathop{\mathbb{E}\/}_{q^{\prime}(xy|m^{\prime})}[(-1)^{f}]\Big{|}$
$\displaystyle=|\mathop{\mathbb{E}\/}_{q^{\prime}(xy|D(m^{\prime}))}[(-1)^{f}]\Big{|}.$

Thus, we get that

$\mathsf{M}^{\mathsf{ext}}_{I}(p^{\prime},f)\leq\mathsf{M}^{\mathsf{ext}}_{I}(p,f)+IC\cdot\exp(-\Omega(\beta^{2}L)).$

Setting $L=O(\log(IC)/\beta^{2})$ proves the theorem. ∎

Smooth protocols have the feature that the log-ratios of the information terms
are tightly concentrated. To explain this phenomenon, we need to introduce a
few definitions. For every $xym$ in the support of $p$, and $j\geq 2$, define
the $j$-th divergence costs:

$\displaystyle d^{A}_{j}(xm)$ $\displaystyle=\sum_{\begin{subarray}{c}2\leq
i\leq j\\\ i\text{
odd}\end{subarray}}\mathop{\mathbb{E}\/}_{p(m_{i}|xm_{<i})}\Big{[}\log\frac{p(m_{i}|xm_{<i})}{p(m_{i}|m_{<i})}\Big{]},$
$\displaystyle d^{B}_{j}(ym)$ $\displaystyle=\sum_{\begin{subarray}{c}2\leq
i\leq j\\\ i\text{
even}\end{subarray}}\mathop{\mathbb{E}\/}_{p(m_{i}|ym_{<i})}\Big{[}\log\frac{p(m_{i}|ym_{<i})}{p(m_{i}|m_{<i})}\Big{]},$
$\displaystyle d_{j}(xym)$ $\displaystyle=d^{A}_{j}(xm)+d^{B}_{j}(ym).$

By the non-negativity of divergence, the divergence costs are monotone i.e.
$d_{j}(xym)\leq d_{j+1}(xym)$. Since the protocol is $\beta$-smooth, we have

$\displaystyle d_{j+1}^{A}(xm)-d_{j}^{A}(xm)$
$\displaystyle\leq\log\frac{1/2+\beta}{1/2-\beta}\leq 5\beta,$ $\displaystyle
d_{j+1}^{B}(ym)-d_{j}^{B}(ym)$
$\displaystyle\leq\log\frac{1/2+\beta}{1/2-\beta}\leq 5\beta.$ (76)

We say a function $r(xym)$ taking values in $\\{1,\ldots,C\\}$ is a _frontier_
if every $m$ contains exactly one prefix of the type $m^{\prime}_{\leq
r(xym^{\prime})}$, and that is the prefix $m_{\leq r(xym)}$. Alternatively,
for every $m,m^{\prime}$ such that $r(xym)\neq r(xym^{\prime})$, it holds that
both $r(xym)$ and $r(xym^{\prime})$ are larger than the length of the longest
common prefix of $m$ and $m^{\prime}$. Given a frontier $r(xym)$, define

$\displaystyle F_{r,\alpha}$ $\displaystyle=\Big{\\{}xym:\Big{|}\sum_{i\geq
2}^{r(xym)}\log\frac{p(m_{i}|xym_{<i})}{p(m_{i}|m_{<i})}-d_{r(xym)}(xym)\Big{|}\geq\alpha\Big{\\}},$
$\displaystyle F^{A}_{r,\alpha}$
$\displaystyle=\Big{\\{}xym:\Big{|}\sum_{i\geq 2\text{
odd}}^{r(xym)}\log\frac{p(m_{i}|xym_{<i})}{p(m_{i}|m_{\leq
i})}-d^{A}_{r(xym)}(xm)\Big{|}\geq\alpha\Big{\\}},$ $\displaystyle
F^{B}_{r,\alpha}$ $\displaystyle=\Big{\\{}xym:\Big{|}\sum_{i\geq 2\text{
even}}^{r(xym)}\log\frac{p(m_{i}|xym_{<i})}{p(m_{i}|m_{\leq
i})}-d^{B}_{r(xym)}(ym)\Big{|}\geq\alpha\Big{\\}}.$ (77)

######  Lemma 41.

Let $r(xym)$ be a frontier such that for every $xym$, it holds that
$d_{r(xym)}(xym)\leq\tau$. Then $p(F_{r,\alpha}),p(F^{A}_{r,\alpha})$ and
$p(F^{B}_{r,\alpha})$ are all at most $2\exp(-\Omega(\alpha^{2}/\tau))$.

###### Proof.

We prove the inequality for $p(F_{r,\alpha})$; the proofs for the other two
terms are similar. Define the random variable $z_{0},z_{1}\ldots$ where
$z_{0}=z_{1}=0$ and for every $i\geq 2$,

$\displaystyle
z_{i}=\begin{cases}\log\frac{p(m_{i}|xym_{<i})}{p(m_{i}|m_{<i})}&\text{if
$i\leq r(xym)$}\\\ 0&\text{otherwise.}\end{cases}$

and let $t_{i}=z_{i}-\mathop{\mathbb{E}\/}_{p(m_{i}|xym_{<i})}[z_{i}]$. Then
by definition $\mathop{\mathbb{E}\/}[t_{i}|t_{<i}]=0$. Moreover, we have

$\displaystyle\sup(z_{i}|xym_{<i})$
$\displaystyle\leq\max_{m_{i}}\Big{\\{}\log\frac{p(m_{i}|xym_{<i})}{p(m_{i}|m_{<i})}\Big{\\}}$
$\displaystyle\leq\log\frac{1/2-\beta+\sqrt{d_{i}(xym)-d_{i-1}(xym)}}{1/2-\beta}$
$\displaystyle\leq O(\sqrt{d_{i}(xym)-d_{i-1}(xym)}).$

Similarly,

$\displaystyle\inf(z_{i}|xym_{<i})$
$\displaystyle\geq\log\frac{1/2-\beta}{1/2-\beta-\sqrt{d_{i}(xym)-d_{i-1}(xym)}}$
$\displaystyle\geq-O(\sqrt{d_{i}(xym)-d_{i-1}(xym)}).$

So, if we define $L$ as below, we have

$\displaystyle L$
$\displaystyle=\sup_{xym}\sum_{i=2}^{C}(\sup(t_{i}|xym_{<i})-\inf(t_{i}|xym_{<i}))^{2}$
$\displaystyle=\sup_{xym}\sum_{i=2}^{C}(\sup(z_{i}|xym_{<i})-\inf(z_{i}|xym_{<i}))^{2}$
$\displaystyle\leq O(\tau).$

It is well known that if $\mathop{\mathbb{E}\/}[t_{i}]=0$, then
$\mathop{\mathbb{E}\/}[\exp(t_{i})]\leq\exp((\sup(t_{i})-\inf(t_{i}))^{2}/8)$
(see Lemma 2.6 in [JHM+98]). We can use this inequality to bound:

$\displaystyle\mathop{\mathbb{E}\/}_{p(m|xy)}\Big{[}\exp(\frac{4\alpha}{L}\cdot\sum_{i=2}^{C}t_{i})\Big{]}$
$\displaystyle\leq\mathop{\mathbb{E}\/}_{p(m_{\leq
2}|xy)}\Big{[}\exp(\frac{4\alpha}{L}t_{2})\cdot\mathop{\mathbb{E}\/}_{p(m|xym_{<3})}\Big{[}\exp(\frac{4\alpha}{L}\cdot\sum_{i=3}^{C}t_{i})\Big{]}\Big{]}$
$\displaystyle\leq\dotsc$
$\displaystyle\leq\exp\Big{(}\frac{(4\alpha/L)^{2}\sup_{xym}\sum_{i=2}^{C}(\sup(t_{i}|xym_{<i})-\inf(t_{i}|xym_{<i}))^{2}}{8}\Big{)}$
$\displaystyle\leq\exp\Big{(}2\alpha^{2}/L\Big{)}.$

So by Markov’s inequality, we get:

$\displaystyle
p(\sum_{i=2}^{C}t_{i}>\alpha)\leq\mathop{\mathbb{E}\/}\Big{[}\exp(\frac{4\alpha}{L}\cdot\sum_{i=2}^{C}t_{i})\Big{]}\cdot\exp(-4\alpha^{2}/L)\leq\exp(-\Omega(\alpha^{2}/\tau)).$

Applying the same argument with $t_{i}=-t_{i}$ proves the other inequality.
Defining $z_{i},t_{i}$ appropriately proves the other inequalities using the
same proof. ∎

##  9 Compressing external marginal information

Here we prove Theorem 8. Set
$\mathsf{M}^{\mathsf{ext}}=\mathsf{M}^{\mathsf{ext}}_{I}(p,f)+KI$, for a large
constant $K$ to be chosen later. By Theorem 40, it is no loss of generality to
assume that $p$ is $\beta$-smooth, with
$\beta=1/(K\log(C2^{5\mathsf{M}^{\mathsf{ext}}/I}))$. Let $g_{1},g_{2}$ be as
in Equation 43.

Define:

$\displaystyle r^{A}_{i}(xm)$
$\displaystyle=\begin{cases}\min\\{j:d_{j}^{A}(xm)>20\beta+d^{A}_{i-1}(xm)\\}&\text{if
such $j$ exists,}\\\ C&\text{otherwise.}\end{cases}$ $\displaystyle
r^{B}_{i}(ym)$
$\displaystyle=\begin{cases}\min\\{j:d_{j}^{B}(ym)>20\beta+d^{B}_{i-1}(ym)\\}&\text{if
such $j$ exists,}\\\ C&\text{otherwise.}\end{cases}$

Note that $r_{i}^{A}(xm)$ is always odd, and $r_{i}^{B}(ym)$ is always even.

Because $p$ is a protocol, we have

$\mathop{\mathbb{E}\/}_{p(xy|m)}[d_{j}^{A}(xm)+d_{j}^{B}(ym)]=d_{j}(m).$

Let $\varepsilon$ be a parameter such that $\varepsilon\ll
2^{-5\mathsf{M}^{\mathsf{ext}}/I}$. Now, we describe a protocol $\Gamma$ for
computing $f(xy)$. Throughout this protocol, the parties will maintain a
partial transcript $m_{<i}$. These partial transcripts may be inconsistent
with each other, but we describe the protocol assuming that they are
consistent with each other. In the analysis we shall show that the probability
that the parties end up with inconsistent transcripts is negligible.

  1. 1.

The parties sample $m_{0}$ using the distribution $p(m_{0})$. The parties also
sample a uniformly random function
$h:\mathbb{Z}\rightarrow\\{1,2,\dotsc,\lceil 1/\varepsilon\rceil\\}$.

  2. 2.

Run the protocol $\pi$ from Lemma 24 with
$u=p(m_{1}|m_{0}x),v=p(m_{1}|m_{0}),L=5\mathsf{M}^{\mathsf{ext}}$, error
parameter $\varepsilon$, to obtain functions $a,b$ and transcript $s$. Alice
sets $m^{A}_{1}=a(\pi(us))$, Bob sets $m^{B}_{1}=b(\pi(vs))$. If
$m^{B}_{1}=\bot$, the protocol terminates. Bob sends a bit to Alice to
indicate whether or not this occurs. The communication complexity of this step
is $L+O(\log(1/\varepsilon))$.

  3. 3.

Let $m_{\leq\ell}$ denote the part of the transcript sampled so far. Alice and
Bob repeat the following steps until $m$ corresponds to an entire transcript.

    1. (a)

Both parties use shared randomness to sample a full transcript $\widetilde{m}$
according to $p(m|m_{\leq\ell})$. They exchange the values of
$r^{A}_{\ell+1}(x\widetilde{m})$ and $r^{B}_{\ell+1}(y\widetilde{m})$ to
determine

$k=\min\\{r^{A}_{\ell+1}(x\widetilde{m}),r^{B}_{\ell+1}(y\widetilde{m})\\}.$

    2. (b)

Alice privately samples a number $\zeta^{A}\in[0,1]$ and sends $1$ to Bob if

$\zeta^{A}\leq\frac{1}{2}\cdot\prod_{\begin{subarray}{c}i=\ell+2\\\ i\text{
odd}\end{subarray}}^{k}\frac{p(\widetilde{m}_{i}|x\widetilde{m}_{<i})}{p(\widetilde{m}_{i}|\widetilde{m}_{<i})},$

and otherwise sends $0$.

    3. (c)

Bob privately samples a number $\zeta^{B}\in[0,1]$ and sends $1$ to Alice if

$\zeta^{B}\leq\frac{1}{2}\cdot\prod_{\begin{subarray}{c}i=\ell+2\\\ i\text{
even}\end{subarray}}^{k}\frac{p(\widetilde{m}_{i}|y\widetilde{m}_{<i})}{p(\widetilde{m}_{i}|\widetilde{m}_{<i})},$

and otherwise sends $0$.

    4. (d)

If both players receive $1$ then, set $m_{\leq k}\leftarrow\widetilde{m}_{\leq
k}$.

  4. 4.

If $\eta^{A}\leq g_{1}(xm)\cdot 2^{-\lceil\log g_{1}(xm)\rceil}$, Alice sends
$h(\lceil\log g_{1}(xm)\rceil)$ to Bob, and otherwise she sends $\bot$ to
indicate that the protocol should be aborted.

  5. 5.

If there is a unique integer $z$ such that

$\displaystyle|z+\log g_{2}(ym)|$ $\displaystyle\leq
3\mathsf{M}^{\mathsf{ext}}/I,$ $\displaystyle h(z)$
$\displaystyle=h(\lceil\log g_{1}(xm)\rceil),$ $\displaystyle\eta^{B}$
$\displaystyle\leq g_{2}(ym)\cdot 2^{z-3\mathsf{M}^{\mathsf{ext}}/I},$

Bob sends
$\mathsf{sign}\Big{(}\mathop{\mathbb{E}\/}_{q(xy|m)}[(-1)^{f}]\Big{)}\in\\{\pm
1\\}$ to Alice. Otherwise, he sends $\bot$ to abort the protocol.

To ensure the communication of the protocol is small, in our final protocol
the parties abort and output a random bit if the communication in step 3
exceeds $(\mathsf{M}^{\mathsf{ext}}\cdot
2^{15\mathsf{M}^{\mathsf{ext}}/I}\cdot\log C)/\beta$. Then, the total
communication is at most

$5\mathsf{M}^{\mathsf{ext}}+\frac{\mathsf{M}^{\mathsf{ext}}\cdot
2^{15\mathsf{M}^{\mathsf{ext}}/I}\cdot\log C}{\beta}+O(\log
1/\varepsilon)=O(\mathsf{M}^{\mathsf{ext}}\cdot
2^{15\mathsf{M}^{\mathsf{ext}}/I}\cdot\log^{2}(C\cdot
2^{5\mathsf{M}^{\mathsf{ext}}/I}))\leq\Delta\cdot I\log^{2}C,$

for some $\Delta$ that depends only on $\alpha$ since
$\mathsf{M}^{\mathsf{ext}}\leq(\alpha+K)I$.

Throughout the analysis below, we assume that in step 2, Alice always samples
a message according to $u$, and Bob either accepts this sample or aborts, but
never samples an inconsistent message. We can afford to make this assumption,
because the probability of Bob sampling an inconsistent message without
aborting is bounded by $\varepsilon$, which will be much smaller than our
final advantage. Moreover, if Alice and Bob sample consistently in step 2 then
the transcript they end up with after step 3 must be the same.

Let $S$ and $R$ be the sets defined in Equations 47 and 48 for our choice of
$K$. In addition to $S$ and $R$, we need the following sets to analyze the
simulating protocol:

$\displaystyle Q$ $\displaystyle=\Big{\\{}xym\eta^{A}\eta^{B}:\eta^{A}\leq
g_{1}(xm)\cdot 2^{-\lceil\log g_{1}(xm)\rceil},\eta^{B}\leq g_{2}(ym)\cdot
2^{\lceil\log g_{1}(xm)\rceil-3\mathsf{M}^{\mathsf{ext}}/I}\Big{\\}},$
$\displaystyle\mathcal{Z}$ $\displaystyle=\Big{\\{}xymh:\exists\text{ unique
integer $z$ with }|z+\log
g_{2}(ym)|\leq\frac{3\mathsf{M}^{\mathsf{ext}}}{I}\text{ and
}h(z)=h(\lceil\log g_{1}(xm)\rceil)\Big{\\}}.$

Let $\mathcal{G}$ denote the event that the protocol reaches the final step
without aborting and having communicated at most
$(\mathsf{M}^{\mathsf{ext}}\cdot 2^{15\mathsf{M}^{\mathsf{ext}}/I}\cdot\log
C)/\beta$ bits in step 3. Define $\mathcal{A}(xym)\in\\{\pm 1\\}$ by

$\mathcal{A}(xym)=\mathsf{sign}\Big{(}\mathop{\mathbb{E}\/}_{q(xy|m)}[(-1)^{f(xy)}]\Big{)}\cdot(-1)^{f(xy)}.$

Our protocol computes $f(xy)$ correctly when $\mathcal{G}$ happens and
$\mathcal{A}(xym)=1$. The advantage of the protocol is at least

$\displaystyle\Gamma(\mathcal{Z}QS\mathcal{G})\cdot\mathop{\mathbb{E}\/}_{\Gamma}[\mathcal{A}(xym)|\mathcal{Z}QS\mathcal{G}]-\Gamma(\mathcal{G}(\mathcal{Z}QS)^{c})$
(78)

We shall prove:

$\displaystyle\mathop{\mathbb{E}\/}_{\Gamma}[\mathcal{A}(xym)|\mathcal{Z}QS\mathcal{G}]$
$\displaystyle\geq\Omega(2^{-\delta\mathsf{M}^{\mathsf{ext}}/(12I)}),$ (79)
$\displaystyle\Gamma(\mathcal{Z}QS\mathcal{G})$
$\displaystyle\geq\Omega(2^{-3\mathsf{M}^{\mathsf{ext}}/I}),$ (80)
$\displaystyle\Gamma(\mathcal{G}(\mathcal{Z}QS)^{c})$ $\displaystyle\leq
O(2^{-4\mathsf{M}^{\mathsf{ext}}/I}).$ (81)

By Equation 78, since $\delta\leq 1$, we can choose $K$ to be large enough to
prove the theorem, since $\alpha+K\geq\mathsf{M}^{\mathsf{ext}}/I\geq K$.

We first prove Equation 81. By the union bound, we have:

$\displaystyle\Gamma(\mathcal{G}(\mathcal{Z}QS)^{c})$
$\displaystyle\leq\Gamma(\mathcal{Z}^{c}\mathcal{G})+\Gamma(S^{c}\mathcal{GZ})+\Gamma(Q^{c}\mathcal{GZ}S).$

The definition of the protocol ensures that
$\Gamma(\mathcal{Z}^{c}\mathcal{G})=0$. Moreover,
$\Gamma(Q^{c}\mathcal{GZ}S)=0$, because if the event $\mathcal{Z}S$ happens
and the parties do not abort, then:

$\displaystyle\eta^{A}$ $\displaystyle\leq g_{1}(xm)\cdot 2^{\lceil\log
g_{1}(xm)\rceil}\text{ and}$ $\displaystyle\eta^{B}$ $\displaystyle\leq
g_{2}(ym)\cdot 2^{z-3\mathsf{M}^{\mathsf{ext}}/I}=g_{2}(ym)\cdot 2^{\lceil\log
g_{1}(xm)\rceil-3\mathsf{M}^{\mathsf{ext}}/I}.$

Additionally, $\Gamma(S^{c}\mathcal{GZ})\leq\Gamma(S^{c}\mathcal{Z})\leq
O(\varepsilon\mathsf{M}/I)$, since if $S^{c}\mathcal{Z}$ happens then there
must have been a hash collision, which happens with probability at most
$O(\varepsilon\mathsf{M}/I)$.

In order to prove Equations 79 and 80, we need to first establish that
$\Gamma(xym)$ is typically quite close to $p(xym)$. Indeed, consider a
particular execution of step 3 in the protocol. At this point, some prefix
$m_{\leq\ell}$ has been fixed. For $m$ consistent with this prefix
$m_{\leq\ell}$, define the frontier

$\displaystyle r(xym)$
$\displaystyle=\min\\{r_{\ell+1}^{A}(xm),r_{\ell+1}^{B}(ym)\\}.$

When the parties finally accept a sample, it will be a string $m_{\leq
r(xym)}$ on the frontier. By the definition of
$r_{\ell+1}^{A},r_{\ell+1}^{B}$, and by Equation 76, we have that for all $m$,
$d_{r(xym)}(m)-d_{\ell}(m)\leq 45\beta$. Setting $\tau=45\beta$ and
$\alpha=1/4$, we apply Lemma 41 to conclude that if

$\displaystyle F^{A}$ $\displaystyle=\Big{\\{}xym:\prod_{j=\ell+1\text{
odd}}^{r(xym)}p(m_{j}|xym_{\leq\ell})\geq 2\cdot\prod_{j=\ell+1\text{
odd}}^{r(xym)}p(m_{\leq r(xym)}|m_{\leq\ell})\Big{\\}},$ $\displaystyle F^{B}$
$\displaystyle=\Big{\\{}xym:\prod_{j=\ell+1\text{
even}}^{r(xym)}p(m_{j}|xym_{\leq\ell})\geq 2\cdot\prod_{j=\ell+1\text{
even}}^{r(xym)}p(m_{\leq r(xym)}|m_{\leq\ell})\Big{\\}}.$

then

$\displaystyle p(F^{A}\cup F^{B}|xym_{\leq\ell})\leq
4\exp(-\Omega(1/\beta))\leq C^{-1}\cdot 2^{-5\mathsf{M}^{\mathsf{ext}}/I}.$
(82)

Now, we perform a standard analysis of rejection sampling. Let $W$ denote the
event that the first sample of $m_{r(xym)}$ is accepted in the protocol. Given
$xym_{\leq\ell}$, the probability that $W$ occurs is

$\displaystyle\Gamma(W|xym_{\leq\ell})$
$\displaystyle\geq\sum_{m^{\prime}_{r(xym^{\prime})}:xym^{\prime}_{r(xym)}\notin
F^{A}\cup F^{B}}p(m^{\prime}_{\leq r(xym^{\prime})}|xym_{\leq\ell})/4$
$\displaystyle\geq 1/4-p(F^{A}\cup F^{B}|xym_{\leq\ell})/4\geq 1/4-C^{-1}\cdot
2^{-5\mathsf{M}^{\mathsf{ext}}/I}\geq 1/8,$ (83)

where here we abused notation to write $xym^{\prime}_{r(xym)}\notin F^{A}\cup
F^{B}$ to mean that the prefix is not consistent with any $m$ in $F^{A}\cup
F^{B}$.

It is clear that the sampled point is independent of the event $\neg W$, so it
is also independent of $W$. So, the probability that a particular prefix
$m_{r(xym)}$ is sampled is the same as the probability that it is sampled
conditioned on $W$. When $m_{r(xym)}$ is not consistent with $F^{A}\cup
F^{B}$, the probability of such a point is

$\displaystyle\frac{p(m_{\leq r(xym)}|xym_{\leq\ell})/4}{1/4-p(F^{A}\cup
F^{B}|xym_{\leq\ell})/4}=p(m_{\leq r(xym)}|xym_{\leq\ell})\cdot(1\pm
O(C^{-1}\cdot 2^{-5\mathsf{M}^{\mathsf{ext}}/I})).$ (84)

Let $B$ denote the event that the final sample $xym$ is such that at some
point a prefix was sampled in $F^{A}\cup F^{B}$ during step 3. Whenever step 3
accepts a sample, the length of the transcript increases by at least $1$, so
the number of times step 3 accepts a sample is at most $C$. Thus, by the union
bound and Equation 82,

$\displaystyle p(B)\leq O(2^{-5\mathsf{M}^{\mathsf{ext}}/I}).$ (85)

Moreover, by Equation 84, for $xym\notin B$,

$\displaystyle\Gamma(xym)=p(xym)\cdot(1\pm
O(2^{-5\mathsf{M}^{\mathsf{ext}}/I})).$ (86)

Equations 85 and 86 imply

$\displaystyle\Gamma(B)=1-\Gamma(B^{c})\leq
1-p(B^{c})\cdot(1-O(2^{-5\mathsf{M}^{\mathsf{ext}}/I}))\leq
O(2^{-5\mathsf{M}^{\mathsf{ext}}/I}).$ (87)

Additionally, we have

$\displaystyle q(SB^{c})=q(S)-q(BS)\geq
q(S)-2^{3\mathsf{M}^{\mathsf{ext}}/I}\cdot p(B)\geq
1-\Omega(2^{-\mathsf{M}/I}),$ (88)

by the definition of $S$, 33 and 85.

Now we can begin to understand $\Gamma(\mathcal{Z}QS\mathcal{G})$. For $xym\in
S$,

$\displaystyle\Gamma(Q|xym)=\frac{g_{1}(xm)\cdot 2^{-\lceil\log
g_{1}(xm)\rceil}\cdot g_{2}(ym)\cdot 2^{\lceil\log
g_{1}(xm)\rceil}}{2^{3\mathsf{M}^{\mathsf{ext}}/I}}$
$\displaystyle=\frac{q(xym)}{p(xym)}\cdot\frac{1}{2^{3\mathsf{M}^{\mathsf{ext}}/I}},$
(89)

where the first equality follows from the fact that

$g_{2}(ym)\cdot 2^{\lceil\log g_{1}(xm)\rceil}=2^{\lceil\log
g_{1}(xm)\rceil+\log g_{2}(ym)}\leq 2^{3\mathsf{M}/I},$

by the definition of $S$.

We can bound

$\displaystyle\Gamma(QSB^{c})$ $\displaystyle=\sum_{xym\in S\cap
B^{c}}\Gamma(xym)\cdot\Gamma(Q|xym)$ $\displaystyle=\sum_{xym\in S\cap
B^{c}}p(xym)\cdot\Gamma(Q|xym)\cdot(1\pm
O(2^{-5\mathsf{M}^{\mathsf{ext}}/I})).$ (by Equation 86)
$\displaystyle=2^{-3\mathsf{M}^{\mathsf{ext}}/I}\cdot q(SB^{c})\cdot(1\pm
O(2^{-5\mathsf{M}^{\mathsf{ext}}/I}))$ (90)
$\displaystyle=\Omega(2^{-3\mathsf{M}^{\mathsf{ext}}/I}),$ (91)

by Equations 85 and 88. We claim that for all $xym\in SB^{c}$,

$\displaystyle\Gamma(\mathcal{Z}|xymQSB^{c})=\Gamma(\mathcal{Z}|xym)\geq
1-O(\varepsilon\mathsf{M}^{\mathsf{ext}}/I).$ (92)

The equality follows by observing that $xym$ determine $SB^{c}$, and given
$xym$, $\mathcal{Z}$ just depends on the choice of $h$, which is independent
of $Q$. The inequality follows from the fact that for each $xym$ in $S$, the
event $\mathcal{Z}^{c}$ can happen only if there exists an integer $z$
distinct from $\lceil\log g_{1}(xm)\rceil$ such that $h(\lceil\log
g_{1}(xm)\rceil)=h(z)$ and $\left|z+\log g_{2}(ym)\right|\leq
3\mathsf{M}^{\mathsf{ext}}/I$. The probability that this happens is at most
$O(\varepsilon\cdot\mathsf{M}^{\mathsf{ext}}/I)$. In particular, this implies

$\displaystyle\Gamma(\mathcal{Z}|QS)\geq
1-O(\varepsilon\mathsf{M}^{\mathsf{ext}}/I).$ (93)

For $xym\in S\cap B^{c}$, we have

$\displaystyle\Gamma(xym|\mathcal{Z}QSB^{c})$
$\displaystyle=\frac{\Gamma(xym)\cdot\Gamma(\mathcal{Z}QSB^{c}|xym)}{\Gamma(\mathcal{Z}QSB^{c})}$
$\displaystyle=\frac{p(xym)\cdot\Gamma(Q|xym)\cdot\Gamma(\mathcal{Z}|xym)}{\Gamma(\mathcal{Z}QSB^{c})}\cdot(1\pm
O(2^{-5\mathsf{M}^{\mathsf{ext}}/I}))$ (by Equation 86, and since $xym$
determine $S,B^{c}$)
$\displaystyle=\frac{p(xym)}{\Gamma(QSB^{c})}\cdot\frac{q(xym)}{p(xym)\cdot
2^{3\mathsf{M}^{\mathsf{ext}}/I}}\cdot\frac{\Gamma(\mathcal{Z}|xym)}{\Gamma(\mathcal{Z}|QSB^{c})}\cdot(1\pm
O(2^{-5\mathsf{M}^{\mathsf{ext}}/I}))$ (By Equation 89)
$\displaystyle=\frac{q(xym)}{q(SB^{c})}\cdot(1\pm
O(\varepsilon\mathsf{M}^{\mathsf{ext}}/I+2^{-5\mathsf{M}^{\mathsf{ext}}/I})).$
(By Equations 92 and 90) $\displaystyle=q(xym|SB^{c})\cdot(1\pm
O(\varepsilon\mathsf{M}^{\mathsf{ext}}/I+2^{-5\mathsf{M}^{\mathsf{ext}}/I})).$
(94)

To argue that the protocol does not have too much communication, we show that
typically the divergence costs of the accepted transcripts are small. Define
the sets

$\displaystyle H$
$\displaystyle=\\{xym:\log\frac{p(m|xy)}{p(m)}\leq\mathsf{M}^{\mathsf{ext}}\cdot
2^{10\mathsf{M}^{\mathsf{ext}}/I}\\},$ $\displaystyle F$
$\displaystyle=\\{xym:d_{C}(xym)>2\mathsf{M}^{\mathsf{ext}}\cdot
2^{10\mathsf{M}^{\mathsf{ext}}/I}\\}$

and the frontier

$\displaystyle r(xym)$
$\displaystyle=\begin{cases}\min\\{i:d_{i}(xym)>2\mathsf{M}^{\mathsf{ext}}\cdot
2^{10\mathsf{M}^{\mathsf{ext}}/I}\\}&\text{if such $i$ exists,}\\\
C&\text{otherwise.}\end{cases}$

We have $F\cap H\subseteq F_{r,\mathsf{M}^{\mathsf{ext}}\cdot
2^{10\mathsf{M}^{\mathsf{ext}}/I}}$, where
$F_{r,\mathsf{M}^{\mathsf{ext}}\cdot 2^{10\mathsf{M}^{\mathsf{ext}}/I}}$ is
the set from Equation 77. By Equation 76, and the the choice of $r$,
$d_{r(xym)}(xym)\leq 2\mathsf{M}^{\mathsf{ext}}\cdot
2^{10\mathsf{M}^{\mathsf{ext}}/I}+5\beta$, so we can apply Lemma 41 to
conclude that

$\displaystyle p(FH)\leq p(F_{r,\mathsf{M}^{\mathsf{ext}}\cdot
2^{10\mathsf{M}^{\mathsf{ext}}/I}})\leq
2\exp(-\Omega(\mathsf{M}^{\mathsf{ext}}\cdot
2^{10\mathsf{M}^{\mathsf{ext}}/I})).$ (95)

We have

$\displaystyle q(F|SB^{c})$ $\displaystyle\leq\frac{q(FS)}{q(SB^{c})}$
$\displaystyle\leq\frac{q(FHS)+q(H^{c})}{q(SB^{c})}$ $\displaystyle\leq
O(q(FHS)+q(H^{c}))$ (by Equation 88) $\displaystyle\leq
O(q(FHS)+2^{-10\mathsf{M}^{\mathsf{ext}}/I})$ (by Markov’s inequality and
Equation 55) $\displaystyle\leq O(p(FHS)\cdot
2^{3\mathsf{M}^{\mathsf{ext}}/I}+2^{-10\mathsf{M}^{\mathsf{ext}}/I})$ (using
the definition of $S$) $\displaystyle\leq
O(\exp(-\Omega(\mathsf{M}^{\mathsf{ext}}\cdot
2^{10\mathsf{M}^{\mathsf{ext}}/I}))\cdot
2^{3\mathsf{M}^{\mathsf{ext}}/I}+2^{-10\mathsf{M}^{\mathsf{ext}}/I}),$

by Equation 95. Putting this bound back into Equation 94, we get

$\displaystyle\Gamma(F|\mathcal{Z}QSB^{c})$ $\displaystyle\leq
O(2^{-10\mathsf{M}^{\mathsf{ext}}/I})$ (96)

We note that every time step 3 accepts a sample, the divergence cost of the
transcript increases by $20\beta$, and in expectation, the number of rounds of
rejection sampling involved to accept a sample is at most $8$ by Equation 83
and a standard calculation. Moreover, in each round, the players communicate
at most $2+2\log C$ bits to exchange two indices in $\\{1,\ldots,C\\}$. Hence,
given $xy$ and a transcript $m$ the expected communication to sample $m$ is at
most $16\cdot(1+\log C)\cdot d_{C}(xym)/(20\beta)$. Recall that $\mathcal{G}$
occurs when the protocol reaches the final step having communicated at most
$(\mathsf{M}^{\mathsf{ext}}\cdot 2^{15\mathsf{M}^{\mathsf{ext}}/I}\cdot\log
C)/\beta$. Thus, Markov’s inequality implies that

$\displaystyle\Gamma(\mathcal{G}|\mathcal{Z}QSB^{c}F^{c})=1-O(2^{-5\mathsf{M}^{\mathsf{ext}}/I}).$
(97)

So, we can conclude that

$\displaystyle\Gamma(\mathcal{Z}QS\mathcal{G})$
$\displaystyle\geq\Gamma(\mathcal{Z}QSB^{c}F^{c}\cal G)$
$\displaystyle\geq\Gamma(QSB^{c})\cdot\Gamma(\mathcal{Z}|QSB^{c})\cdot\Gamma(F^{c}|\mathcal{Z}QSB^{c})\cdot\Gamma(\mathcal{G}|\mathcal{Z}QSB^{c}F^{c})$
$\displaystyle\geq\Omega(2^{-3\mathsf{M}^{\mathsf{ext}}/I}),$ (by Equations
91, 92, 97 and 96)

proving Equation 80. Observe that by Equations 80, 87 and 96,

$\displaystyle\Gamma(B|\mathcal{Z}QS\mathcal{G})$
$\displaystyle\leq\frac{\Gamma(B)}{\Gamma(\mathcal{Z}QS\mathcal{G})}\leq
O(2^{-2\mathsf{M}^{\mathsf{ext}}/I}),$ (98)
$\displaystyle\Gamma(F|\mathcal{Z}QS\mathcal{G})$
$\displaystyle\leq\frac{\Gamma(F\mathcal{Z}QSB^{c})+\Gamma(B)}{\Gamma(\mathcal{Z}QS\mathcal{G})}\leq
O(2^{-2\mathsf{M}^{\mathsf{ext}}/I}).$ (99)

Moreover, we have

$\displaystyle\mathop{\mathbb{E}\/}_{\Gamma}[\mathcal{A}(xym)|\mathcal{Z}QSB^{c}F^{c}]$
$\displaystyle\leq\Gamma(\mathcal{G}|\mathcal{Z}QSB^{c}F^{c})\cdot\mathop{\mathbb{E}\/}_{\Gamma}[\mathcal{A}(xym)|\mathcal{Z}QS\mathcal{G}B^{c}F^{c}]+\Gamma(\mathcal{G}^{c}|\mathcal{Z}QSB^{c}F^{c})$
$\displaystyle\leq\mathop{\mathbb{E}\/}_{\Gamma}[\mathcal{A}(xym)|\mathcal{Z}QS\mathcal{G}B^{c}F^{c}]+O(2^{-5\mathsf{M}^{\mathsf{ext}}/I}),$
(100)
$\displaystyle\mathop{\mathbb{E}\/}_{\Gamma}[\mathcal{A}(xym)|\mathcal{Z}QSB^{c}]$
$\displaystyle\leq\Gamma(F^{c}|\mathcal{Z}QSB^{c})\cdot\mathop{\mathbb{E}\/}_{\Gamma}[\mathcal{A}(xym)|\mathcal{Z}QSB^{c}F^{c}]+\Gamma(F|\mathcal{Z}QSB^{c})$
$\displaystyle\leq\mathop{\mathbb{E}\/}_{\Gamma}[\mathcal{A}(xym)|\mathcal{Z}QSB^{c}F^{c}]+O(2^{-10\mathsf{M}^{\mathsf{ext}}/I}),$
(101)

by Equation 96.

We are now ready to prove Equation 79. We have

$\displaystyle\mathop{\mathbb{E}\/}_{\Gamma}[\mathcal{A}(xym)|\mathcal{Z}QS\mathcal{G}]$
$\displaystyle\geq\Gamma(B^{c}F^{c}|\mathcal{Z}QS\mathcal{G})\cdot\mathop{\mathbb{E}\/}_{\Gamma}[\mathcal{A}(xym)|\mathcal{Z}QS\mathcal{G}B^{c}F^{c}]-\Gamma(B|\mathcal{Z}QS\mathcal{G})-\Gamma(F|\mathcal{Z}QS\mathcal{G})$
$\displaystyle\geq(1-O(2^{-2\mathsf{M}^{\mathsf{ext}}/I}))\cdot\mathop{\mathbb{E}\/}_{\Gamma}[\mathcal{A}(xym)|\mathcal{Z}QS\mathcal{G}B^{c}F^{c}]-\Omega(2^{-2\mathsf{M}^{\mathsf{ext}}/I})$
(by Equations 99 and 98)
$\displaystyle\geq(1/2)\cdot\mathop{\mathbb{E}\/}_{\Gamma}[\mathcal{A}(xym)|\mathcal{Z}QSB^{c}F^{c}]-\Omega(2^{-5\mathsf{M}^{\mathsf{ext}}/I})-\Omega(2^{-2\mathsf{M}^{\mathsf{ext}}/I})$
(by Equation 100)
$\displaystyle\geq(1/2)\cdot\mathop{\mathbb{E}\/}_{\Gamma}[\mathcal{A}(xym)|\mathcal{Z}QSB^{c}]-\Omega(2^{-10\mathsf{M}^{\mathsf{ext}}/I})-\Omega(2^{-2\mathsf{M}^{\mathsf{ext}}/I})$
(by Equation 101)
$\displaystyle\geq(1/4)\cdot\mathop{\mathbb{E}\/}_{q}[\mathcal{A}(xym)|SB^{c}]-\Omega(2^{-2\mathsf{M}^{\mathsf{ext}}/I})$
(by Equation 94)
$\displaystyle\geq(1/4)\cdot\mathop{\mathbb{E}\/}_{q(xym)}[\mathcal{A}(xym)]-\Omega(2^{-\mathsf{M}^{\mathsf{ext}}/I})$
(by Equation 88)
$\displaystyle=(1/4)\cdot\mathop{\mathbb{E}\/}_{q(xym)}\bigg{[}\mathsf{sign}\bigg{(}\mathop{\mathbb{E}\/}_{q(x^{\prime}y^{\prime}|m)}\Big{[}(-1)^{f}\Big{]}\bigg{)}\cdot(-1)^{f(xy)}\bigg{]}-\Omega(2^{-\mathsf{M}^{\mathsf{ext}}/I})$
$\displaystyle=(1/4)\cdot\mathop{\mathbb{E}\/}_{q(m)}\bigg{[}\bigg{|}\mathop{\mathbb{E}\/}_{q(xy|m)}\Big{[}(-1)^{f(xy)}\Big{]}\bigg{|}\bigg{]}-\Omega(2^{-\mathsf{M}^{\mathsf{ext}}/I})$
$\displaystyle\geq\Omega(2^{-\delta\mathsf{M}^{\mathsf{ext}}/(12I)}).$ (by
Equation 56)

This concludes the proof of the theorem.

##  10 Compressing bounded-round protocols

We prove the Theorem 10 in this section. Let $p(xym)$ be a protocol
distribution such that $p(xy)=\mu(xy)$. We have $m=(m_{0},\dotsc,m_{r})$,
which is the transcript consisting of $r$ messages along with the shared
randomness. By assumption, $\mathsf{M}_{I}(p,f)=\alpha I$, and
$m_{r}\in\\{0,1\\}$. We assume without loss of generality that $r$ is even.
Let $q(xym)$ be a rectangular distribution that realizes
$\mathsf{M}_{I}(p,f)$. For a large constant $K$, let
$\mathsf{M}=\mathsf{M}_{I}(p,f)+KI$. Since $\mathsf{M}(p,f)\geq 0$, we have
$\mathsf{M}\geq KI$. Let $g_{1},g_{2}$ be as in Equation 43. Let $\varepsilon$
be a parameter such that $\varepsilon=(2^{4\mathsf{M}/I}\cdot(r+1))^{-1}$.

We define a protocol $\Gamma$ whose communication complexity is bounded by

$O(r\cdot(\mathsf{M}+\log(r/\varepsilon))).$

Since $\mathsf{M}_{I}(p,f)=\alpha I$ we get that
$\mathsf{M}\leq(\alpha+K)\cdot I$, and it follows that the communication is
bounded by $\Delta r(I+\log r)$ for some $\Delta$ that only depends on
$\alpha$. Now, we describe $\Gamma$.

  1. 1.

Jointly sample $p(m_{0})$. Alice sets $m^{A}_{0}=m_{0}$ and Bob sets
$m^{B}_{0}=m_{0}$. Jointly sample $\eta^{A}_{0},\eta^{A}_{1},\eta^{B}\in[0,1]$
uniformly and independently. Jointly sample a uniformly random function
$h:\mathbb{Z}\to\\{1,\ldots,\lceil 1/\varepsilon\rceil\\}$.

  2. 2.

For each $i\in\\{1,\ldots,r-1\\}:$

    1. (a)

If $i$ is odd, run the protocol $\pi$ from Lemma 24 with
$u=p(m_{i}|m^{A}_{<i}x)$, $v=p(m_{i}|m^{B}_{<i}y)$,
$L=14\mathsf{M}+5\log(r+1)$ and error parameter $\varepsilon$, to obtain
functions $a_{i},b_{i}$ and transcript $s$. Alice sets $m^{A}_{i}=a_{i}(us)$,
Bob sets $m^{B}_{i}=b_{i}(vs)$. If $m^{B}_{i}=\bot$, Bob signals to abort in
the next round and sends a random bit to Alice, which they both output.

    2. (b)

If $i$ is even, run the protocol $\pi$ from Lemma 24 with
$u=p(m_{i}|m^{B}_{<i}y)$, $v=p(m_{i}|m^{A}_{<i}x)$,
$L=14\mathsf{M}+5\log(r+1)$ and error parameter $\varepsilon$, to obtain
functions $a_{i},b_{i}$ and transcript $s$. Bob sets $m^{B}_{i}=a_{i}(us)$,
Alice sets $m^{A}_{i}=b_{i}(vs)$. If $m^{A}_{i}=\bot$, Alice signals to abort
in the next round and sends a random bit to Bob, which they both output.

Let $\langle m^{A}\rangle,\langle m^{B}\rangle$ denote the values of $m^{A}$
and $m^{B}$ after the first $r-1$ rounds.

  3. 3.

For each $b\in\\{0,1\\}$, Alice sends a message to Bob. If
$\eta^{A}_{b}\leq\log g_{1}(x\langle m^{A}\rangle b)\cdot 2^{-\lceil\log
g_{1}(x\langle m^{A}\rangle b)\rceil}$, Alice sends $h(\lceil\log
g_{1}(x\langle m^{A}\rangle b)\rceil)$ to Bob, otherwise she sends $0$.

  4. 4.

Bob samples a bit $b$ according to $p(m_{r}|\langle m^{B}\rangle y)$. If there
is a unique integer $z$ such that

$\displaystyle|z+\log g_{2}(y\langle m^{B}\rangle b)|$ $\displaystyle\leq
3\mathsf{M}/I,$ $\displaystyle h(z)$ $\displaystyle=h(\lceil\log
g_{1}(x\langle m^{A}\rangle b)\rceil),$ $\displaystyle\eta^{B}$
$\displaystyle\leq g_{2}(y\langle m^{B}\rangle b)\cdot 2^{z-3\mathsf{M}/I},$

Bob sends $\mathsf{sign}\Big{(}\mathop{\mathbb{E}\/}_{q(xy|\langle
m^{B}\rangle b)}[(-1)^{f}]\Big{)}\in\\{\pm 1\\}$ to Alice. Otherwise, he sends
$\bot$ to abort the protocol.

We note that the above protocol involves at most $r$ rounds of communication,
and in each of the first $r-1$ rounds, the communication from step 2 is at
most

$14\mathsf{M}+5\log(r+1)+O(\log 1/\varepsilon)\leq
O(\mathsf{M}+\log(r/\varepsilon)).$

In step 3, Alice additionally sends $O(\log 1/\varepsilon)$ bits for the
hashes. Hence, the total communication is at most
$O(r\cdot(\mathsf{M}+\log(r/\varepsilon)))$.

We may assume that at the beginning of $\Gamma$, the players sample $r$
independent random tapes, where the $i$-th random tape is used for the $i$-th
execution of the protocol $\pi$ from Lemma 24 in step 2 of $\Gamma$. Given
this assumption, define $m$ as follows: $m_{0}=m^{A}_{0}=m^{B}_{0}$, and for
all $i\geq 1$, $m_{i}=a_{i}(p(m_{i}|m_{<i}xy)s)$, where $s$ is a transcript of
the protocol $\pi$ from Lemma 24 that is determined given $x,y,m_{<i}$ and the
$i$-th random tape, and $a_{i}$ is the function promised by the lemma. From
item 1 of Lemma 24, it is clear that $\Gamma(xym)=p(xym)$.

Let $S$ be the set defined in Equation 44 for our choice of $K$. In addition
to $S$, we need the following sets to analyze the simulating protocol.

$\displaystyle Q$
$\displaystyle=\Big{\\{}xym\eta^{A}_{m_{r}}\eta^{B}:\eta^{A}_{m_{r}}\leq
g_{1}(xm)\cdot 2^{-\lceil\log g_{1}(xm)\rceil},\eta^{B}\leq g_{2}(ym)\cdot
2^{\lceil\log g_{1}(xm)\rceil-3\mathsf{M}/I}\Big{\\}},$
$\displaystyle\mathcal{E}$ $\displaystyle=\\{\langle m^{A}\rangle\langle
m^{B}\rangle m_{<r}:\langle m^{A}\rangle=\langle m^{B}\rangle=m_{<r}\\},$
$\displaystyle\mathcal{Z}$ $\displaystyle=\\{xymh:\exists\text{ a unique
integer $z$ with }|z+\log g_{2}(ym)|\leq 3\mathsf{M}/I\text{ and
}h(z)=h(\lceil\log g_{1}(xm)\rceil)\\}.$

Let $\mathcal{G}$ denote the event that the protocol reaches the final step
without aborting, and define $\mathcal{A}(xym)\in\\{\pm 1\\}$ by

$\mathcal{A}(xym)=\mathsf{sign}\Big{(}\mathop{\mathbb{E}\/}_{q(xy|m)}[(-1)^{f(xy)}]\Big{)}\cdot(-1)^{f(xy)}.$

Our protocol computes $f(xy)$ correctly when: $\mathcal{G}$ happens,
$\mathcal{A}(xym)=1$ and $m_{<r}=\langle m^{B}\rangle$. Since
$\mathcal{EZ}SQ\subseteq\mathcal{G}$, and $\mathcal{E}$ implies
$m_{<r}=\langle m^{B}\rangle$, the advantage of our protocol is at least:

$\displaystyle\Gamma(\mathcal{EZ}SQ)\cdot\mathop{\mathbb{E}\/}_{\Gamma(xym|\mathcal{EZ}SQ)}[\mathcal{A}(xym)]-\Gamma(\mathcal{G}(\mathcal{EZ}SQ)^{c}).$
(102)

We shall prove each of the following bounds:

$\displaystyle\mathop{\mathbb{E}\/}_{\Gamma(xym|\mathcal{EZ}QS)}[\mathcal{A}(xym)]$
$\displaystyle\geq\Omega(2^{-\delta\mathsf{M}/(12I)}),$ (103)
$\displaystyle\Gamma(\mathcal{EZ}QS)$
$\displaystyle\geq\Omega(2^{-3\mathsf{M}/I}),$ (104)
$\displaystyle\Gamma(\mathcal{G}(\mathcal{EZ}SQ)^{c})$ $\displaystyle\leq
O(2^{-4\mathsf{M}/I}).$ (105)

Because $\delta\leq 1$ and $(\alpha+K)\geq\mathsf{M}/I\geq K$, we can choose
$K$ to be large enough to prove the theorem.

We first upper bound $\Gamma(\mathcal{G}(\mathcal{EZ}SQ)^{c})$. By the union
bound, we have:

$\displaystyle\Gamma(\mathcal{G}(\mathcal{EZ}SQ)^{c})$
$\displaystyle\leq\Gamma(\mathcal{G}\mathcal{E}^{c})+\Gamma(\mathcal{Z}^{c}|\mathcal{GE})+\Gamma(S^{c}\mathcal{GEZ})+\Gamma(Q^{c}|\mathcal{GEZ}S).$

The definition of the protocol ensures that
$\Gamma(\mathcal{Z}^{c}|\mathcal{GE})=0$. Moreover, we claim that
$\Gamma(Q^{c}|\mathcal{GEZ}S)=0$, because if the event $\mathcal{EZ}S$ happens
and the parties do not abort, then

$\displaystyle\eta^{A}_{m_{r}}$ $\displaystyle\leq g_{1}(x\langle m^{A}\rangle
m_{r})\cdot 2^{\lceil\log g_{1}(x\langle m^{A}\rangle
m_{r})\rceil}=g_{1}(xm)\cdot 2^{\lceil\log g_{1}(xm)\rceil},$
$\displaystyle\eta^{B}$ $\displaystyle\leq g_{2}(y\langle m^{B}\rangle
m_{r})\cdot 2^{z-3\mathsf{M}/I}=g_{2}(ym)\cdot 2^{\lceil\log
g_{1}(xm)\rceil-3\mathsf{M}/I}.$

The event $\mathcal{G}\mathcal{E}^{c}$ implies that $\pi$ made an error in one
of the $r$ rounds, leaving Alice and Bob with strings that were not equal. The
probability that this happens is at most $\varepsilon\cdot r\leq
2^{-4\mathsf{M}/I}$, by our choice of $\varepsilon$. Finally,
$\Gamma(S^{c}\mathcal{GEZ})\leq\Gamma(S^{c}\mathcal{EZ})\leq
O(\varepsilon\mathsf{M}/I)$, since if $S^{c}\mathcal{EZ}$ happens then there
must have been a hash collision, which happens with probability at most
$O(\varepsilon\mathsf{M}/I)$. This implies Equation 105.

Now, we turn to proving Equation 104. Let us first estimate $\Gamma(QS)$. We
have,

$\displaystyle\Gamma(QS)$ $\displaystyle=\sum_{xym\in
S}\Gamma(xym)\cdot\Gamma(Q|xym)=\sum_{xym\in S}p(xym)\cdot\Gamma(Q|xym).$

For $xym\in S$,

$\displaystyle\Gamma(Q|xym)=\frac{g_{1}(xm)\cdot 2^{-\lceil\log
g_{1}(xm)\rceil}\cdot g_{2}(ym)\cdot 2^{\lceil\log
g_{1}(xm)\rceil}}{2^{3\mathsf{M}/I}}$
$\displaystyle=\frac{q(xym)}{p(xym)}\cdot\frac{1}{2^{3\mathsf{M}/I}},$ (106)

where the first equality follows from the fact that

$g_{2}(ym)\cdot 2^{\lceil\log g_{1}(xm)\rceil}=2^{\lceil\log
g_{1}(xm)\rceil+\log g_{2}(ym)}\leq 2^{3\mathsf{M}/I},$

by the definition of $S$. Therefore,

$\displaystyle\Gamma(QS)=\sum_{xym\in
S}p(xym)\cdot\frac{q(xym)}{p(xym)}\cdot\frac{1}{2^{3\mathsf{M}/I}}$
$\displaystyle=\frac{q(S)}{2^{3\mathsf{M}/I}}$
$\displaystyle\geq\frac{(1-5\cdot
2^{-\mathsf{M}/I})}{2^{3\mathsf{M}/I}}=\Omega(2^{-3\mathsf{M}/I}),$ (107)

where in the last line, we used 33.

We claim that for all $xym\in S$,

$\displaystyle\Gamma(\mathcal{Z}|xymQS)=\Gamma(\mathcal{Z}|xym)\geq
1-O(\varepsilon\mathsf{M}/I).$ (108)

The equality follows by noting that $xym$ determine $S$ and given $xym$,
$\mathcal{Z}$ just depends on the choice of $h$, which is independent of $Q$.
The event $\mathcal{Z}^{c}$ can happen only if there exists an integer $z$
distinct from $\lceil\log g_{1}(xm)\rceil$ such that $h(\lceil
g_{1}(xm)\rceil)=h(z)$ and $\left|z+\log g_{2}(ym)\right|\leq 3\mathsf{M}/I$.
The probability that this happens is at most
$O(\varepsilon\cdot\mathsf{M}/I)$. Therefore, $\Gamma(\mathcal{Z}|xym)\geq
1-O(\varepsilon\mathsf{M}/I)\geq 1/2$, by our choice of $\varepsilon$. We
conclude that

$\displaystyle\Gamma(QS\mathcal{Z})$
$\displaystyle=\Gamma(QS)\cdot\Gamma(\mathcal{Z}|QS)\geq\Omega(2^{-3\mathsf{M}/I}),$
(109)

For all $xym\in S$,

$\displaystyle\Gamma(xym|QS\mathcal{Z})$
$\displaystyle=\frac{\Gamma(xym)\cdot\Gamma(QS\mathcal{Z}|xym)}{\Gamma(QS\mathcal{Z})}$
$\displaystyle=\frac{p(xym)}{\Gamma(QS)}\cdot\Gamma(Q|xym)\cdot\frac{\Gamma(\mathcal{Z}|xymQS)}{\Gamma(\mathcal{Z}|QS)}$
$\displaystyle=\frac{p(xym)}{\Gamma(QS)}\cdot\frac{q(xym)}{p(xym)\cdot
2^{3\mathsf{M}/I}}\cdot\frac{\Gamma(\mathcal{Z}|xymQS)}{\Gamma(\mathcal{Z}|QS)}$
$\displaystyle=\frac{q(xym)}{q(S)}\cdot\frac{\Gamma(\mathcal{Z}|xymQS)}{\Gamma(\mathcal{Z}|QS)}$
(By Section 10) $\displaystyle=q(xym|S)\cdot(1\pm
O(\varepsilon\mathsf{M}/I)),$ (110)

where the last line follows from Equation 108.

Given Equation 109, to complete the proof of Equation 104, it will be enough
to prove that $\Gamma(\mathcal{E}|QS\mathcal{Z})\geq 1/2$. Let $T$ be the set
$T_{K}$ defined in 35 for our choice of $K$. We have

$\displaystyle\Gamma(\mathcal{E}^{c}|QS\mathcal{Z})$
$\displaystyle\leq\Gamma(T^{c}|QSZ)+\Gamma(\mathcal{E}^{c}|QS\mathcal{Z}T)$
$\displaystyle\leq
q(T^{c}|S)\cdot(1+O(\varepsilon\mathsf{M}/I))+\Gamma(\mathcal{E}^{c}|QS\mathcal{Z}T)$
(By Equation 110) $\displaystyle\leq
O(2^{-\mathsf{M}/I})+\Gamma(\mathcal{E}^{c}|QS\mathcal{Z}T)$ (By 35)
$\displaystyle\leq O(2^{-\mathsf{M}/I})+2\varepsilon\cdot r\leq
O(2^{-\mathsf{M}/I})\leq 1/2$ (111)

where in the last line, we used the fact that given $QS\mathcal{Z}T$, item 2
and 3 of Lemma 24 guarantee that $\mathcal{E}^{c}$ can only happen with
probability at most $2\varepsilon$ in each of the $r$ rounds. Equations 111
and 109 together prove Equation 104.

Next, we prove Equation 103. Since $|\mathcal{A}(xym)|\leq 1$, we have

$\displaystyle\mathop{\mathbb{E}\/}_{\Gamma(xym|QS\mathcal{Z})}[\mathcal{A}(xym)]\leq\Gamma(\mathcal{E}|QS\mathcal{Z})\cdot\mathop{\mathbb{E}\/}_{\Gamma(xym|QS\mathcal{ZE})}[\mathcal{A}(xym)]+\Gamma(\mathcal{E}^{c}|QS\mathcal{Z}),$

and since $\Gamma(\mathcal{E}|QS\mathcal{Z})\leq 1$, this gives

$\displaystyle\mathop{\mathbb{E}\/}_{\Gamma(xym|QS\mathcal{ZE})}[\mathcal{A}(xym)]$
$\displaystyle\geq\mathop{\mathbb{E}\/}_{\Gamma(xym|QS\mathcal{Z})}[\mathcal{A}(xym)]-\Gamma(\mathcal{E}^{c}|QS\mathcal{Z})$
$\displaystyle\geq\mathop{\mathbb{E}\/}_{q(xym|S)}[\mathcal{A}(xym)]-\Omega(\varepsilon\mathsf{M}/I+2^{-\mathsf{M}/I})$
(using Equations 111 and 110)
$\displaystyle\geq\mathop{\mathbb{E}\/}_{q(xym)}[\mathcal{A}(xym)]-\Omega(2^{-\mathsf{M}/I})$
(by 33)
$\displaystyle=\mathop{\mathbb{E}\/}_{q(xym)}\bigg{[}\mathsf{sign}\bigg{(}\mathop{\mathbb{E}\/}_{q(x^{\prime}y^{\prime}|m)}\Big{[}(-1)^{f}\Big{]}\bigg{)}\cdot(-1)^{f(xy)}\bigg{]}-\Omega(2^{-\mathsf{M}/I})$
$\displaystyle=\mathop{\mathbb{E}\/}_{q(m)}\bigg{[}\bigg{|}\mathop{\mathbb{E}\/}_{q(xy|m)}\Big{[}(-1)^{f(xy)}\Big{]}\bigg{|}\bigg{]}-\Omega(2^{-\mathsf{M}/I})\geq\Omega(2^{-\delta\mathsf{M}/(12I)}),$

by Equation 53. This completes the proof of Equation 103.

##  11 Compression independent of communication

In this section, we prove Theorem 9. Let $K$ be a sufficiently large constant
to be determined later. Let $p(xym)$ be a protocol distribution such that
$p(xy)=\mu(xy)$ and $\mathsf{M}_{I}(p,f)\leq\alpha I$. Let $q(xym)$ be a
rectangular distribution that realizes $\mathsf{M}_{I}(p,f)$.

Define $\mathsf{M}=\mathsf{M}_{I}(p,f)+KI$. Since $\mathsf{M}(p,f)\geq 0$, we
have $\mathsf{M}\geq KI$. Let $g_{1},g_{2}$ be as in Equation 43. Let
$\varepsilon$ be a parameter such that
$\varepsilon=2^{-6\mathsf{M}/I-8\mathsf{M}}$. We define a protocol $\Gamma$
whose communication complexity is bounded by

$2\log 1/\varepsilon\leq O(6\mathsf{M}/I+8\mathsf{M})=\Delta I,$

for some $\Delta$ that depends only on $\alpha$.

We describe the protocol $\Gamma$.

  1. 1.

Jointly sample $\eta^{A},\eta^{B}\in[0,1]$ uniformly. Jointly sample two
uniformly random functions $h,t:\mathbb{Z}\to\\{1,\ldots,\lceil
1/\varepsilon\rceil\\}$.

  2. 2.

Jointly sample an infinite sequence of triples
$(m^{1},\rho_{A}^{1},\rho_{B}^{1}),(m^{2},\rho_{A}^{2},\rho_{B}^{2}),\ldots,$
where $m^{i}$ is sampled uniformly at random from the set of all transcripts
and $\rho_{A}^{i},\rho_{B}^{i}$ are sampled uniformly at random in $[0,1]$.

  3. 3.

Alice finds the first index $i_{A}$ such that

$\displaystyle\rho_{A}^{i_{A}}$ $\displaystyle\leq\prod_{j\text{
odd}}p(m^{i_{A}}_{j}|xm^{i_{A}}_{<j}),$ $\displaystyle\rho_{B}^{i_{A}}$
$\displaystyle\leq 2^{6\mathsf{M}}\cdot\prod_{j\text{
even}}p(m^{i_{A}}_{j}|xm^{i_{A}}_{<j}).$

Alice checks if $\eta^{A}\leq g_{1}(xm^{i_{A}})\cdot 2^{\lceil\log
g_{1}(xm^{i_{A}})\rceil}$, in which case she sends $t(i_{A})$ and
$h(\lceil\log g_{1}(xm^{i_{A}})\rceil)$ to Bob. Otherwise, she sends $\bot$
signaling to abort.

  4. 4.

Bob finds the first index $i_{B}$ such that

$\displaystyle\rho_{A}^{i_{B}}$ $\displaystyle\leq
2^{6\mathsf{M}}\cdot\prod_{j\text{ odd}}p(m^{i_{B}}_{j}|ym^{i_{B}}_{<j}),$
$\displaystyle\rho_{B}^{i_{B}}$ $\displaystyle\leq\prod_{j\text{
even}}p(m^{i_{B}}_{j}|ym^{i_{B}}_{<j}).$

If $t(i_{B})=t(i_{A})$, he checks if there is a unique integer $z$ such that

$\displaystyle|z+\log g_{2}(ym^{i_{B}})|$ $\displaystyle\leq 3\mathsf{M}/I,$
$\displaystyle h(z)$ $\displaystyle=h(\lceil\log g_{1}(xm^{i_{A}})\rceil),$
$\displaystyle\eta^{B}$ $\displaystyle\leq g_{2}(ym^{i_{B}})\cdot
2^{z-3\mathsf{M}/I},$

If all these conditions are satisfied, he sends
$\mathsf{sign}\Big{(}\mathop{\mathbb{E}\/}_{q(xy|m^{i_{B}})}[(-1)^{f}]\Big{)}\in\\{\pm
1\\}$ to Alice. Otherwise, he sends $\bot$ to abort the protocol.

The protocol has the feature that Alice sends at most $2\log 1/\varepsilon$
bits to Bob. Let $i_{*}$ be the smallest index such that

$\prod_{j\text{
odd}}p(m^{i_{*}}_{j}|xm^{i_{*}}_{<j})\geq\rho^{i_{*}}_{A}\text{ and
}\prod_{j\text{ even}}p(m^{i_{*}}_{j}|xm^{i_{*}}_{<j})\geq\rho^{i_{*}}_{B}.$

Let $m=m^{i_{*}}$. We note that $\Gamma(xym)=p(xym)$.

Let $S$ and $T$ be the sets defined in Equation 44 and Equation 51
respectively for our choice of $K$. In addition to $S$, we need the following
sets to analyze the simulating protocol:

$\displaystyle Q$ $\displaystyle=\Big{\\{}xym\eta^{A}\eta^{B}:\eta^{A}\leq
g_{1}(xm)\cdot 2^{-\lceil\log g_{1}(xm)\rceil},\eta^{B}\leq g_{2}(ym)\cdot
2^{\lceil\log g_{1}(xm)\rceil-3\mathsf{M}/I}\Big{\\}},$
$\displaystyle\mathcal{E}$
$\displaystyle=\Big{\\{}i_{A}i_{B}i_{*}:i_{A}=i_{B}=i_{*}\Big{\\}},$
$\displaystyle\mathcal{Z}$ $\displaystyle=\Big{\\{}xymh:\exists\text{ a unique
integer $z$ with }|z+\log g_{2}(ym)|\leq\frac{3\mathsf{M}}{I}\text{ and
}h(z)=h(\lceil\log g_{1}(xm)\rceil)\Big{\\}}.$

Let $\mathcal{G}$ denote the event that the protocol reaches the final step
without aborting, and define $\mathcal{A}(xym)\in\\{\pm 1\\}$ by

$\mathcal{A}(xym)=\mathsf{sign}\Big{(}\mathop{\mathbb{E}\/}_{q(xy|m)}[(-1)^{f(xy)}]\Big{)}\cdot(-1)^{f(xy)}.$

Our protocol computes $f(xy)$ correctly when: $\mathcal{G}$ happens,
$\mathcal{A}(xym)=1$ and $m=m^{i_{B}}$. Since
$\mathcal{EZ}SQ\subseteq\mathcal{G}$, and $\mathcal{E}$ implies $m=m^{i_{B}}$,
the advantage of our protocol is at least:

$\displaystyle\Gamma(\mathcal{EZ}SQ)\cdot\mathop{\mathbb{E}\/}_{\Gamma(xym|\mathcal{EZ}SQ)}[\mathcal{A}(xym)]-\Gamma(\mathcal{G}(\mathcal{EZ}SQ)^{c}).$
(112)

We shall prove:

$\displaystyle\mathop{\mathbb{E}\/}_{\Gamma(xym|\mathcal{EZ}SQ)}[\mathcal{A}(xym)]$
$\displaystyle\geq\Omega(2^{-\delta\mathsf{M}/(12I)}),$ (113)
$\displaystyle\Gamma(\mathcal{EZ}SQ)$
$\displaystyle\geq\Omega(2^{-6\mathsf{M}/I-6\mathsf{M}}),$ (114)
$\displaystyle\Gamma(\mathcal{G}(\mathcal{EZ}SQ)^{c})$ $\displaystyle\leq
O(2^{-6\mathsf{M}/I-7\mathsf{M}}).$ (115)

By Equation 112, since $\delta\leq 1$, we can choose $K$ to be large enough to
prove the theorem, since $\alpha+K\geq\mathsf{M}/I\geq K$.

We first upper bound $\Gamma(\mathcal{G}(\mathcal{EZ}SQ)^{c})$. By the union
bound, we have:

$\displaystyle\Gamma(\mathcal{G}(\mathcal{EZ}SQ)^{c})$
$\displaystyle\leq\Gamma(\mathcal{G}\mathcal{E}^{c})+\Gamma(\mathcal{Z}^{c}|\mathcal{GE})+\Gamma(S^{c}\mathcal{GEZ})+\Gamma(Q^{c}|\mathcal{GEZ}S).$

The definition of the protocol ensures that
$\Gamma(\mathcal{Z}^{c}|\mathcal{GE})=0$. Moreover, we claim that
$\Gamma(Q^{c}|\mathcal{GEZ}S)=0$, because if the event $\mathcal{EZ}S$ happens
and the parties do not abort, then:

$\displaystyle\eta^{A}$ $\displaystyle\leq g_{1}(xm^{i_{A}})\cdot
2^{\lceil\log g_{1}(xm^{i_{A}})\rceil}=g_{1}(xm)\cdot 2^{\lceil\log
g_{1}(xm)\rceil},$ $\displaystyle\eta^{B}$ $\displaystyle\leq
g_{2}(ym^{i_{B}})\cdot 2^{z-3\mathsf{M}/I}=g_{2}(ym)\cdot 2^{\lceil\log
g_{1}(xm)\rceil-3\mathsf{M}/I}.$

The event $\mathcal{G}\mathcal{E}^{c}$ implies that there was a hash error for
the triples accepted by Alice and Bob. The probability of this happening is at
most $\varepsilon$. Finally,
$\Gamma(S^{c}\mathcal{GEZ})\leq\Gamma(S^{c}\mathcal{EZ})\leq
O(\varepsilon\mathsf{M}/I)$, since if $S^{c}\mathcal{EZ}$ happens then there
must have been a hash collision, which happens with also occurs with
probability at most $2\varepsilon$. By our choice of $\varepsilon$, the total
error is bounded by $2^{-6\mathsf{M}/I-8\mathsf{M}}(2+\mathsf{M}/I)\leq
2^{-6\mathsf{M}/I-7\mathsf{M}}$, for $K$ sufficiently large. This implies
Equation 115.

Let us estimate $\Gamma(QS)$. We have,

$\displaystyle\Gamma(QS)$ $\displaystyle=\sum_{xym\in
S}\Gamma(xym)\cdot\Gamma(Q|xym)=\sum_{xym\in S}p(xym)\cdot\Gamma(Q|xym).$

For $xym\in S$,

$\displaystyle\Gamma(Q|xym)=\frac{g_{1}(xm)\cdot 2^{-\lceil\log
g_{1}(xm)\rceil}\cdot g_{2}(ym)\cdot 2^{\lceil\log
g_{1}(xm)\rceil}}{2^{3\mathsf{M}/I}}$
$\displaystyle=\frac{q(xym)}{p(xym)}\cdot\frac{1}{2^{3\mathsf{M}/I}},$ (116)

where the first equality follows from the fact that

$g_{2}(ym)\cdot 2^{\lceil\log g_{1}(xm)\rceil}=2^{\lceil\log
g_{1}(xm)\rceil+\log g_{2}(ym)}\leq 2^{3\mathsf{M}/I},$

by the definition of $S$. Therefore,

$\displaystyle\Gamma(QS)=\sum_{xym\in
S}p(xym)\cdot\frac{q(xym)}{p(xym)}\cdot\frac{1}{2^{3\mathsf{M}/I}}$
$\displaystyle=\frac{q(S)}{2^{3\mathsf{M}/I}}$
$\displaystyle\geq\frac{(1-5\cdot
2^{-\mathsf{M}/I})}{2^{3\mathsf{M}/I}}=\Omega(2^{-3\mathsf{M}/I}),$ (117)

where in the last line, we used 33.

We claim that for all $xym\in S$,

$\displaystyle\Gamma(\mathcal{Z}|xymQS)=\Gamma(\mathcal{Z}|xym)\geq
1-O(\varepsilon\mathsf{M}/I).$ (118)

The equality follows by observing that $xym$ determine $S$ and given $xym$,
$\mathcal{Z}$ just depends on the choice of $h$, which is independent of $Q$.
The event $\mathcal{Z}^{c}$ can happen only if there exists an integer $z$
distinct from $\lceil\log g_{1}(xm)\rceil$ such that $h(\lceil
g_{1}(xm)\rceil)=h(z)$ and $\left|z+\log g_{2}(ym)\right|\leq 3\mathsf{M}/I$.
The probability that this happens is at most
$O(\varepsilon\cdot\mathsf{M}/I)$. Therefore, $\Gamma(\mathcal{Z}|xym)\geq
1-O(\varepsilon\mathsf{M}/I)\geq 1/2$, by our choice of $\varepsilon$. We
conclude that

$\displaystyle\Gamma(QS\mathcal{Z})$
$\displaystyle=\Gamma(QS)\cdot\Gamma(\mathcal{Z}|QS)\geq\Omega(2^{-3\mathsf{M}/I}),$
(119)

Let $W$ be the event that $\min\\{i_{A},i_{B},i_{*}\\}=1$ and let $T$ be the
set defined in Equation 51 for our choice of $K$. We claim that $TW^{c}$
implies $i_{*}>1$, since if $xym\in T$ then $p(m|xy)\leq
2^{6\mathsf{M}}\cdot\min\\{p(m|x),p(m|y)\\}$, which implies

$\displaystyle\prod_{j\text{ even}}p(m_{j}|ym_{<j})$ $\displaystyle\leq
2^{6\mathsf{M}}\cdot\prod_{j\text{ even}}p(m_{j}|xm_{<j}),$
$\displaystyle\prod_{j\text{ odd}}p(m_{j}|xm_{<j})$ $\displaystyle\leq
2^{6\mathsf{M}}\cdot\prod_{j\text{ even}}p(m_{j}|ym_{<j}),$

and hence if $i_{*}=1$ then in fact $i_{A}=i_{B}=1$.

Now, we compute $\Gamma(\mathcal{E}|QS\mathcal{Z})$.

$\displaystyle\Gamma(\mathcal{E}|QS\mathcal{Z})$
$\displaystyle=\Gamma(\mathcal{E}|QS\mathcal{Z}W)$
$\displaystyle\geq\frac{\Gamma(i_{A}=i_{B}=i_{*}=1|QS\mathcal{Z})}{\Gamma(i_{A}=1|QS\mathcal{Z})+\Gamma(i_{B}=1|QS\mathcal{Z})+\Gamma(i_{*}=1|QS\mathcal{Z})}$
$\displaystyle\geq\frac{\Gamma(i_{A}=i_{B}=i_{*}=1,QS\mathcal{Z})}{\Gamma(i_{A}=1)+\Gamma(i_{B}=1)+\Gamma(i_{*}=1)}.$
(120)

Now, we estimate the numerator and denominator in the last expression. Let
$\mathcal{M}$ be the set of all transcripts in the support of $p$. We have,

$\displaystyle\Gamma(i_{A}=i_{B}=i_{*}=1,QS\mathcal{Z})$
$\displaystyle\geq\sum_{xym\in S\cap
T}\Gamma(i_{A}=i_{B}=i_{*}=1,xym,Q\mathcal{Z})$ $\displaystyle=\sum_{xym\in
S\cap T}\Gamma(i_{A}=i_{B}=i_{*}=1,xym)\cdot\Gamma(Q\mathcal{Z}|xym)$ (given
$xym$, $Q\mathcal{Z}$ is independent of $i_{A},i_{B},i_{*}$)
$\displaystyle=\sum_{xym\in S\cap
T}p(xym)\cdot\frac{1}{|\mathcal{M}|}\cdot\Gamma(Q\mathcal{Z}|xym)$ (by the
definition $\Gamma$ and $T$) $\displaystyle=\sum_{xym\in S\cap
T}p(xym)\cdot\frac{1}{|\mathcal{M}|}\cdot\frac{q(xym)}{p(xym)2^{3\mathsf{M}/I}}\cdot\Gamma(\mathcal{Z}|xym)$
(by Equation 116) $\displaystyle\geq q(ST)\cdot\frac{1}{|\mathcal{M}|\cdot
2^{3\mathsf{M}/I}}\cdot(1-\Omega(\varepsilon\mathsf{M}/I)).$ (by Equation 118)

Next,

$\displaystyle\Gamma(i_{A}=1)=\sum_{xm^{\prime}}\Gamma(i_{A}=1,xm^{\prime})$
$\displaystyle\leq\sum_{xm^{\prime}}p(x)\cdot\frac{1}{|\mathcal{M}|}\cdot\prod_{j\text{
odd}}p(m^{\prime}_{j}|xm^{\prime}_{<j})\cdot
2^{6\mathsf{M}}\cdot\prod_{j\text{ even}}p(m^{\prime}_{j}|xm^{\prime}_{<j})$
$\displaystyle\leq\sum_{xm^{\prime}}p(xm^{\prime})\cdot\frac{2^{6\mathsf{M}}}{|\mathcal{M}|}\leq\frac{2^{6\mathsf{M}}}{|\mathcal{M}|}.$

An identical calculation shows that $\Gamma(i_{B}=1)\leq
2^{6\mathsf{M}}/|\mathcal{M}|$. Furthermore,

$\displaystyle\Gamma(i_{*}=1)=\sum_{xym}\Gamma(i_{*}=1,xym)$
$\displaystyle=\sum_{xym}p(x)\cdot\frac{1}{|\mathcal{M}|}\cdot\prod_{j\text{
odd}}p(m_{j}|xm_{<j})\cdot\prod_{j\text{ even}}p(m_{j}|ym_{<j})$
$\displaystyle\leq\sum_{xym}p(xym)\cdot\frac{1}{|\mathcal{M}|}\leq\frac{1}{|\mathcal{M}|}.$

Plugging this into Equation 120 we get

$\displaystyle\Gamma(\mathcal{E}|QS\mathcal{Z})$
$\displaystyle\geq\frac{q(ST)\cdot(1-\Omega(\varepsilon\mathsf{M}/I))}{2^{6\mathsf{M}+(3\mathsf{M}/I)+2}}=\Omega(2^{-6\mathsf{M}-(3\mathsf{M}/I)}),$

by 33 and 36. Using Equation 119 we get that
$\Gamma(QS\mathcal{Z}\mathcal{E})=\Omega(2^{-6\mathsf{M}-(6\mathsf{M}/I)})$ as
claimed in Equation 114.

For all $xym\in S$,

$\displaystyle\Gamma(xym|QS\mathcal{Z})$
$\displaystyle=\frac{\Gamma(xym)\cdot\Gamma(QS\mathcal{Z}|xym)}{\Gamma(QS\mathcal{Z})}$
$\displaystyle=\frac{p(xym)}{\Gamma(QS)}\cdot\Gamma(Q|xym)\cdot\frac{\Gamma(\mathcal{Z}|xymQS)}{\Gamma(\mathcal{Z}|QS)}$
$\displaystyle=\frac{p(xym)}{\Gamma(QS)}\cdot\frac{q(xym)}{p(xym)\cdot
2^{3\mathsf{M}/I}}\cdot\frac{\Gamma(\mathcal{Z}|xymQS)}{\Gamma(\mathcal{Z}|QS)}$
$\displaystyle=\frac{q(xym)}{q(S)}\cdot\frac{\Gamma(\mathcal{Z}|xymQS)}{\Gamma(\mathcal{Z}|QS)}$
(By Section 11) $\displaystyle=q(xym|S)\cdot(1\pm
O(\varepsilon\mathsf{M}/I)),$ (121)

where the last line follows by Equation 118.

Next, we note that

$\displaystyle\Gamma(\mathcal{E}|QS\mathcal{Z},i_{*}=1)\geq\Gamma(\mathcal{E},T|QS\mathcal{Z},i_{*}=1)=\Gamma(T|QS\mathcal{Z}),$
(122)

where we used the fact that the event $T,i_{*}=1$ implies $\mathcal{E}$ and
that $xym$ is distributed independently of $i_{*}$. For any $xym\in S\cap T$

$\displaystyle\Gamma(xym|QS\mathcal{Z}\mathcal{E})$
$\displaystyle=\Gamma(xym|QS\mathcal{Z}\mathcal{E}W)$ ($xym$ is independent of
$W$ even conditioned on $QS\mathcal{Z}\mathcal{E}$)
$\displaystyle=\Gamma(xym|QS\mathcal{Z}\mathcal{E},i_{*}=1)$ (the event
$\mathcal{E}W$ is the same as the event $\mathcal{E},i_{*}=1$)
$\displaystyle=\frac{\Gamma(xym\mathcal{E}|QS\mathcal{Z},i_{*}=1)}{\Gamma(\mathcal{E}|QS\mathcal{Z}i^{*}=1)}$
$\displaystyle=\Gamma(xym|QS\mathcal{Z})\cdot\frac{\Gamma(\mathcal{E}|xym,i_{*}=1)}{\Gamma(\mathcal{E}|QS\mathcal{Z}i^{*}=1)}$
$\displaystyle=\frac{\Gamma(xym|QS\mathcal{Z})}{\Gamma(\mathcal{E}|QS\mathcal{Z}i^{*}=1)}$
(because $xym\in S\cap T$) $\displaystyle=\Gamma(xym|QS\mathcal{Z})\cdot(1\pm
O(\Gamma(T^{c}|QS\mathcal{Z})))$

where the last inequality used the fact that
$1\geq\Gamma(\mathcal{E}|QS\mathcal{Z}i^{*}=1)\geq
1-\Gamma(T^{c}|QS\mathcal{Z})$ by Equation 122. Together with Equation 121 we
get that for any $xym\in S\cap T$

$\displaystyle\Gamma(xym|QS\mathcal{Z}\mathcal{E})$
$\displaystyle=q(xym|S)\cdot(1\pm
O(\Gamma(T^{c}|QS\mathcal{Z})+\varepsilon\mathsf{M}/I))$
$\displaystyle=q(xym|S)\cdot(1\pm O(q(T^{c}|S)+\varepsilon\mathsf{M}/I))$
$\displaystyle=q(xym|S)\cdot(1\pm
O(2^{-\mathsf{M}/I}+\varepsilon\mathsf{M}/I)),$ (123)

where the last line follows by 36.

Now, we complete the proof of Equation 113. We have

$\displaystyle\mathop{\mathbb{E}\/}_{\Gamma(xym|QS\mathcal{ZE})}[\mathcal{A}(xym)]$
$\displaystyle\geq\sum_{xym\in S\cap
T}\Gamma(xym|QS\mathcal{ZE})\cdot\mathcal{A}(xym)-\Gamma(T^{c}|QS\mathcal{ZE})$
$\displaystyle\geq\sum_{xym\in S\cap
T}q(xym|S)\cdot\mathcal{A}(xym)-\Omega(2^{-\mathsf{M}/I}+\varepsilon\mathsf{M}/I)-1+\Gamma(T|QS\mathcal{ZE})$
(by Equation 123)
$\displaystyle\geq\mathop{\mathbb{E}\/}_{q(xym|S)}[\mathcal{A}(xym)]-q(T^{c}|S)-\Omega(2^{-\mathsf{M}/I}+\varepsilon\mathsf{M}/I)-1+q(T|S)\cdot(1-O(2^{-\mathsf{M}/I}+\varepsilon\mathsf{M}/I))$
(by Equation 123)
$\displaystyle\geq\mathop{\mathbb{E}\/}_{q(xym)}[\mathcal{A}(xym)]-q(S^{c})-2q(T^{c}|S)-\Omega(2^{-\mathsf{M}/I}+\varepsilon\mathsf{M}/I)$
$\displaystyle=\mathop{\mathbb{E}\/}_{q(xym)}[\mathcal{A}(xym)]-\Omega(2^{-\mathsf{M}/I}+\varepsilon\mathsf{M}/I)$
(by 33 and 36)
$\displaystyle=\mathop{\mathbb{E}\/}_{q(xym)}\bigg{[}\mathsf{sign}\bigg{(}\mathop{\mathbb{E}\/}_{q(x^{\prime}y^{\prime}|m)}\Big{[}(-1)^{f}\Big{]}\bigg{)}\cdot(-1)^{f(xy)}\bigg{]}-\Omega(2^{-\mathsf{M}/I})$
$\displaystyle=\mathop{\mathbb{E}\/}_{q(m)}\bigg{[}\bigg{|}\mathop{\mathbb{E}\/}_{q(xy|m)}\Big{[}(-1)^{f(xy)}\Big{]}\bigg{|}\bigg{]}-\Omega(2^{-\mathsf{M}/I})\geq\Omega(2^{-\delta\mathsf{M}/(12I)}),$

by Equation 53.

## References

  * [BBCR10] Boaz Barak, Mark Braverman, Xi Chen, and Anup Rao.  How to compress interactive communication.  In Proceedings of the Forty-Second ACM Symposium on Theory of Computing, STOC ’10, page 67–76, New York, NY, USA, 2010. Association for Computing Machinery.
  * [BK18] Mark Braverman and Gillat Kol.  Interactive compression to external information.  In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, page 964–977, New York, NY, USA, 2018. Association for Computing Machinery.
  * [BP16] Gábor Braun and Sebastian Pokutta.  Common information and unique disjointness.  Algorithmica, 76(3):597–629, 2016.
  * [BR11] Mark Braverman and Anup Rao.  Information equals amortized communication.  In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 748–757, Los Alamitos, CA, USA, oct 2011. IEEE Computer Society.
  * [Bra15] Mark Braverman.  Interactive information complexity.  SIAM Journal on Computing, 44(6):1698–1739, 2015.
  * [BRWY13a] Mark Braverman, Anup Rao, Omri Weinstein, and Amir Yehudayoff.  Direct product via round-preserving compression.  In Fedor V. Fomin, Rusins Freivalds, Marta Z. Kwiatkowska, and David Peleg, editors, Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part I, volume 7965 of Lecture Notes in Computer Science, pages 232–243. Springer, 2013.
  * [BRWY13b] Mark Braverman, Anup Rao, Omri Weinstein, and Amir Yehudayoff.  Direct products in communication complexity.  In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 746–755, 2013.
  * [BYJKS02] Z. Bar-Yossef, T.S. Jayram, R. Kumar, and D. Sivakumar.  An information statistics approach to data stream and communication complexity.  In The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings., pages 209–218, 2002.
  * [CSWY01] A. Chakrabarti, Yaoyun Shi, A. Wirth, and A. Yao.  Informational complexity and the direct sum problem for simultaneous message complexity.  In Proceedings 42nd IEEE Symposium on Foundations of Computer Science, pages 270–278, 2001.
  * [CT91] Thomas M. Cover and Joy A. Thomas.  Elements of Information Theory.  Wiley series in telecommunications. J. Wiley and Sons, New York, 1991\.
  * [FKNN95] Tomás Feder, Eyal Kushilevitz, Moni Naor, and Noam Nisan.  Amortized communication complexity.  SIAM Journal on Computing, 24(4):736–750, 1995.
  * [GKR16] Anat Ganor, Gillat Kol, and Ran Raz.  Exponential separation of information and communication for boolean functions.  J. ACM, 63(5), nov 2016.
  * [HJMR10] Prahladh Harsha, Rahul Jain, David McAllester, and Jaikumar Radhakrishnan.  The communication complexity of correlation.  IEEE Transactions on Information Theory, 56(1):438–449, 2010.
  * [Hol07] Thomas Holenstein.  Parallel repetition: Simplifications and the no-signaling case.  In Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing, STOC ’07, page 411–419, New York, NY, USA, 2007. Association for Computing Machinery.
  * [JHM+98] Mark Jerrum, Michel Habib, Colin McDiarmid, Jorge L. Ramirez-Alfonsin, and Bruce Reed.  Probabilistic Methods for Algorithmic Discrete Mathematics, volume 16 of Algorithms and Combinatorics.  Springer-Verlag, 1998.
  * [JPY12] Rahul Jain, Attila Pereszlényi, and Penghui Yao.  A direct product theorem for the two-party bounded-round public-coin communication complexity.  In 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, pages 167–176, 2012.
  * [JRS03] Rahul Jain, Jaikumar Radhakrishnan, and Pranab Sen.  A direct sum theorem in communication complexity via message compression.  In Jos C. M. Baeten, Jan Karel Lenstra, Joachim Parrow, and Gerhard J. Woeginger, editors, Automata, Languages and Programming, pages 300–315, Berlin, Heidelberg, 2003. Springer Berlin Heidelberg.
  * [JSY23] Xinrui Jia, Ola Svensson, and Weiqiang Yuan.  The exact bipartite matching polytope has exponential extension complexity.  In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1635–1654. SIAM, 2023.
  * [Kol16] Gillat Kol.  Interactive compression for product distributions.  In Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, STOC ’16, page 987–998, New York, NY, USA, 2016. Association for Computing Machinery.
  * [KRW95] Mauricio Karchmer, Ran Raz, and Avi Wigderson.  Super-logarithmic depth lower bounds via the direct sum in communication complexity.  Comput. Complex., 5(3/4):191–204, 1995.
  * [Pǎt11] Mihai Pǎtraşcu.  Unifying the landscape of cell-probe lower bounds.  SIAM J. Comput., 40(3):827–847, jun 2011.
  * [Rao11] Anup Rao.  Parallel repetition in projection games and a concentration bound.  SIAM Journal on Computing, 40(6):1871–1891, 2011.
  * [Raz92] Alexander A. Razborov.  On the distributional complexity of disjointness.  Theor. Comput. Sci., 106(2):385–390, 1992.
  * [Raz95] Ran Raz.  A parallel repetition theorem.  In Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, STOC ’95, page 447–456, New York, NY, USA, 1995. Association for Computing Machinery.
  * [Rot17] Thomas Rothvoss.  The matching polytope has exponential extension complexity.  J. ACM, 64(6), sep 2017.
  * [RR15] Sivaramakrishnan Natarajan Ramamoorthy and Anup Rao.  How to compress asymmetric communication.  In Proceedings of the 30th Conference on Computational Complexity, CCC ’15, page 102–123, Dagstuhl, DEU, 2015. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
  * [RS18] Anup Rao and Makrand Sinha.  Simplified separation of information and communication.  Theory of Computing, 14(20):1–29, 2018.
  * [RY20] Anup Rao and Amir Yehudayoff.  Communication Complexity: and Applications.  Cambridge University Press, 2020.
  * [Sha48] Claude Elwood Shannon.  A mathematical theory of communication.  The Bell System Technical Journal, 27:379–423, 1948.
  * [She18] Alexander A. Sherstov.  Compressing interactive communication under product distributions.  SIAM Journal on Computing, 47(2):367–419, 2018.
  * [Sin18] Makrand Sinha.  Lower bounds for approximating the matching polytope.  In Artur Czumaj, editor, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 1585–1604. SIAM, 2018.
  * [SK87] Georg Schnitger and Bala Kalyanasundaram.  The probabilistic communication complexity of set intersection.  In Proceedings of the Second Annual Conference on Structure in Complexity Theory, Cornell University, Ithaca, New York, USA, June 16-19, 1987. IEEE Computer Society, 1987.
  * [Yu22] Huacheng Yu.  Strong xor lemma for communication with bounded rounds : (extended abstract).  In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 1186–1192, 2022.