# Strong XOR Lemma for Communication with Bounded Rounds

Huacheng Yu Department of Computer Science, Princeton University.
<EMAIL_ADDRESS>Supported by Simons Junior Faculty Award.

###### Abstract

In this paper, we prove a strong XOR lemma for bounded-round two-player
randomized communication. For a function
$f:\mathcal{X}\times\mathcal{Y}\rightarrow\\{0,1\\}$, the $n$-fold XOR
function $f^{\oplus
n}:\mathcal{X}^{n}\times\mathcal{Y}^{n}\rightarrow\\{0,1\\}$ maps $n$ input
pairs $(X_{1},\ldots,X_{n},Y_{1},\ldots,Y_{n})$ to the XOR of the $n$ output
bits $f(X_{1},Y_{1})\oplus\cdots\oplus f(X_{n},Y_{n})$. We prove that if every
$r$-round communication protocols that computes $f$ with probability $2/3$
uses at least $C$ bits of communication, then any $r$-round protocol that
computes $f^{\oplus n}$ with probability $1/2+\exp(-O(n))$ must use
$n\cdot\left(r^{-O(r)}\cdot C-1\right)$ bits. When $r$ is a constant and $C$
is sufficiently large, this is $\Omega(n\cdot C)$ bits. It matches the
communication cost and the success probability of the trivial protocol that
computes the $n$ bits $f(X_{i},Y_{i})$ independently and outputs their XOR, up
to a constant factor in $n$.

A similar XOR lemma has been proved for $f$ whose communication lower bound
can be obtained via bounding the discrepancy [Sha03]. By the equivalence
between the discrepancy and the correlation with $2$-bit communication
protocols [VW08], our new XOR lemma implies the previous result.

###### Contents

  1. 1 Introduction
    1. 1.1 Related work
  2. 2 Technical Overview
    1. 2.1 An alternative view of [BBCR13]
    2. 2.2 Obtaining exponentially small advantage
    3. 2.3 Generalized protocols
    4. 2.4 $\theta$-cost and $\chi^{2}$-costs
    5. 2.5 Proof outline
    6. 2.6 Convert a generalized protocol to a standard protocol
  3. 3 Notations and Definitions for Generalized Protocols
    1. 3.1 Notations and standard probabilities
    2. 3.2 Generalized communication protocols
    3. 3.3 The $\theta$-cost and $\chi^{2}$-costs
    4. 3.4 Rectangle properties in generalized protocols
  4. 4 Main Setup
  5. 5 Decomposition of Generalized Protocols
    1. 5.1 Definition of $\pi_{<k}$ and $\pi_{k}$
    2. 5.2 Decomposition of the costs
  6. 6 Induction: Proof of Lemma 26
    1. 6.1 Identify event $U$
    2. 6.2 High costs
    3. 6.3 Low costs
    4. 6.4 Putting together
    5. 6.5 Proof of Lemma 37
  7. 7 Compression of Generalized Protocols: Proof of Lemma 40
  8. A Theorem 2 Implies Shaltiel’s XOR Lemma

##  1 Introduction

In computational complexity, XOR lemmas study the relation between the
complexity of a $\\{0,1\\}$-valued function $f(x)$ and the complexity of the
$n$-fold XOR function $f^{\oplus n}$ where

$f^{\oplus n}(x_{1},\ldots,x_{n})=f(x_{1})\oplus\cdots\oplus f(x_{n})$

and $\oplus$ is the XOR. A classic example is Yao’s XOR lemma for circuits
[Yao82], which states if $f$ cannot be computed with probability $2/3$ on a
random input by size-$s$ circuits, then $f^{\oplus n}$ cannot be computed with
probability $1/2+\exp(-\Omega(n))$ on a random input by size-$s^{\prime}$
circuits for some $s^{\prime}<s$ (and small $n$). Such lemmas can be used to
create very hard functions in a blackbox way, which can only be computed
barely better than random guessing, from functions that are “just” hard to
compute with constant probability. This approach of hardness amplification has
been used in one-way functions [Yao82, Lev87], pseudorandom generators [Imp95,
IW97], and more recently, streaming lower bounds [AN21, CKP+21].

In general, suppose computing a function $f$ with probability $2/3$ requires
resource $s$ in some model of computation (e.g., circuit size, running time,
query complexity, communication cost, etc). Then the trivial way to compute
$f^{\oplus n}$ is to compute each $f(x_{i})$ using resource $s$ independently,
and output their XOR. It uses resource $n\cdot s$ in total, and each instance
is correct with probability $2/3$, hence, their XOR is correct with
probability $1/2+\exp(-\Theta(n))$: For two _independent_ random bits
$b_{1},b_{2}$, if $\Pr[b_{1}=0]=1/2+\alpha_{1}/2$ and
$\Pr[b_{2}=0]=1/2+\alpha_{2}/2$, then

$\displaystyle\Pr[b_{1}\oplus
b_{2}=0]=(1/2+\alpha_{1}/2)(1/2+\alpha_{2}/2)+(1/2-\alpha_{1}/2)(1/2-\alpha_{2}/2)=1/2+\alpha_{1}\alpha_{2}/2;$

let $b_{i}=0$ if and only if $f(x_{i})$ is computed correctly, applying the
above calculation inductively gives the claimed probability. A _strong XOR
lemma_ asserts that to achieve $1/2+\exp(-O(n))$ success probability, one must
use $\Omega(n\cdot s)$ resource — the trivial solution is essentially optimal.

Now suppose that we are given $n\cdot s/2$ resource in total, and we want to
compute $f^{\oplus n}$. If we try to solve the $n$ copies independently, then
no matter how we distribute the resource among the $n$ copies, at least half
of them will get no more than $s$. The function $f^{\oplus}$ is computed
correctly with probability at most $1/2+\exp(-\Omega(n))$. Of course, since
all $n$ inputs $(x_{1},\ldots,x_{n})$ are given together, we can potentially
process them jointly. This may correlate the $n$ copies, and in particular, it
may correlate the correctness of computing each $f(x_{i})$. Hence, one
difficulty in proving the strong XOR lemma from the technical point of view is
that in the above calculation of the probability of XOR of two independent
bits, the linear terms perfectly cancel only because $b_{1}$ and $b_{2}$ are
independent; when they are not independent, we may get a linear term
remaining, and do not reduce the probability bias as desired. In computational
models where one cannot expect the independence between the copies throughout
the computation, a success probability lower bound of $1/2+\exp(-\Omega(n))$
(hence, a strong XOR lemma) is generally difficult to prove.

In this paper, we prove a strong XOR lemma for the two-player randomized
communication complexity with bounded rounds: Alice and Bob receive $X$ and
$Y$ respectively, they alternatively send a total of $r$ messages to each
other with the goal of computing $f(X,Y)$. For $f^{\oplus n}$, Alice receives
$(X_{1},\ldots,X_{n})$ and Bob receives $(Y_{1},\ldots,Y_{n})$, and they wish
to compute $f(X_{1},Y_{1})\oplus\cdots\oplus f(X_{n},Y_{n})$ after $r$ rounds
of communication. Each player has half of the inputs for all copies, and can
send messages that arbitrarily depend on them, which can nontrivially
correlate the $n$ instances. Nevertheless, we show that one cannot do much
better than simply solving all $n$ copies in parallel.

Let $\mathbf{R}^{(r)}_{p}(f)$ be the minimum number of bits of communication
needed in $r$ messages in order to compute $f(X,Y)$ correctly with probability
$p$. We prove the following theorem.

######  Theorem 1.

For any $\\{0,1\\}$-valued function $f$, we have

$\mathbf{R}^{(r)}_{1/2+2^{-n}}(f^{\oplus n})\geq
n\cdot\left(r^{-O(r)}\cdot\mathbf{R}^{(r)}_{2/3}(f)-1\right).$

In particular, when $r$ is a constant, it implies that
$\mathbf{R}^{(r)}_{1/2+2^{-n}}(f^{\oplus
n})\geq\Omega\left(n\cdot\left(\mathbf{R}^{(r)}_{2/3}(f)-O(1)\right)\right)$.111Observe
that since $\mathbf{R}^{(r)}_{0.51}(f)\leq\mathbf{R}^{(r)}_{0.99}(f)\leq
O(\mathbf{R}^{(r)}_{0.51}(f))$, the constant $2/3$ does not matter as long as
it is in $(1/2,1)$. Our proof will also show that the base in $2^{-n}$ can be
any constant. To the best of our knowledge, such an XOR lemma was not known
even for one-way communication and without the factor of $n$.

As pointed in [BBCR13], the “$-O(1)$” term is needed. This is because for
$f(X,Y)=X\oplus Y$, we have $\mathbf{R}^{(r)}_{2/3}(f)=2$. On the other hand,
$f^{\oplus n}$ can also be computed with $2$ bits of communication by simply
(locally) computing $\bigoplus_{i=1}^{n}X_{i}$ and $\bigoplus_{i=1}^{n}Y_{i}$
and exchanging the values.

We obtain Theorem 1 via the following _distributional_ strong XOR lemma. Let
$\mathrm{suc}_{\mu}({f;C_{A},C_{B},r})$ be the maximum success probability of
an $r$-round protocol $\pi$ computing $f(X,Y)$ where

  * •

Alice sends at most $C_{A}$ bits in every odd round,

  * •

Bob sends at most $C_{B}$ bits in every even round, and

  * •

$(X,Y)$ is sampled from $\mu$.

######  Theorem 2.

Let $c>0$ be a sufficiently large constant. Fix $\alpha\in(0,r^{-cr})$ and
$C_{A},C_{B}\geq 2c\log(r/\alpha)$. Let
$f:\mathcal{X}\times\mathcal{Y}\rightarrow\\{0,1\\}$ be a function, and $\mu$
be a distribution over $\mathcal{X}\times\mathcal{Y}$. Suppose $f$ satisfies

$\mathrm{suc}_{\mu}({f;C_{A},C_{B},r})\leq 1/2+\alpha/2,$

then for any integer $n\geq 2$, we have

$\mathrm{suc}_{\mu^{n}}(f^{\oplus n};2^{-8}r^{-1}n\cdot
C_{A},2^{-8}r^{-1}n\cdot C_{B},r)\leq\frac{1}{2}+\frac{\alpha^{2^{-12}n}}{2}.$

This distributional strong XOR lemma states that for any fixed input
distribution $\mu$ and function $f$, to compute $f^{\oplus n}$ when the $n$
inputs are sampled independently from $\mu$, either the advantage is
exponentially small in $\Omega(n)$, or one of the players need to communicate
at least $\Omega(n/r)$ times more than one copy. This also gives a strong XOR
lemma in the asymmetric communication, where we separately count how many bits
Alice and Bob send.

It is worth noting that Shaltiel [Sha03] proved a similar strong XOR lemma for
functions whose communication lower bound can be obtained via bounding the
_discrepancy_. By the equivalence between the discrepancy and the correlation
with 2-bit protocols [VW08], Theorem 2 implies their result. See Appendix A
for a more detailed argument.

Note that a simple argument shows that Theorem 2 implies Theorem 1 (see also
Section 4). Therefore, we will focus on the distributional version, and assume
that the $n$ input pairs are sampled independently from some distribution
$\mu$.

Our proof of the distributional version is inspired by the _information
complexity_ [CSWY01]. We define a new complexity measure for protocols, the
_$\chi^{2}$ -cost_, which is related to the _internal information cost_
[BJKS04, BBCR13]. Roughly speaking, it replaces the KL-divergence in the
internal information cost with the $\chi^{2}$-divergence, which can be viewed
as the “exponential” version of KL. This provides better concentration, which
is needed in our argument. Throughout the proof, we will also work with
distributions that are “close to” communication protocols, i.e., the speaker’s
message may slightly depend on the receiver’s input. Such distributions have
also been studied in the proof of direct product theorems [JPY12, BRWY13a,
BRWY13b]. We will provide more details in Section 2.

###  1.1 Related work

As we mentioned earlier, Shaltiel [Sha03] proved a strong XOR lemma for
functions whose communication lower bound can be obtained via bounding the
discrepancy. Sherstov [She11] extended this bound to generalized discrepancy
and quantum communication complexity.

Barak, Braverman, Chen and Rao [BBCR13] obtained an XOR lemma for the
information complexity and then an XOR lemma for communication (with worst
parameters) via information compression. However, their XOR lemma does not
give exponentially small advantage. They proved that if $f$ is hard to compute
with information cost $C$, then $f^{\oplus n}$ is hard to compute with
information cost $O(n\cdot C)$. In fact, the starting point of our proof is an
alternative view of their argument, which we will outline in Section 2.1.

Viola and Wigderson [VW08] proved a strong XOR lemma for multi-player $c$-bit
communication for small $c$. As pointed out in their paper, it implies the XOR
lemma by Shaltiel [Sha03]. XOR lemmas have also been proved in circuit
complexity [Yao82, Lev87, Imp95, IW97, GNW11], query complexity [Sha03, She11,
Dru12, BKLS20], streaming [AN21] and for low degree polynomials [VW08].

Direct product and direct sum theorems, which are results of similar types,
have also been studied in the literature. They ask to return the outputs of
all $n$ copies instead of their XOR. Direct sum theorems state that the
problem cannot be solved with the same probability unless $\Omega(n)$ times
more resource is used, while direct product theorems state that the problem
can only be solved with probability _exponentially small_ in $\Omega(n)$
unless $\Omega(n)$ times more resource is used. The direct sum theorem for
information complexity is known [CSWY01, BJKS04, BBCR13]. A direct sum theorem
for communication complexity with suboptimal parameters can be obtained via
information compression [BBCR13]. A direct sum theorem for bounded-round
communication has been proved [BR11], and we use a similar argument in one
component of the proof (see Section 2.6 and Section 7). Direct product
theorems for communication complexity (with suboptimal parameters via
information compression), bounded-round communication and from information
complexity to communication complexity have also been studied [JPY12, BRWY13b,
BW15].

##  2 Technical Overview

###  2.1 An alternative view of [BBCR13]

The starting point of our proof is an alternative view of the XOR lemma in
[BBCR13] for _information complexity_ , which does not give an exponentially
small advantage. Running a protocol on an input pair sampled from some fixed
input distribution defines a joint distribution over the input pairs and the
transcripts. Information complexity studies that in this joint distribution,
how much information the transcript reveals about the inputs. The (internal)
information cost is defined as

$I(X;\mathbf{M}\mid Y,M_{0})+I(Y;\mathbf{M}\mid X,M_{0}),$

where $\mathbf{M}=(M_{0},M_{1},\ldots,M_{r})$ is the transcript and $M_{0}$ is
the public random bits.222In the usual definition, the public random string is
not part of the transcript. We add it for simplicity of notations. This does
not change the values of the mutual information terms as it is already in the
condition. We assume that Alice sends all the odd $M_{i}$ and Bob sends all
the even $M_{i}$. The internal information cost of a protocol is always at
most its communication cost. It is also known that for bounded-round
communication, the internal information complexity is roughly equal to the
communication complexity [BR11] (up to some additive error probability).

For the XOR lemma for information complexity, we consider input pair
$X=(X_{1},\ldots,X_{n})$ and $Y=(Y_{1},\ldots,Y_{n})$ sampled from $\mu^{n}$.
Suppose there is a protocol $\pi$ computing $f^{\oplus n}$ with information
cost $I$, we want to show that $f$ can be computed with information cost
$\approx I/n$.

To this end, we show that $\pi$ can be “decomposed” into a protocol $\pi_{<n}$
computing $f^{\oplus n-1}$ with information cost $I_{1}$ and a protocol
$\pi_{n}$ computing $f$ with information cost $I_{2}$ such that
$I_{1}+I_{2}\approx I$, as follows (see also Figure 1).

  * •

For $\pi_{<n}$, given $n-1$ input pairs, the players view them as $X_{<n}$ and
$Y_{<n}$ as part of the inputs for $\pi$, where $X_{<n}$ denotes
$(X_{1},\ldots,X_{n-1})$ and $Y_{<n}$ denotes $(Y_{1},\ldots,Y_{n-1})$; then
the players publicly sample $X_{n}\sim\mu_{X}$, and Bob privately samples
$Y_{n}$ conditioned on $X_{n}$; the players run $\pi$ to compute $f^{\oplus
n}(X,Y)$; Bob sends one extra bit indicating $f(X_{n},Y_{n})$.

  * •

For $\pi_{n}$, given one input pair, the players view it as $X_{n}$ and
$Y_{n}$; then the players publicly sample $Y_{<n}\sim\mu_{Y}^{n-1}$, and Alice
privately samples $X_{<n}$ conditioned on $Y_{<n}$; the players run $\pi$ to
compute $f^{\oplus n}(X,Y)$; Alice sends one extra bit indicating
$\oplus_{i=1}^{n-1}f(X_{i},Y_{i})$.

$X$$Y$ (a) Protocol $\pi_{<k}$

$X$$Y$ (b) Protocol $\pi_{k}$

Figure 1: Decomposition of $\pi$:  is the inputs,  is sampled publicly,  is
sampled privately.

If $\pi$ computes $f^{\oplus n}$ correctly, then the two protocols compute
$f^{\oplus n-1}$ and $f$ correctly respectively. For the information cost of
$\pi_{<n}$ (if we exclude the last bit indicating $f(X_{n},Y_{n})$), the first
term is equal to $I(X_{<n};\mathbf{M}\mid Y_{<n},X_{n},M_{0})$, since $X_{n}$
is sampled using public random bits. It is also equal to
$I(X_{<n};\mathbf{M}\mid Y,X_{n},M_{0})$ due to the _rectangle property_ of
communication protocols. For the information cost of $\pi_{n}$ (if we exclude
the last bit), the first term is equal to $I(X_{n};\mathbf{M}\mid Y,M_{0})$
since $Y_{<n}$ is sampled using public random bits. Therefore, the first terms
sum up to exactly $I(X;\mathbf{M}\mid Y,M_{0})$, the first term in the
information cost of $\pi$, by the chain rule of mutual information. Similarly,
the second terms sum up to $I(Y;\mathbf{M}\mid X,M_{0})$, the second term in
the information cost of $\pi$.

Hence, including the last bits in the protocols, we have $I_{1}+I_{2}\leq
I+O(1)$. Thus, by repeatedly applying this argument, we obtain a protocol for
$f$ with information cost $I/n+O(1)$, as desired. Note that in this
decomposition, the players _do not_ need to sample the private parts
explicitly. As long as they can send the messages from the same distribution
(e.g., by directly sampling the messages conditioned on the previous messages
and their own inputs), the information costs and correctness are not affected.

The original paper proves the same result by explicitly writing out the
protocol for $f$ obtained after applying the above decomposition $i$ times for
a random $i\in[n]$, and proving the expected cost is as claimed. The two
proofs are essentially equivalent for this statement.333The orginal proof
embeds the input to $f$ into a random coordinate $i$ of $f^{\oplus n}$, and
samples $X_{>i}$ and $Y_{<i}$ using public random bits. However, as we will
see later, our new view is more flexible, allowing for more sophisticated
manipulations when doing the decomposition.

###  2.2 Obtaining exponentially small advantage

The above decomposition preserves the success probability. However, if we
start from a protocol for $f^{\oplus n}$ with exponentially small advantage,
then we will not be able to obtain a protocol for $f$ with success probability
$2/3$, which is required in order to prove the strong XOR lemma.444In fact,
this is inherent for information complexity, since the strong XOR lemma for
_information complexity_ does not hold. This is because the information
complexity is an average measure, and it is at most the _expected_
communication. A protocol can choose to compute _all_ $f(X_{i},Y_{i})$ with
probability $\varepsilon$ and output a random bit otherwise, which achieves
success probability $1/2+\varepsilon$ and expected communication $\varepsilon
n$ times the one-copy cost. However, the reader is encouraged to continue
reading this subsection pretending that they do not know about this
counterexample.

Let $\mathrm{adv}(f(X,Y)\mid\mathbf{R})$ denote the advantage for $f(X,Y)$
conditioned on $\mathbf{R}$, which is defined as

$\left|2\Pr[f(X,Y)=1\mid\mathbf{R}]-1\right|,$

i.e., the advantage is $\alpha$ if the conditional probability is either
$1/2+\alpha/2$ or $1/2-\alpha/2$.

Now let us take a closer look at the two protocols $\pi_{<n}$ and $\pi_{n}$
(see Figure 2). For $\pi_{<n}$, in _Bob’s view_ at the end of the
communication, he knows his input $Y_{<n}$, the publicly sampled $X_{n}$ and
the transcript $\mathbf{M}$. Hence, he is able to predict $f^{\oplus
n-1}(X_{<n},Y_{<n})$ with advantage $\mathrm{adv}(f^{\oplus
n-1}(X_{<n},Y_{<n})\mid X_{n},Y_{<n},\mathbf{M})$. By letting Bob send one
extra bit indicating his prediction, the advantage of the protocol achieves
the same. For $\pi_{n}$, in _Alice’s view_ at the end of the communication,
she knows her input $X_{n}$, the publicly sampled $Y_{<n}$ and the transcript
$\mathbf{M}$. Hence, she is able to predict $f(X_{n},Y_{n})$ with advantage
$\mathrm{adv}(f(X_{n},Y_{n})\mid X_{n},Y_{<n},\mathbf{M})$. By letting Alice
send one extra bit indicating her prediction, the advantage of the protocol
achieves the same.

Now an important observation is that $X_{<n}$ and $Y_{n}$ are independent
conditioned on $(X_{n},Y_{<n},\mathbf{M})$, by the rectangle property of
communication protocols. Hence, $f^{\oplus n-1}(X_{<n},Y_{<n})$ and
$f(X_{n},Y_{n})$ are also independent conditioned on
$(X_{n},Y_{<n},\mathbf{M})$. Since $f^{\oplus n}(X,Y)=f^{\oplus
n-1}(X_{<n},Y_{<n})\oplus f(X_{n},Y_{n})$, by the probability of XOR of two
independent bits, we have

$\displaystyle\mathrm{adv}(f^{\oplus n}(X,Y)\mid X_{n},Y_{<n},\mathbf{M})$
$\displaystyle=\mathrm{adv}(f^{\oplus n-1}(X_{<n},Y_{<n})\mid
X_{n},Y_{<n},\mathbf{M})$ (1) $\displaystyle\hskip
70.0pt\times\mathrm{adv}(f(X_{n},Y_{n})\mid X_{n},Y_{<n},\mathbf{M}).$

$X$$Y$ (a) Bob’s view in $\pi_{<k}$

$X$$Y$ (b) Alice’s view in $\pi_{k}$

Figure 2: Decomposition of $\pi$:  is unknown inputs,  is known.

This suggests the following strategy for the decomposition:

  * •

if the information cost of $\pi_{n}$ is large, then the information cost of
$\pi_{<n}$ must be much smaller than that of $\pi$;

  * •

if the information cost of $\pi_{n}$ is small and its advantage for $f$ is
large, then we have obtained a good protocol for $f$;

  * •

if the information cost of $\pi_{n}$ is small and its advantage for $f$ is
small, then by (1), the advantage of $\pi_{<n}$ must be larger than that of
$\pi$ by some factor.

Hence, in each decomposition, if we don’t already obtain a good protocol for
$f$, then when decrementing $n$ to $n-1$, we must either significantly
decrease the information cost, or increase the advantage by a multiplicative
factor. If we start with a protocol with a low cost and a mild-exponentially
small advantage for $f^{\oplus n}$, then we must obtain a good protocol for
$f$ by applying this decomposition iteratively.

It turns out that the main difficulty in applying the above strategy is to
formalize the last bullet point. Note that the expected advantage of $\pi_{n}$
(after Alice sending the one extra bit indicating her prediction) is
$\mathop{\mathbb{E}}\left[\mathrm{adv}(f(X_{n},Y_{n})\mid
X_{n},Y_{<n},\mathbf{M})\right]$, the expected advantage of $\pi_{<n}$ (after
Bob sending the one extra bit indicating his prediction) is
$\mathop{\mathbb{E}}\left[\mathrm{adv}(f^{\oplus n-1}(X_{<n},Y_{<n})\mid
X_{n},Y_{<n},\mathbf{M})\right]$, and the expected advantage of $\pi$ is
$\mathop{\mathbb{E}}\left[\mathrm{adv}(f^{\oplus
n}(X,Y)\mid\mathbf{M})\right]$, which is at most
$\mathop{\mathbb{E}}\left[\mathrm{adv}(f^{\oplus n}(X,Y)\mid
X_{n},Y_{<n},\mathbf{M})\right]$.

When we say that the advantage of $\pi_{n}$ for $f$ is small in the last
bullet point, we can only guarantee that this expectation is small. Equation
(1), which is a pointwise equality, does not directly give any useful bounds
on the expectations. For example, it is possible that both
$\mathop{\mathbb{E}}\left[\mathrm{adv}(f(X_{n},Y_{n})\mid
X_{n},Y_{<n},\mathbf{M})\right]$ and
$\mathop{\mathbb{E}}\left[\mathrm{adv}(f^{\oplus n-1}(X_{<n},Y_{<n})\mid
X_{n},Y_{<n},\mathbf{M})\right]$ are very small, but
$\mathrm{adv}(f(X_{n},Y_{n})\mid X_{n},Y_{<n},\mathbf{M})$ and
$\mathrm{adv}(f^{\oplus n-1}(X_{<n},Y_{<n})\mid X_{n},Y_{<n},\mathbf{M})$ are
always equal to zero or one at the same time, both concentrated on a small
probability set. Then we have $\mathop{\mathbb{E}}[\mathrm{adv}(f^{\oplus
n}(X,Y)\mid
X_{n},Y_{<n},\mathbf{M})]=\mathop{\mathbb{E}}[\mathrm{adv}(f^{\oplus
n-1}(X_{<n},Y_{<n})\mid X_{n},Y_{<n},\mathbf{M})]$, the advantage may not
increase at all. In this case, the advantage $\mathrm{adv}(f^{\oplus
n}(X,Y)\mid X_{n},Y_{<n},\mathbf{M})$ is also concentrated on the same small
probability set.

On the other hand, observe that if $\mathrm{adv}(f^{\oplus n}(X,Y)\mid
X_{n},Y_{<n},\mathbf{M})$ takes roughly the same value (say, $\varepsilon$)
most of the time, then we do obtain an advantage increase:

$\displaystyle\kern-20.00003pt\mathop{\mathbb{E}}[\mathrm{adv}(f^{\oplus
n-1}(X_{<n},Y_{<n})\mid X_{n},Y_{<n},\mathbf{M})]$
$\displaystyle=\mathop{\mathbb{E}}[\varepsilon/\mathrm{adv}(f(X_{n},Y_{n})\mid
X_{n},Y_{<n},\mathbf{M})]$
$\displaystyle\geq\varepsilon/\mathop{\mathbb{E}}[\mathrm{adv}(f(X_{n},Y_{n})\mid
X_{n},Y_{<n},\mathbf{M})]$

by the convexity of $1/x$.

This motivates us to consider the following two extreme cases:

  1. 1.

$\mathrm{adv}(f^{\oplus n}(X,Y)\mid X_{n},Y_{<n},\mathbf{M})$ is roughly
uniformly distributed among all $(X_{n},Y_{<n},\mathbf{M})$;

  2. 2.

$\mathrm{adv}(f^{\oplus n}(X,Y)\mid X_{n},Y_{<n},\mathbf{M})$ is concentrated
on a tiny fraction of the triples $(X_{n},Y_{<n},\mathbf{M})$.

Basically following what we just argued, the above strategy directly applies
in the first case. The second case is related to the _direct product theorems_
, where we also want to analyze protocols that is correct with exponentially
small probability. This is because one possible strategy for the players is to
compute all $f(X_{i},Y_{i})$ correctly with some probability $\varepsilon$ and
output a random bit otherwise. We must at least show that in this case,
$\varepsilon\leq\exp(-\Omega(n))$.

###  2.3 Generalized protocols

For the second case above, we follow one strategy for direct product theorems
[BRWY13b]. When the advantage $\mathrm{adv}(f^{\oplus n}(X,Y)\mid
X_{n},Y_{<n},\mathbf{M})$ is concentrated on a small set $U$ of triples
$(X_{n},Y_{<n},\mathbf{M})$, we restrict our attention to $U$ by
_conditioning_ $\pi$ on $U$. However, this immediately creates two issues.

The first issue is that although $\pi\mid U$ is a well-defined distribution,
it is not necessarily a _protocol_ , since conditioning on an arbitrary event
may break the independence between a message and the receiver’s input, e.g.,
$M_{1}$ may no longer be independent of $Y$conditioned on $X$.555Conditioning
on an event also distorts the input distribution, which needs to be handled.
But for simplicity, we omit it in the overview.

This issue was also encountered in the direct product theorem proofs. Instead
of studying standard protocols, we focus on _generalized protocols_ , where we
allow each message to depend on both player’s inputs, and we wish to restrict
the correlation between the odd $M_{i}$ and Bob’s input and the correlation
between the even $M_{i}$ and Alice’s input. In the previous work, it bounds

$\theta(\pi):=\sum_{\mathrm{odd}\,i}I(M_{i};Y\mid
X,M_{<i})+\sum_{\mathrm{even}\,i}I(M_{i};X\mid Y,M_{<i}),$

the mutual information between the message and the receiver’s input.

Intuitively, the $\theta$-value measures how close to a standard protocol a
generalized protocol is. It turns out that the $\theta$-value of a standard
protocol conditioned on a not-too-small probability event is small; on the
other hand, when the $\theta$-value is small, it is statistically close to a
standard protocol. Furthermore, an important feature of $\theta(\pi)$ is that
the decomposition of $\pi$ into $\pi_{<n}$ and $\pi_{n}$ also satisfies that
$\theta(\pi)=\theta(\pi_{<n})+\theta(\pi_{n})$. Hence, when doing the
decomposition, we can hope to obtain a generalized protocol for $f$ that is
very close to a standard protocol.

The second issue is that conditioning on a small probability event $U$ could
greatly increase the information cost, from $I$ to $\Omega(I/\Pr[U])$. Since
$I$ is close to the communication cost, such a multiplicative loss in each
step of decomposition is unaffordable. Such a loss occurs because the mutual
information is an average measure (an expectation), which does not provide any
concentration (also recall the counterexample in footnote 4 where the
communication cost and the advantage are both concentrated on an
$\varepsilon$-probability event, when we condition on this event, both the
expected communication cost and the advantage increase by a factor of
$1/\varepsilon$). More specifically, consider the first term in the
information cost, $I(X;\mathbf{M}\mid Y)$ (omit the public random bits for
now). For standard protocols, it is equal to

$\sum_{x,y,\mathbf{m}}\pi(x,y,\mathbf{m})\cdot\log\left(\frac{\pi(x\mid\mathbf{m},y)}{\pi(x\mid
y)}\right)=\mathop{\mathbb{E}}_{\pi}\left[\log\left(\frac{\pi(X\mid\mathbf{M},Y)}{\pi(X\mid
Y)}\right)\right]=\mathop{\mathbb{E}}_{\pi}\left[\log\left(\frac{\pi(X\mid\mathbf{M},Y)}{\mu(X\mid
Y)}\right)\right].$

If we only have a bound on this expectation, then inevitably its value can
greatly increase after conditioning on a small probability event, not to say
that the logarithm inside the expectation is _not_ nonnegative, so it can get
worse than what Markov’s inequality gives.

We also note that the argument in the previous subsections crucially uses the
_rectangle property_ of the communication protocols, which does not
necessarily hold for generalized protocols. This turns out not to be a real
issue, since throughout the argument, we will maintain the rectangle property
_at all leaves_ , which is sufficient for the argument to go through (see also
Section 2.6).

###  2.4 $\theta$-cost and $\chi^{2}$-costs

Our novel solution to the second issue above is to focus on the “exponential
version” of the information cost, i.e., for the first term,

$\chi^{2}_{\mu,A}(\pi):=\mathop{\mathbb{E}}_{\pi}\left[\frac{\pi(X\mid\mathbf{M},Y)}{\mu(X\mid
Y)}\right],$

which we call the $\chi^{2}$-cost by Alice. The $\chi^{2}$-cost by Bob,
$\chi^{2}_{\mu,B}(\pi)$, is defined similarly for the second term in the
information cost (see Definition 15).

This notion of the cost has the following benefits.

  * •

For a (deterministic) standard protocol with $C$ bits of communication,
$\chi^{2}_{\mu,A}(\pi)\leq 2^{C}$. Hence, it corresponds to the exponential of
the communication cost.

  * •

When conditioning on a small probability event $U$, we can essentially ensure
that it increases by a factor of $O(1/\pi(U))$ (Lemma 37 gives a more
generalized statement). Effectively, this only adds $\log(1/\pi(U))$ to the
communication cost, which becomes affordable.

Note that the mutual information is the expected KL-divergence, and the
$\chi^{2}$-cost is the expected $\chi^{2}$-divergence (plus one). Similarly,
we also define an “exponential version” of $\theta(\pi)$, which we call the
$\theta$-cost of $\pi$ (see Definition 12). It also ensures that the value
does not increase significantly when conditioning on a small probability
event.

On the other hand, going from mutual information to its “exponential version”
loses many of its good properties, most importantly, the chain rule. The next
crucial observation is that the chain rule for mutual information in fact
holds _pointwisely_ , which enables us to work with the $\chi^{2}$-costs.

More specifically, let $X,Y,Z$ be three random variables with joint
distribution $\pi$, the chain rules says $I(X;Y,Z)=I(X;Y)+I(X;Z\mid Y)$. By
writing the mutual information as an expectation, this is

$\mathop{\mathbb{E}}\left[\log\left(\frac{\pi(Y,Z\mid
X)}{\pi(Y,Z)}\right)\right]=\mathop{\mathbb{E}}\left[\log\left(\frac{\pi(Y\mid
X)}{\pi(Y)}\right)\right]+\mathop{\mathbb{E}}\left[\log\left(\frac{\pi(Z\mid
X,Y)}{\pi(Z\mid Y)}\right)\right].$

This equality holds pointwisely in the sense that for any concrete values
$(x,y,z)$, the equality holds for the logarithms inside the expectation

$\log\left(\frac{\pi(y,z\mid x)}{\pi(y,z)}\right)=\log\left(\frac{\pi(y\mid
x)}{\pi(y)}\right)+\log\left(\frac{\pi(z\mid x,y)}{\pi(z\mid y)}\right)$

by the definition of conditional probability.

Therefore, the “exponential version” also holds pointwisely:

$\frac{\pi(y,z\mid x)}{\pi(y,z)}=\frac{\pi(y\mid
x)}{\pi(y)}\cdot\frac{\pi(z\mid x,y)}{\pi(z\mid y)}.$

This is what we use in replacement of the chain rule for mutual information.
See the next subsection for more details.

###  2.5 Proof outline

We now give an outline of the proof of the following statement: Given an
$r$-round standard protocol $\pi$ for $f^{\oplus n}$ with communication cost
$o(n\cdot C)$ that succeeds with advantage $\alpha^{o(n)}$ on the inputs
sampled from $\mu^{n}$, we can obtain an $r$-round generalized protocol $\rho$
for $f$ with $\chi^{2}$-costs $\approx 2^{C}$, $\theta$-cost $\approx
1/\alpha$ and advantage $\approx\alpha$. We will then discuss how to convert
such a generalized protocol to a standard protocol with low communication cost
in the next subsection.

We first show that $\pi$ is also a generalized protocol with $\chi^{2}$-cost
$2^{o(nC)}$ and $\theta$-cost $1$ (in the proof of Lemma 25). Next, we
decompose $\pi$ into $\pi_{<n}$ for $f^{\oplus n-1}$ and $\pi_{n}$ for $f$,
and prove that the product of the $\theta$-cost [resp. $\chi^{2}$-costs] of
$\pi_{<n}$ and $\pi_{n}$ is that of $\pi$ pointwisely (Section 5). Now if the
advantage of $\pi$ is not roughly evenly distributed, we will identify an
event $U$ such that the advantage conditioned on $U$ is much higher than the
average advantage, and more importantly, the advantage within $U$ becomes
roughly evenly distributed (not concentrated on any small probability event in
$U$) (Section 6.1). Conditioning on $U$ increases the advantage while also
increases the $\theta$-cost and $\chi^{2}$-costs, it turns out that they all
increase by about the same factor. Next, we partition the sample space of
$\pi$ into $S_{\textnormal{high-cost}},S_{\textnormal{low-cost}}$ and
$S_{\textnormal{low-prob}}$ such that

  * •

in $S_{\textnormal{high-cost}}$, $\pi_{n}$ has high $\theta$-cost or high
$\chi^{2}$-cost (excluding some corner cases), say $\geq 1/\alpha$ for
$\theta$-cost or $\geq 2^{C}$ for $\chi^{2}$-cost,

  * •

in $S_{\textnormal{low-cost}}$, $\pi_{n}$ has low $\theta$-cost and low
$\chi^{2}$-cost (also excluding some corner cases),

  * •

$S_{\textnormal{low-prob}}$ is the rest, which will happen with very low
probability.

Since the advantage is not concentrated on any small probability in $U$, then
(at least) one of $S_{\textnormal{high-cost}}$ or $S_{\textnormal{low-cost}}$
will have advantage about as high as the advantage of $U$. If
$S_{\textnormal{high-cost}}$ has the advantage as high as $U$, then we prove
that by the pointwise equality for the costs, $\pi_{<n}\mid
S_{\textnormal{high-cost}}$ must have a much smaller cost than $\pi\mid U$,
while they have roughly the same advantage (Section 6.2). If
$S_{\textnormal{low-cost}}$ has the advantage as high as $U$, then if
$\pi_{n}\mid S_{\textnormal{low-cost}}$ has high advantage, then we obtain a
desired generalized protocol for $f$ with low costs and high advantage;
otherwise we prove that $\pi_{<n}\mid S_{\textnormal{low-cost}}$ has a much
higher advantage than $\pi\mid U$ (as the advantage of $\pi$ is roughly evenly
distribution within $U$), while they have roughly the same costs (Section
6.3).

To summarize the above argument, if we don’t already find a desired
generalized protocol for $f$, then when decrementing $n$ to $n-1$, we first
condition on an event $U$, increasing costs and advantage simultaneously by
about the same (while arbitrary) factor, then either we reduce the
$\theta$-cost by a factor of $\geq 1/\alpha$, or we reduce the
$\chi^{2}$-costs by a factor of $\geq 2^{C}$, or we increase the advantage by
a factor of $\geq 1/\alpha$. Since we start with $\chi^{2}$-costs $2^{o(nC)}$,
$\theta$-cost $1$ and advantage $\alpha^{o(n)}$, we cannot repeat this for $n$
steps without finding a desired protocol for $f$. More formally, we will
measure the progress by using a potential function that depends on the costs
and advantage of the current protocol, and show that each time we decrement
from $k$ to $k-1$, how much the potential must decrease (Section 4).

###  2.6 Convert a generalized protocol to a standard protocol

Finally, we need to show that the existence of a good generalized protocol
implies the existence of a good standard protocol. We prove that if an
$r$-round generalized protocol $\rho$ has $\chi^{2}$-costs $2^{C}$,
$\theta$-cost $1/\alpha$ and advantage $\alpha$, then there is an $r$-round
standard protocol $\tau$ with communication cost $\approx C$ and advantage
$\approx\alpha^{3}$. Together with what we summarized in the last subsection,
we obtain the strong XOR lemma for $r$-round communication.

[BR11] converts a _standard_ protocol $\rho$ with constant rounds to a
standard protocol with communication matching the internal information cost of
$\rho$. Using a similar argument, we can convert $\rho$ to a standard protocol
with communication $\approx C$. By the convexity of $2^{x}$, $\chi^{2}$-cost
of $2^{C}$ implies internal information cost of at most $C$. It turns out that
the (almost) same argument applies in our case, for generalized protocol
$\rho$.

Then the next crucial observation is that we can ensure the generalized
protocol $\rho$ that we obtain from the arguments in the previous subsection
has the _rectangle property_ with respect to $\mu$. Roughly speaking, it means
that for all transcripts $\mathbf{M}$, if we look at the ratio of the
probabilities $\frac{\rho(X,Y\mid\mathbf{M})}{\mu(X,Y)}$, it is a product
function of $X$ and $Y$, i.e., it is equal to $g_{A}(X)\cdot g_{B}(Y)$ for
some functions $g_{A},g_{B}$ that may depend on $\mathbf{M}$. Note that a
standard protocol has the rectangle property, since each message depends only
on either $X$ or $Y$, and the same property holds even conditioned on any
prefix of the transcript $M_{<i}$. A generalized protocol may not have this
property in general, but we can ensure that the protocol we obtain has this
product structure conditioned on any _complete_ transcript $\mathbf{M}$.

After generating a transcript $\mathbf{M}$ using [BR11], the rectangle
property allows the players to locally “re-adjust” the probabilities (via
rejection sampling) so that after the readjustment, the probability of a
triple $(X,Y,\mathbf{M})$ is proportional to the “right” probability
$\rho(X,Y,\mathbf{M})$, which in turn, gives the advantage proportional to
that of $\rho$.

The probability that is sacrificed in the rejection sampling depends on how
far $\rho$ is from a standard protocol, i.e., the $\theta$-cost of $\rho$. It
turns out that the above argument gives an overall advantage of at least
$\alpha^{2}$ divided by the $\theta$-cost of $\rho$. See Section 7 for the
formal proof.

##  3 Notations and Definitions for Generalized Protocols

###  3.1 Notations and standard probabilities

Throughout the paper, all logarithms have base $2$. We use $[n]$ to denote the
set $\\{1,\ldots,n\\}$. Let
$f:\mathcal{X}\times\mathcal{Y}\rightarrow\\{0,1\\}$ be a binary-valued
function. We use $f^{\oplus n}$ to denote the function $f^{\oplus
n}:\mathcal{X}^{n}\times\mathcal{Y}^{n}\rightarrow\\{0,1\\}$ such that

$f^{\oplus
n}(X_{1},\ldots,X_{n},Y_{1},\ldots,Y_{n})=\bigoplus_{i=1}^{n}f(X_{i},Y_{i}),$

where $\oplus$ is the XOR operation.

Let $X$ be a vector $(X_{1},\ldots,X_{n})$. We denote the prefix
$(X_{1},\ldots,X_{i})$ by $X_{\leq i}$. Similarly, $X_{<i}$ denotes
$(X_{1},\ldots,X_{i-1})$ and $X_{>i}$ denotes $(X_{i+1},\ldots,X_{n})$. For
vectors $X$ where we start the index from $0$, $X_{\leq i}$ denotes
$(X_{0},\ldots,X_{i})$.

Let $\pi$ be a distribution over triples
$(X,Y,\mathbf{M})\in\mathcal{X}\times\mathcal{Y}\times\mathcal{M}$, where
$\mathbf{M}=(M_{0},\ldots,M_{r})$. For an event
$W\subseteq\mathcal{X}\times\mathcal{Y}\times\mathcal{M}$, we use $\pi(W)$ to
denote its probability. For a random variable $\mathbf{M}$, we use
$\pi(\mathbf{M})$ to denote the probability of $\mathbf{M}$ in distribution
$\pi$, which by itself is a random variable that depends on the value of
$\mathbf{M}$. It is similar for multiple variables, e.g., $\pi(X,M_{<i})$
denotes the probability of $(X,M_{<i})$.

Let $S$ be a set of possible values of several variables, say, $S$ is a set of
possible values of $(X,M_{<i})$. We use $\pi(S)$ to denote the probability
that $(X,M_{<i})\in S$, i.e., $\pi(S)=\Pr_{\pi}\left[(X,M_{<i})\in
S\right]=\pi(\\{(X,Y,\mathbf{M}):(X,M_{<i})\in S\\})$. When there is no
ambiguity, we may abuse the notation, and use $S$ to denote the event that
$(X,M_{<i})\in S$, which is the set $\\{(X,Y,\mathbf{M}):(X,M_{<i})\in S\\}$,
e.g., if $T$ is a set of possible values of $(Y,M_{<j})$, then $S\cap T$ is
the event that $(X,M_{<i})\in S\wedge(Y,M_{<j})\in T$, which is the set
$\\{(X,Y,\mathbf{M}):(X,M_{<i})\in S\wedge(Y,M_{<j})\in T\\}$.

The $\chi^{2}$-divergence of two distributions is defined as follows.

######  Definition 3 ($\chi^{2}$-divergence).

Let $P$ and $Q$ be two distributions over a sample space $\mathcal{X}$. The
$\chi^{2}$-divergence from $Q$ to $P$ is

$\mathbf{D}_{\mathrm{\chi^{2}}}(P\,\|\,Q)=\sum_{x\in\mathcal{X}}\frac{P(x)^{2}}{Q(x)}-1=\mathop{\mathbb{E}}_{x\sim
P}\left[\frac{P(x)}{Q(x)}\right]-1.$

The KL-divergence of two distributions is defined as follows.

######  Definition 4 (KL-divergence).

Let $P$ and $Q$ be two distributions over a sample space $\mathcal{X}$. The
KL-divergence from $Q$ to $P$ is

$\mathbf{D}_{\mathrm{KL}}(P\,\|\,Q)=\sum_{x\in\mathcal{X}}P(x)\log\left(\frac{P(x)}{Q(x)}\right)=\mathop{\mathbb{E}}_{x\sim
P}\left[\log\left(\frac{P(x)}{Q(x)}\right)\right].$

A simple calculation gives the following proposition.

######  Proposition 5.

Let $R_{1},R_{2}\in\\{0,1\\}$ be two _independent_ random variables such that
$\Pr[R_{1}=0]=\frac{1}{2}+\frac{\sigma_{1}}{2}$ and
$\Pr[R_{2}=0]=\frac{1}{2}+\frac{\sigma_{2}}{2}$. Then $\Pr[R_{1}\oplus
R_{2}=0]=\frac{1}{2}+\frac{\sigma_{1}\sigma_{2}}{2}$.

###  3.2 Generalized communication protocols

For most standard communication protocols discussed in this paper, we pair it
with an input distribution, and study the joint distribution.

######  Definition 6 (standard protocols).

An $r$-round _standard protocol_ $\pi$ for input distribution $\mu$ is a
distribution over triples

$(X,Y,\mathbf{M})\in\mathcal{X}\times\mathcal{Y}\times\mathcal{M},$

where the transcript $\mathbf{M}=(M_{0},\ldots,M_{r})$, and each $M_{i}$ is
chosen from a prefix-free set of strings that only depends on $M_{<i}$.
Moreover, $(X,Y)\sim\mu$; the public random string $M_{0}$ is independent of
$(X,Y)$; for odd $i\geq 1$, $M_{i}$ (a message by Alice) is independent of $Y$
conditioned on $X$ and $M_{<i}$; for even $i\geq 1$, $M_{i}$ (a message by
Bob) is independent of $X$ conditioned on $Y$ and $M_{<i}$. The output of
$\pi$ is a function of $\mathbf{M}$.

Now we define $\mathrm{suc}_{\mu}(f;C_{A},C_{B},r)$ to be the maximum success
probability of a protocol computing $f$ under the communication cost
constraints.

######  Definition 7.

Let $f:\mathcal{X}\times\mathcal{Y}\rightarrow\\{0,1\\}$ be a function, and
$\mu$ be a distribution over $\mathcal{X}\times\mathcal{Y}$. For
$C_{A},C_{B},r\geq 1$, let

$\mathrm{suc}_{\mu}(f;C_{A},C_{B},r)$

be the supremum over all $r$-round _standard_ protocols $\pi$ where Alice
sends at most $C_{A}$ bits and Bob sends at most $C_{B}$ bits in a round, the
probability that the output of $\pi$ is equal to $f(X,Y)$ when $(X,Y)$ is
sampled from $\mu$.

######  Remark.

Without loss of generality, we may assume that $M_{r}\in\\{0,1\\}$. This is
because the output of the protocol is a function of $\mathbf{M}$. Instead of
$M_{r}$, we could always let Bob send the output, which has only one bit.

Next, we define generalized protocols.

######  Definition 8 (generalized protocols).

An $r$-round _generalized protocol_ $\pi$ is a distribution over triples

$(X,Y,\mathbf{M})\in\mathcal{X}\times\mathcal{Y}\times\mathcal{M},$

where $\mathbf{M}=(M_{0},M_{1},\ldots,M_{r})$, and each $M_{i}$ is chosen from
a prefix-free set of strings that only depends on $M_{<i}$.

In this paper, we also only consider generalized protocols with
$M_{r}\in\\{0,1\\}$.

Clearly, a standard protocol is also a generalized protocol. One still should
think $M_{0}$ as the public random bits, and think $M_{i}$ as a message sent
by Alice if $i$ is odd, and sent by Bob if $i$ is even. The messages and
public random bits are allowed to be arbitrarily correlated with both players’
inputs.

We do not explicitly define the output of a generalized protocol in this
paper. When we study the correctness of a generalized protocol when computing
some function $f$, we characterize it using the _advantage_.

######  Definition 9 (advantage).

Let $\pi$ be a generalized protocol, and $f$ be a binary-valued random
variable (e.g., $f=f(X,Y)$ for
$f:\mathcal{X}\times\mathcal{Y}\rightarrow\\{0,1\\}$). The advantage of $\pi$
for $f$ conditioned on $W$ is

$\mathrm{adv}_{\pi}(f\mid W):=\left|2\pi(f=0\mid
W)-1\right|=\left|2\pi(f=1\mid W)-1\right|.$

We may omit the subscript $\pi$ when there is no ambiguity.

Note that fixing $\pi$ and $f$, $\mathrm{adv}_{\pi}(f\mid W)$ is a function of
$W$. For a standard protocol with input distribution $\mu$, the larges
probability that the output can equal $f$ when the transcript is $\mathbf{M}$
is

$\frac{1}{2}+\frac{1}{2}\cdot\mathrm{adv}_{\pi}(f(X,Y)\mid\mathbf{M}).$

Thus, the overall success probability is always at most

$\frac{1}{2}+\frac{1}{2}\cdot\mathop{\mathbb{E}}_{\mathbf{M}\sim\pi}\left[\mathrm{adv}_{\pi}(f(X,Y)\mid\mathbf{M})\right].$

For general protocols, we will also use
$\mathop{\mathbb{E}}_{\mathbf{M}\sim\pi}\left[\mathrm{adv}_{\pi}(f(X,Y)\mid\mathbf{M})\right]$
to characterize the success probability.

The (conditional) advantage is superadditive when weighted by the probability
of the condition.

######  Lemma 10.

Let $W_{1},W_{2}$ be _disjoint_ events and $\mathbf{R}$ be a set of random
variables, then

$\displaystyle\pi(W_{1}\cup W_{2})\cdot\mathop{\mathbb{E}}_{\pi\mid W_{1}\cup
W_{2}}\left[\mathrm{adv}(f(X,Y)\mid\mathbf{R},W_{1}\cup W_{2})\right]$
$\displaystyle\quad\,\,\leq\pi(W_{1})\cdot\mathop{\mathbb{E}}_{\pi\mid
W_{1}}\left[\mathrm{adv}(f(X,Y)\mid\mathbf{R},W_{1})\right]+\pi(W_{2})\cdot\mathop{\mathbb{E}}_{\pi\mid
W_{2}}\left[\mathrm{adv}(f(X,Y)\mid\mathbf{R},W_{2})\right].$

###### Proof.

By definition, we have

$\displaystyle\kern-20.00003pt\pi(W_{1})\cdot\mathop{\mathbb{E}}_{\pi\mid
W_{1}}\left[\mathrm{adv}(f(X,Y)\mid\mathbf{R},W_{1})\right]+\pi(W_{2})\cdot\mathop{\mathbb{E}}_{\pi\mid
W_{2}}\left[\mathrm{adv}(f(X,Y)\mid\mathbf{R},W_{2})\right]$
$\displaystyle=\pi(W_{1})\cdot\sum_{\mathbf{R}}\pi(\mathbf{R}\mid
W_{1})\cdot\left|2\pi(f(X,Y)=1\mid\mathbf{R},W_{1})-1\right|$
$\displaystyle\qquad+\pi(W_{2})\cdot\sum_{\mathbf{R}}\pi(\mathbf{R}\mid
W_{2})\cdot\left|2\pi(f(X,Y)=1\mid\mathbf{R},W_{2})-1\right|$
$\displaystyle=\sum_{\mathbf{R}}\left|2\pi(f(X,Y)=1,\mathbf{R},W_{1})-\pi(\mathbf{R},W_{1})\right|+\sum_{\mathbf{R}}\left|2\pi(f(X,Y)=1,\mathbf{R},W_{2})-\pi(\mathbf{R},W_{2})\right|$
which by the fact that $W_{1}$ and $W_{2}$ are disjoint, is
$\displaystyle\geq\sum_{\mathbf{R}}\left|2\pi(f(X,Y)=1,\mathbf{R},W_{1}\cup
W_{2})-\pi(\mathbf{R},W_{1}\cup W_{2})\right|$ $\displaystyle=\pi(W_{1}\cup
W_{2})\cdot\mathop{\mathbb{E}}_{\pi\mid W_{1}\cup
W_{2}}\left[\mathrm{adv}(f(X,Y)\mid\mathbf{R},W_{1}\cup W_{2})\right].$

∎

The following proposition states that knowing more could only increase the
expected advantage.

######  Proposition 11.

Let $\mathbf{R}_{1},\mathbf{R}_{2}$ be two random variables, then

$\mathop{\mathbb{E}}_{\mathbf{R}_{1}\sim\pi}\left[\mathrm{adv}(f\mid\mathbf{R}_{1})\right]\leq\mathop{\mathbb{E}}_{\mathbf{R}_{1},\mathbf{R}_{2}\sim\pi}\left[\mathrm{adv}(f\mid\mathbf{R}_{1},\mathbf{R}_{2})\right].$

###### Proof.

We have

$\displaystyle\kern-20.00003pt\mathop{\mathbb{E}}_{\mathbf{R}_{1},\mathbf{R}_{2}\sim\pi}\left[\mathrm{adv}(f\mid\mathbf{R}_{1},\mathbf{R}_{2})\right]$
$\displaystyle=\sum_{\mathbf{R}_{1},\mathbf{R}_{2}}\pi(\mathbf{R}_{1},\mathbf{R}_{2})\cdot\left|2\pi(f=1\mid\mathbf{R}_{1},\mathbf{R}_{2})-1\right|$
$\displaystyle=\sum_{\mathbf{R}_{1}}\pi(\mathbf{R}_{1})\sum_{\mathbf{R}_{2}}\pi(\mathbf{R}_{2}\mid\mathbf{R}_{1})\cdot\left|2\pi(f=1\mid\mathbf{R}_{1},\mathbf{R}_{2})-1\right|$
$\displaystyle\geq\sum_{\mathbf{R}_{1}}\pi(\mathbf{R}_{1})\cdot\left|\sum_{\mathbf{R}_{2}}\pi(\mathbf{R}_{2}\mid\mathbf{R}_{1})\cdot
2\pi(f=1\mid\mathbf{R}_{1},\mathbf{R}_{2})-\sum_{\mathbf{R}_{2}}\pi(\mathbf{R}_{2}\mid\mathbf{R}_{1})\right|$
$\displaystyle=\sum_{\mathbf{R}_{1}}\pi(\mathbf{R}_{1})\cdot\left|2\pi(f=1\mid\mathbf{R}_{1})-1\right|$
$\displaystyle=\mathop{\mathbb{E}}_{\mathbf{R}_{1}\sim\pi}\left[\mathrm{adv}(f\mid\mathbf{R}_{1})\right].$

∎

###  3.3 The $\theta$-cost and $\chi^{2}$-costs

In a standard protocol, Alice’s message must be independent of Bob’s input
conditioned on Alice’s input and the previous messages, and vice versa, while
we allow arbitrary correlation in a generalized protocol. The _$\theta$ -cost_
of a generalized protocol measures this correlation.

######  Definition 12 ($\theta$-cost).

The $\theta$-cost of $\pi$ with respect to $\mu$ at $(X,Y,\mathbf{M})$ is

$\displaystyle\theta_{\mu}(\pi\,@\,X,Y,\mathbf{M})$
$\displaystyle:=\frac{\pi(X,Y\mid
M_{0})}{\mu(X,Y)}\cdot\prod_{\mathrm{odd}\,i\in[r]}\frac{\pi(M_{i}\mid
X,Y,M_{<i})}{\pi(M_{i}\mid
X,M_{<i})}\cdot\prod_{\mathrm{even}\,i\in[r]}\frac{\pi(M_{i}\mid
X,Y,M_{<i})}{\pi(M_{i}\mid Y,M_{<i})}$
$\displaystyle=\frac{\pi(X,Y,\mathbf{M})}{\pi(M_{0})\cdot\mu(X,Y)\cdot\prod_{\mathrm{odd}\,i\in[r]}\pi(M_{i}\mid
X,M_{<i})\cdot\prod_{\mathrm{even}\,i\in[r]}\pi(M_{i}\mid Y,M_{<i})}.$

The $\theta$-cost of $\pi$ with respect to $\mu$ is

$\displaystyle\theta_{\mu}(\pi)$
$\displaystyle:=\mathop{\mathbb{E}}_{(X,Y,\mathbf{M})\sim\pi}\left[\theta_{\mu}(\pi\,@\,X,Y,\mathbf{M})\right].$

For an event $W$, the $\theta$-cost of $\pi$ respect to $\mu$ conditioned on
$W$ is

$\displaystyle\theta_{\mu}(\pi\mid
W):=\mathop{\mathbb{E}}_{(X,Y,\mathbf{M})\sim\pi\mid
W}\left[\theta_{\mu}(\pi\,@\,X,Y,\mathbf{M})\right].$

######  Remark.

We emphasize that $\theta_{\mu}(\pi\mid W)$ is different from
$\theta_{\mu}(\pi_{W})$ for $\pi_{W}$ being the distribution of $\pi$
conditioned on $W$. According to the definitions, although $(X,Y,\mathbf{M})$
is sampled from $\pi\mid W$ in both cases, the quantity inside the expectation
is different. For $\theta_{\mu}(\pi\mid W)$, we still measure the
$\theta$-cost at $(X,Y,\mathbf{M})$ according to distribution $\pi$, while for
$\theta_{\mu}(\pi_{W})$, we measure the $\theta$-cost at $(X,Y,\mathbf{M})$
according to $\pi_{W}$.

######  Remark.

Let $\tau$ be the protocol obtained by “making $\pi$ standard.” That is,
$\tau(X,Y)$ is equal to $\mu(X,Y)$; $\tau(M_{0})$ is $\pi(M_{0})$, independent
of $(X,Y)$. Each odd $M_{i}$ is sampled according to $\pi(M_{i}\mid X,M_{<i})$
independent of $Y$, and each even $M_{i}$ is sampled according to
$\pi(M_{i}\mid Y,M_{<i})$ independent of $X$. Then $\tau$ is a standard
protocol such that

$\tau(X,Y,\mathbf{M})={\pi(M_{0})\cdot\mu(X,Y)\cdot\prod_{\mathrm{odd}\,i\in[r]}\pi(M_{i}\mid
X,M_{<i})\cdot\prod_{\mathrm{even}\,i\in[r]}\pi(M_{i}\mid Y,M_{<i})}.$

The $\theta$-cost of $\pi$ is simply the $\chi^{2}$-divergence from $\tau$ to
$\pi$ plus one.

By the above connection to $\chi^{2}$-divergence, we have the following
proposition.

######  Proposition 13.

For any protocol $\pi$, we have

$\mathop{\mathbb{E}}_{\pi}\left[\theta_{\mu}(\pi\,@\,X,Y,\mathbf{M})^{-1}\right]=1.$

###### Proof.

Let $\tau$ be the protocol by making $\pi$ standard as described in the remark
above. Then we have

$\theta_{\mu}(\pi\,@\,X,Y,\mathbf{M})=\frac{\pi(X,Y,\mathbf{M})}{\tau(X,Y,\mathbf{M})}.$

Therefore,

$\mathop{\mathbb{E}}_{\pi}\left[\theta_{\mu}(\pi\,@\,X,Y,\mathbf{M})^{-1}\right]=\sum_{(X,Y,\mathbf{M})}\pi(X,Y,\mathbf{M})\cdot\frac{\tau(X,Y,\mathbf{M})}{\pi(X,Y,\mathbf{M})}=1.$

∎

By standard bounds on conditional probabilities, we have the following bound
on the conditional cost.

######  Proposition 14.

For events $W_{1},W_{2}$, we have

$\theta_{\mu}(\pi\mid W_{1}\cap W_{2})\leq\frac{\theta_{\mu}(\pi\mid
W_{1})missing}{\pi(W_{2}\mid W_{1})}.$

###### Proof.

Since $\theta_{\mu}(\pi\,@\,X,Y,\mathbf{M})$ is nonnegative, we have

$\displaystyle\theta_{\mu}(\pi\mid W_{1}\cap W_{2})$
$\displaystyle=\mathop{\mathbb{E}}_{(X,Y,\mathbf{M})\sim\pi\mid W_{1}\cap
W_{2}}\left[\theta_{\mu}(\pi\,@\,X,Y,\mathbf{M})\right]$
$\displaystyle=\sum_{(X,Y,\mathbf{M})}\pi(X,Y,\mathbf{M}\mid W_{1}\cap
W_{2})\cdot\theta_{\mu}(\pi\,@\,X,Y,\mathbf{M})$
$\displaystyle\leq\sum_{(X,Y,\mathbf{M})}\frac{\pi(X,Y,\mathbf{M}\mid
W_{1})}{\pi(W_{2}\mid W_{1})}\cdot\theta_{\mu}(\pi\,@\,X,Y,\mathbf{M})$
$\displaystyle=\frac{\theta_{\mu}(\pi\mid W_{1})missing}{\pi(W_{2}\mid
W_{1})}.$

∎

Next, the _$\chi^{2}$ -cost_ measures the “communication cost” of a protocol:
how different Alice’s input becomes in Bob’s view at the end of the
communication compared to that in the input distribution.

######  Definition 15 ($\chi^{2}$-cost).

Let $\pi$ be a generalized protocol, and $\mu$ be a distribution over the
inputs. The $\chi^{2}$-cost of $\pi$ by Alice with respect to $\mu$ at
$(X,Y,\mathbf{M})$ is

$\displaystyle\chi^{2}_{\mu,A}(\pi\,@\,X,Y,\mathbf{M})$
$\displaystyle:=\frac{\pi(X\mid\mathbf{M},Y)}{\mu(X\mid Y)};$

the $\chi^{2}$-cost of $\pi$ by Bob with respect to $\mu$ at
$(X,Y,\mathbf{M})$ is

$\displaystyle\chi^{2}_{\mu,B}(\pi\,@\,X,Y,\mathbf{M})$
$\displaystyle:=\frac{\pi(Y\mid\mathbf{M},X)}{\mu(Y\mid X)}.$

The $\chi^{2}$-costs of $\pi$ with respect to $\mu$ are

$\displaystyle\chi^{2}_{\mu,A}(\pi)$
$\displaystyle:=\mathop{\mathbb{E}}_{(X,Y,\mathbf{M})\sim\pi}\left[\chi^{2}_{\mu,A}(\pi\,@\,X,Y,\mathbf{M})\right],$
$\displaystyle\chi^{2}_{\mu,B}(\pi)$
$\displaystyle:=\mathop{\mathbb{E}}_{(X,Y,\mathbf{M})\sim\pi}\left[\chi^{2}_{\mu,B}(\pi\,@\,X,Y,\mathbf{M})\right].$

For an event $W$, the $\chi^{2}$-costs of $\pi$ with respect to $\mu$
conditioned on $W$ are

$\displaystyle\chi^{2}_{\mu,A}(\pi\mid W)$
$\displaystyle:=\mathop{\mathbb{E}}_{(X,Y,\mathbf{M})\sim\pi\mid
W}\left[\chi^{2}_{\mu,A}(\pi\,@\,X,Y,\mathbf{M})\right],$
$\displaystyle\chi^{2}_{\mu,B}(\pi\mid W)$
$\displaystyle:=\mathop{\mathbb{E}}_{(X,Y,\mathbf{M})\sim\pi\mid
W}\left[\chi^{2}_{\mu,B}(\pi\,@\,X,Y,\mathbf{M})\right].$

######  Remark.

Similar to the $\theta$-cost, $\chi^{2}_{\mu,A}(\pi\mid W)$ is also different
from $\chi^{2}_{\mu,A}(\pi_{W})$. The $\chi^{2}$-cost of $\pi$ by Alice is the
expected $\chi^{2}$-divergence from $\mu_{X\mid Y}$ to $\pi_{X\mid
Y,\mathbf{M}}$ plus one. Similarly, the $\chi^{2}$-cost of $\pi$ by Bob is the
expected $\chi^{2}$-divergence from $\mu_{Y\mid X}$ to $\pi_{Y\mid
X,\mathbf{M}}$ plus one. Observe that for standard protocols, if we measure
the expected KL-divergence instead of the $\chi^{2}$-divergence, then we
obtain the internal information costs:

$\sum_{\mathrm{odd}\,i}I(X;M_{i}\mid
Y,M_{<i})\qquad\textrm{and}\qquad\sum_{\mathrm{even}\,i}I(Y;M_{i}\mid
X,M_{<i}).$

Similar proofs to Proposition 13 and Proposition 14 give us the following two
propositions.

######  Proposition 16.

For any protocol $\pi$, we have

$\mathop{\mathbb{E}}_{\pi}\left[\chi^{2}_{\mu,A}(\pi\,@\,X,Y,\mathbf{M})^{-1}\right]=1,$

and

$\mathop{\mathbb{E}}_{\pi}\left[\chi^{2}_{\mu,B}(\pi\,@\,X,Y,\mathbf{M})^{-1}\right]=1.$

######  Proposition 17.

For any events $W_{1},W_{2}$, we have

$\chi^{2}_{\mu,A}(\pi\mid W_{1}\cap W_{2})\leq\frac{\chi^{2}_{\mu,A}(\pi\mid
W_{1})missing}{\pi(W_{2}\mid W_{1})},$

and

$\chi^{2}_{\mu,B}(\pi\mid W_{1}\cap W_{2})\leq\frac{\chi^{2}_{\mu,B}(\pi\mid
W_{1})missing}{\pi(W_{2}\mid W_{1})}.$

###  3.4 Rectangle properties in generalized protocols

We will maintain the _rectangle property_ for the generalized protocols
throughout the proof.

######  Definition 18 (Rectangle property).

A generalized protocol $\pi$ has the _rectangle property_ with respect to
$\mu$, if there exists nonnegative functions
$g_{1}:\mathcal{X}\times\mathcal{M}\rightarrow\mathbb{R},g_{2}:\mathcal{Y}\times\mathcal{M}\rightarrow\mathbb{R}$
such that

$\pi(X,Y,\mathbf{M})={\mu(X,Y)\cdot g_{1}(X,\mathbf{M})\cdot
g_{2}(Y,\mathbf{M})}.$

Let $W$ be an event, $(\pi\mid W)$ has the rectangle property with respect to
$\mu$ if there exists nonnegative functions
$g_{1}:\mathcal{X}\times\mathcal{M}\rightarrow\mathbb{R},g_{2}:\mathcal{Y}\times\mathcal{M}\rightarrow\mathbb{R}$
such that

$\pi(X,Y,\mathbf{M}\mid W)=\mu(X,Y)\cdot g_{1}(X,\mathbf{M})\cdot
g_{2}(Y,\mathbf{M}).$

Equivalently, $\pi$ has the rectangle property if for every transcript
$\mathbf{M}$, the posterior distribution $\pi_{X,Y\mid\mathbf{M}}$ is equal to
$\mu$ rescaled by some product function with one factor depending only on $X$
and another factor depending only on $Y$. Note that this property holds for
any standard protocol, since each message $M_{i}$ conditioned on $M_{<i}$ only
depends on one of $X$ and $Y$. Hence, for standard protocols, we have such
product structure even conditioned on any prefix $M_{<i}$.

When decomposing a protocol for $k$ instances, we need the following
definition of the _partial rectangle property_.

######  Definition 19 (Partial rectangle property).

Let $\pi$ be a generalized protocol such that $X=(X_{1},\ldots,X_{k})$ and
$Y=(Y_{1},\ldots,Y_{k})$. $\pi$ satisfies the _partial rectangle property_
with respect to $\mu^{k}$ if there exists nonnegative functions
$g_{1},g_{2},g_{3}$ such that

$\pi(X,Y,\mathbf{M})=\mu^{k}(X,Y)\cdot g_{1}(X,\mathbf{M})\cdot
g_{2}(Y,\mathbf{M})\cdot g_{3}(X_{k},Y_{<k},\mathbf{M}).$

Let $W$ be an event, $(\pi\mid W)$ has the partial rectangle property with
respect to $\mu^{k}$ if there exists nonnegative functions $g_{1},g_{2},g_{3}$
such that

$\pi(X,Y,\mathbf{M}\mid W)=\mu^{k}(X,Y)\cdot g_{1}(X,\mathbf{M})\cdot
g_{2}(Y,\mathbf{M})\cdot g_{3}(X_{k},Y_{<k},\mathbf{M}).$

######  Proposition 20.

If $\pi$ has the partial rectangle property, then $X_{<k}$ and $Y_{k}$ are
independent conditioned on $X_{k},Y_{<k},\mathbf{M}$; If $\pi\mid W$ has the
partial rectangle property, then $X_{<k}$ and $Y_{k}$ are independent
conditioned on $X_{k},Y_{<k},\mathbf{M},W$.

###### Proof.

If $\pi$ has the partial rectangle property, then

$\displaystyle\kern-20.00003pt\pi(X_{<k},Y_{k}\mid X_{k},Y_{<k},\mathbf{M})$
$\displaystyle=\mu^{k}(X,Y)\cdot g_{1}(X,\mathbf{M})\cdot
g_{2}(Y,\mathbf{M})\cdot
g_{3}(X_{k},Y_{<k},\mathbf{M})\cdot\pi(X_{k},Y_{<k},\mathbf{M})^{-1}$
$\displaystyle=\left(\mu^{k-1}(X_{<k},Y_{<k})\cdot
g_{1}(X,\mathbf{M})\right)\cdot\left(\mu(X_{k},Y_{k})\cdot
g_{2}(Y,\mathbf{M})\cdot
g_{3}(X_{k},Y_{<k},\mathbf{M})\cdot\pi(X_{k},Y_{<k},\mathbf{M})^{-1}\right).$

Note that given $(X_{k},Y_{<k},\mathbf{M})$, the first factor only depends on
$X_{<k}$, and the second factor only depends on $Y_{k}$. By normalizing the
two factors, we obtain that

$\pi(X_{<k},Y_{k}\mid X_{k},Y_{<k},\mathbf{M})=\pi(X_{<k}\mid
X_{k},Y_{<k},\mathbf{M})\cdot\pi(Y_{k}\mid X_{k},Y_{<k},\mathbf{M}).$

The proof for $\pi\mid W$ is almost identical. We omit the details. ∎

For a protocol $\pi$, we define the follow sets that are related to the
rectangle property and the partial rectangle property.

######  Definition 21.

Let $\mathcal{U}_{X,M}(\pi)$ be the set consisting of all possible pairs
$(X,\mathbf{M})$. Let $\mathcal{U}_{Y,M}(\pi)$ be the set consisting of all
possible pairs $(Y,\mathbf{M})$. Let $\mathcal{U}_{X_{k},Y_{<k},M}(\pi)$ be
the set consisting of all possible triples $(X_{k},Y_{<k},\mathbf{M})$.

Let $\mathcal{S}_{\mathrm{rec}}(\pi)$ be the collection of all possible events
$S$ such that there exist
$S_{X,M}\subseteq\mathcal{U}_{X,M},S_{Y,M}\subseteq\mathcal{U}_{Y,M}$, and

$S=\\{(X,Y,\mathbf{M}):(X,\mathbf{M})\in S_{X,M}\wedge(Y,\mathbf{M})\in
S_{Y,M}\\}.$

Let $\mathcal{S}_{\mathrm{pt}}(\pi)$ be the collection of all possible events
$S$ such that there exist
$S_{X,M}\subseteq\mathcal{U}_{X,M},S_{Y,M}\subseteq\mathcal{U}_{Y,M},S_{X_{k},Y_{<k},M}\subseteq\mathcal{U}_{X_{k},Y_{<k},M}$,
and

$S=\\{(X,Y,\mathbf{M}):(X,\mathbf{M})\in S_{X,M}\wedge(Y,\mathbf{M})\in
S_{Y,M}\wedge(X_{k},Y_{<k},\mathbf{M})\in S_{X_{k},Y_{<k},M}\\}.$

We may omit $\pi$ and use $\mathcal{S}_{\mathrm{rec}}$,
$\mathcal{S}_{\mathrm{pt}}$ when there is no ambiguity.

Intuitively, $\mathcal{S}_{\mathrm{rec}}(\pi)$ is the collection of events
conditioned on which, $\pi$ remains to have the rectangle property. Similarly,
$\mathcal{S}_{\mathrm{pt}}(\pi)$ is the collection of events conditioned on
which, $\pi$ remains to have the partial rectangle property.

######  Proposition 22.

We have the following properties about $\mathcal{S}_{\mathrm{rec}}$ and
$\mathcal{S}_{\mathrm{pt}}$:

  1. (i)

if $\pi$ has the rectangle property, then for any
$S\in\mathcal{S}_{\mathrm{rec}}$, $(\pi\mid S)$ has the rectangle property;

  2. (ii)

if $\pi$ has the partial rectangle property, then for any
$S\in\mathcal{S}_{\mathrm{pt}}$, $(\pi\mid S)$ has the partial rectangle
property;

  3. (iii)

$\mathcal{S}_{\mathrm{rec}}\subseteq\mathcal{S}_{\mathrm{pt}}$;

  4. (iv)

both $\mathcal{S}_{\mathrm{rec}}$ and $\mathcal{S}_{\mathrm{pt}}$ are closed
under intersection.

###### Proof.

For (i), suppose $S=\\{(X,Y,\mathbf{M}):(X,\mathbf{M})\in
S_{X,M}\wedge(Y,\mathbf{M})\in S_{Y,M}\\}$. Then

$\pi(X,Y,\mathbf{M}\mid
S)=\pi(X,Y,\mathbf{M})\cdot\mathbf{1}_{S_{X,M}}(X,\mathbf{M})\cdot\mathbf{1}_{S_{Y,M}}(Y,\mathbf{M})\cdot\pi(S)^{-1}.$

Thus, if $\pi$ has the rectangle property, then $(\pi\mid S)$ has the
rectangle property.

Similarly for (ii), suppose

$S=\\{(X,Y,\mathbf{M}):(X,\mathbf{M})\in S_{X,M}\wedge(Y,\mathbf{M})\in
S_{Y,M}\wedge(X_{k},Y_{<k},\mathbf{M})\in S_{X_{k},Y_{<k},M}\\}.$

Then

$\pi(X,Y,\mathbf{M}\mid
S)=\pi(X,Y,\mathbf{M})\cdot\mathbf{1}_{S_{X,M}}(X,\mathbf{M})\cdot\mathbf{1}_{S_{Y,M}}(Y,\mathbf{M})\cdot\mathbf{1}_{S_{X_{k},Y_{<k},M}}(X_{k},Y_{<k},\mathbf{M})\cdot\pi(S)^{-1}.$

Thus, if $\pi$ has the partial rectangle property, then $(\pi\mid S)$ has the
partial rectangle property.

(iii) and (iv) follow from the definitions. ∎

##  4 Main Setup

In this section, we set up the main framework for proving our main theorems.

###### Theorem 1 (restated).

For any $\\{0,1\\}$-valued function $f$, we have

$\mathbf{R}^{(r)}_{1/2+2^{-n}}(f^{\oplus n})\geq
n\cdot\left(r^{-O(r)}\cdot\mathbf{R}^{(r)}_{2/3}(f)-1\right).$

###### Theorem 2 (restated).

Let $c>0$ be a sufficiently large constant. Fix $\alpha\in(0,r^{-cr})$ and
$C_{A},C_{B}\geq 2c\log(r/\alpha)$. Let
$f:\mathcal{X}\times\mathcal{Y}\rightarrow\\{0,1\\}$ be a function, and $\mu$
be a distribution over $\mathcal{X}\times\mathcal{Y}$. Suppose $f$ satisfies

$\mathrm{suc}_{\mu}({f;C_{A},C_{B},r})\leq 1/2+\alpha/2,$

then for any integer $n\geq 2$, we have

$\mathrm{suc}_{\mu^{n}}(f^{\oplus n};2^{-8}r^{-1}n\cdot
C_{A},2^{-8}r^{-1}n\cdot C_{B},r)\leq\frac{1}{2}+\frac{\alpha^{2^{-12}n}}{2}.$

We first show that Theorem 2 implies Theorem 1.

###### Proof of Theorem 1.

Fix a function $f$, suppose there is an $r$-round protocol $\pi$ for
$f^{\oplus n}$ with communication cost $T$ and success probability
$1/2+2^{-n}$. Let $\alpha=r^{-2cr}$ for a sufficiently large $c$, then $\pi$
has success probability more than $1/2+\alpha^{2^{-12}n}/2$. By setting
$C_{A}=C_{B}=2^{8}r\cdot T/n+2c\log(r/\alpha)=O(r\cdot T/n+r\log r)$, Theorem
2 implies $\mathrm{suc}_{\mu}(f;C_{A},C_{B},r)>1/2+\alpha/2$, i.e., for
distribution $\mu$, there is an $r$-round protocol with communication cost at
most $O(r\cdot T/n+r\log r)$ in each round and success probability at least
$1/2+r^{-O(r)}$.

Since this holds for _any_ $\mu$, by Yao’s minimax lemma, there is an
$r$-round randomized protocol with $O(r\cdot T/n+r\log r)$ communication in
each round and success probability at least $1/2+r^{-O(r)}$ for all inputs. By
simply running such a protocol $r^{O(r)}$ times in parallel and outputting the
majority, we obtain an $r$-round protocol with $r^{O(r)}\cdot(T/n+1)$ total
communication and success probability $2/3$. Thus, we obtain
$\mathbf{R}_{2/3}^{(r)}(f)\leq r^{O(r)}\cdot(\mathbf{R}_{1/2+2^{-n}}(f^{\oplus
n})/n+1)$. Rearranging the terms gives Theorem 1. ∎

In the rest of the paper, we will focus on proving Theorem 2. Let us fix a
sufficiently large constant $c>0$, parameters $C_{A},C_{B},r,\alpha$, function
$f$ and input distribution $\mu$ satisfying its premises. As mentioned in
Section 2, we will first define a potential function based on the costs and
advantage, and then show that the potential function value decreases as we
decrement $n$.

######  Definition 23 (Potential functions).

For an $r$-round generalized protocol $\pi$ for $f^{\oplus n}$ and an event
$W$, we define the potential function $\phi_{n}(\pi\mid W)$ (and
$\phi_{n}^{\mathrm{cost}},\phi_{n}^{\mathrm{adv}}$) as follows:

$\displaystyle\phi_{n}(\pi\mid W)$
$\displaystyle=\underbrace{\log\theta_{\mu^{n}}(\pi\mid
W)+\frac{\log(1/\alpha)}{C_{A}-c\log(r/\alpha)}\cdot\log\chi^{2}_{\mu,A}(\pi\mid
W)+\frac{\log(1/\alpha)}{C_{B}-c\log(r/\alpha)}\cdot\log\chi^{2}_{\mu,B}(\pi\mid
W)missing}_{\phi_{n}^{\mathrm{cost}}(\pi\mid W)}$
$\displaystyle\qquad+\underbrace{32\log\left(\mathop{\mathbb{E}}_{\pi\mid
W}\left[\mathrm{adv}_{\pi}(f^{\oplus
n}(X,Y)\mid\mathbf{M},W)\right]^{-1}\right)}_{\phi_{n}^{\mathrm{adv}}(\pi\mid
W)}.$

We also define $\phi_{n,\mathrm{pt}}(\pi\mid W)$ (and
$\phi_{n,\mathrm{pt}}^{\mathrm{adv}}$) as follows:

$\displaystyle\phi_{n,\mathrm{pt}}(\pi\mid W)$
$\displaystyle=\log\theta_{\mu^{n}}(\pi\mid
W)+\frac{\log(1/\alpha)}{C_{A}-c\log(r/\alpha)}\cdot\log\chi^{2}_{\mu,A}(\pi\mid
W)+\frac{\log(1/\alpha)}{C_{B}-c\log(r/\alpha)}\cdot\log\chi^{2}_{\mu,B}(\pi\mid
W)$ $\displaystyle\qquad+\underbrace{32\log\left(\mathop{\mathbb{E}}_{\pi\mid
W}\left[\mathrm{adv}_{\pi}(f^{\oplus n}(X,Y)\mid
X_{n},Y_{<n},\mathbf{M},W)\right]^{-1}\right)}_{\phi_{n,\mathrm{pt}}^{\mathrm{adv}}(\pi\mid
W)}.$

When $W$ is the whole sample space, we may simply write $\phi_{n}(\pi)$ or
$\phi_{n,\mathrm{pt}}(\pi)$.

The first three terms in both potential functions $\phi_{n}^{\mathrm{cost}}$
are the (normalized) costs of $\pi$. They are small if $\pi$ has low
$\theta$-cost and low $\chi^{2}$-costs. The last term in both potential
functions depends on the expected advantage. $\phi_{n}$ uses the standard
advantage, while $\phi_{n,\mathrm{pt}}$ uses the advantage conditioned not
only on the transcript, but also $X_{n}$ and $Y_{<n}$. As we will see later,
it is used when decomposing $\pi$. The last term is small if the protocol has
high advantage. By Proposition 11, knowing more could only increase the
expected advantage. Hence, $\phi_{n,\mathrm{pt}}(\pi)$ is always at most
$\phi_{n}(\pi)$.

We have the following lower bound on the potential of $\pi$ conditioned on
$W$. In particular, when $W$ is the whole sample space, the potential function
is nonnegative.

######  Lemma 24.

For any $\pi$, event $W$ and any $n\geq 1$, we must have

$\phi_{n}(\pi\mid W)\geq-3\log(1/\pi(W)).$

###### Proof.

For the $\theta$-cost, by the convexity of $1/x$, we have

$\displaystyle\theta_{\mu^{n}}(\pi\mid W)^{-1}$
$\displaystyle=\mathop{\mathbb{E}}_{\pi\mid
W}\left[\theta_{\mu^{n}}(\pi\,@\,X,Y,\mathbf{M})\right]^{-1}$
$\displaystyle\leq\mathop{\mathbb{E}}_{\pi\mid
W}\left[\theta_{\mu^{n}}(\pi\,@\,X,Y,\mathbf{M})^{-1}\right]$ which by the
fact that $\theta_{\mu^{n}}(\pi\,@\,X,Y,\mathbf{M})$ is nonnegative, is
$\displaystyle\leq\pi(W)^{-1}\cdot\mathop{\mathbb{E}}_{\pi}\left[\theta_{\mu^{n}}(\pi\,@\,X,Y,\mathbf{M})^{-1}\right]$
which by Proposition 13, is $\displaystyle=\pi(W)^{-1}.$

Hence, $\log\theta_{\mu^{n}}(\pi\mid W)\geq-\log(1/\pi(W))$. Similarly, we
also have $\log\chi^{2}_{\mu^{n},A}(\pi\mid W)\geq-\log(1/\pi(W))$, and
$\log\chi^{2}_{\mu^{n},B}(\pi\mid W)\geq-\log(1/\pi(W))$. By the fact that
$\log(1/\alpha)\leq C_{A}-c\log(r/\alpha)$ and $\log(1/\alpha)\leq
C_{B}-c\log(r/\alpha)$, we have

$\phi_{n}^{\mathrm{adv}}(\pi\mid W)\geq-3\log(1/\pi(W)).$

The advantage is always at most $1$. Therefore, the last term is nonnegative.
Hence, $\phi_{n}(\pi\mid W)\geq-3\log(1/\pi(W))$. ∎

The following lemma shows an upper bound on the potential of a _deterministic_
standard protocol $\pi$ computing $f^{\oplus n}$.

######  Lemma 25.

Let $\pi$ be a _deterministic_ standard protocol where Alice sends at most
$T_{A}$ bits in each (odd) round and Bob sends at most $T_{B}$ bits in each
(even) round. If it computes $f^{\oplus n}$ with probability
$\frac{1}{2}+\frac{\sigma}{2}$ under input distribution $\mu^{n}$, then

$\phi_{n}(\pi)\leq\lceil
r/2\rceil\cdot\frac{T_{A}\cdot\log(1/\alpha)}{C_{A}-c\log(r/\alpha)}+\lfloor
r/2\rfloor\cdot\frac{T_{B}\cdot\log(1/\alpha)}{C_{B}-c\log(r/\alpha)}+32\log(1/\sigma).$

###### Proof.

By the property of a standard protocol,
$\theta_{\mu^{n}}(\pi\,@\,X,Y,\mathbf{M})=1$ for any $X,Y,\mathbf{M}$ in the
support of $\pi$. Hence, $\log\theta_{\mu^{n}}(\pi)=0$.

For the $\chi^{2}$-cost by Alice, we have

$\displaystyle\chi^{2}_{\mu^{n},A}(\pi)$
$\displaystyle=\mathop{\mathbb{E}}_{(X,Y,\mathbf{M})\sim\pi}\left[\frac{\pi(X\mid\mathbf{M},Y)}{\mu^{n}(X\mid
Y)}\right]$
$\displaystyle=\mathop{\mathbb{E}}_{(X,Y,\mathbf{M})\sim\pi}\left[\frac{\pi(X\mid\mathbf{M},Y)}{\pi(X\mid
Y)}\right]$
$\displaystyle=\sum_{(X,Y,\mathbf{M})}\frac{\pi(X,Y,\mathbf{M})\pi(X\mid\mathbf{M},Y)}{\pi(X\mid
Y)}$ $\displaystyle=\sum_{(X,Y,\mathbf{M})}\pi(\mathbf{M}\mid X,Y)\pi(X\mid
Y,\mathbf{M})\pi(Y).$

Since $\pi$ is a _deterministic_ standard protocol, $M_{0}$ is fixed. All even
messages $(M_{2},M_{4},\ldots)$ are sent by Bob such that each $M_{i}$ is
determined by $M_{<i}$ and $Y$. Therefore, $(M_{2},M_{4},\ldots)$ are
determined by all odd messages $(M_{1},M_{3},\ldots)$ and $Y$. Denote
$(M_{2},M_{4},\ldots)$ by $M_{\mathrm{even}\,}$ and $(M_{1},M_{3},\ldots)$ by
$M_{\mathrm{odd}\,}$, we have

$\displaystyle\quad\,\,\sum_{(X,Y,\mathbf{M})}\pi(\mathbf{M}\mid X,Y)\pi(X\mid
Y,\mathbf{M})\pi(Y)$
$\displaystyle=\sum_{(X,Y,\mathbf{M})}\pi(M_{\mathrm{even}\,}\mid
X,Y,M_{\mathrm{odd}\,})\pi(M_{\mathrm{odd}\,}\mid X,Y)\pi(X\mid
Y,M_{\mathrm{odd}\,},M_{\mathrm{even}\,})\pi(Y)$
$\displaystyle=\sum_{(X,Y,\mathbf{M})}\pi(M_{\mathrm{even}\,}\mid
X,Y,M_{\mathrm{odd}\,})\pi(M_{\mathrm{odd}\,}\mid X,Y)\pi(X\mid
Y,M_{\mathrm{odd}\,})\pi(Y)$
$\displaystyle=\sum_{(X,Y,\mathbf{M})}\pi(M_{\mathrm{odd}\,}\mid
X,Y)\pi(X,M_{\mathrm{even}\,}\mid Y,M_{\mathrm{odd}\,})\pi(Y)$
$\displaystyle\leq\sum_{(X,Y,\mathbf{M})}\pi(X,M_{\mathrm{even}\,}\mid
Y,M_{\mathrm{odd}\,})\pi(Y)$
$\displaystyle=\sum_{(Y,M_{\mathrm{odd}\,})}\pi(Y)$
$\displaystyle=\sum_{M_{\mathrm{odd}\,}}1$ $\displaystyle\leq 2^{\lceil
r/2\rceil T_{A}},$

where the last inequality uses the fact that Alice’s messages have at most
$T_{A}$ bits in each (odd) round. Similarly, we have
$\chi^{2}_{\pi}(\mu,B)\leq 2^{\lfloor r/2\rfloor T_{B}}$.

Finally, by the connection between advantage and success probability,
$\mathop{\mathbb{E}}_{\pi}\left[\mathrm{adv}_{\pi}(f^{\oplus
n}(X,Y)\mid\mathbf{M})\right]\geq\sigma$. Hence,

$\phi_{n}(\pi)\leq\lceil
r/2\rceil\cdot\frac{T_{A}\cdot\log(1/\alpha)}{C_{A}-c\log(r/\alpha)}+\lfloor
r/2\rfloor\cdot\frac{T_{B}\cdot\log(1/\alpha)}{C_{B}-c\log(r/\alpha)}+32\log(1/\sigma).$

∎

In the rest of the paper, we will prove the following lemma, which shows that
given a protocol for $f^{\oplus k}$, we can construct a protocol for
$f^{\oplus k-1}$ with a lower potential.

######  Lemma 26.

For $k\geq 2$,
if there is a generalized protocol $\pi$ for $f^{\oplus k}$ with the rectangle
property with respect to $\mu^{k}$ and an event
$V\in\mathcal{S}_{\mathrm{rec}}(\pi)$ such that $\pi(V)\geq 2^{-12}$,
then there is a generalized protocol $\pi_{\mathrm{new}}$ for $f^{\oplus k-1}$
with the rectangle property with respect to $\mu^{k-1}$ and an event
$V_{\mathrm{new}}\in\mathcal{S}_{\mathrm{rec}}(\pi_{\mathrm{new}})$ such that
$\pi_{\mathrm{new}}(V_{\mathrm{new}})\geq 2^{-12}$, and

$\phi_{k-1}(\pi_{\mathrm{new}}\mid V_{\mathrm{new}})\leq\phi_{k}(\pi\mid
V)-\frac{1}{16}\log(1/\alpha).$

Our main theorem is a direct corollary of Lemma 24, 25 and 26.

###### Proof of Theorem 2.

Since $C_{A},C_{B}\geq 2c\log(r/\alpha)$, $C_{A}/2\leq C_{A}-c\log(r/\alpha)$
and $C_{B}/2\leq C_{B}-c\log(r/\alpha)$. Suppose there exists an $r$-round
protocol $\pi^{(n)}$ where Alice sends at most

$2^{-8}r^{-1}n\cdot C_{A}\leq 2^{-7}r^{-1}n(C_{A}-c\log(r/\alpha))$

bits in each round and Bob sends at most

$2^{-8}r^{-1}n\cdot C_{B}\leq 2^{-7}r^{-1}n(C_{B}-c\log(r/\alpha))$

in each round, which computes $f^{\oplus n}$ correctly with probability
$1/2+\sigma/2$ when the input is sampled from $\mu^{n}$. By fixing the
randomness, we may assume that $\pi^{(n)}$ is deterministic. Then by Lemma 25,
we have

$\phi_{n}(\pi^{(n)})\leq 2^{-7}n\log(1/\alpha)+32\log(1/\sigma).$

Now we set $V^{(n)}$ to be the whole sample space of $\pi^{(n)}$. Clearly,
$\pi^{(n)}$ and $V^{(n)}$ satisfy the premise of Lemma 26. By inductively
applying Lemma 26 a total of $n-1$ times, we obtain a protocol $\pi^{(1)}$ for
$f$ and event $V^{(1)}$ such that $\pi^{(1)}(V^{(1)})\geq 2^{-12}$ and

$\phi_{1}(\pi^{(1)}\mid
V^{(1)})\leq\phi_{n}(\pi^{(n)})-\frac{n-1}{16}\cdot\log(1/\alpha).$

On the other hand, Lemma 24 implies that the LHS is at least
$-3\log(1/\pi^{(1)}(V^{(1)}))\geq-36$, implying that

$\phi_{n}(\pi^{(n)})\geq\frac{n-1}{16}\cdot\log(1/\alpha)-36\geq
2^{-6}n\log(1/\alpha),$

since $n\geq 2$ and $\alpha<r^{-cr}$ for a sufficiently large $c$.

Combining the above upper and lower bounds on $\phi_{n}(\pi^{(n)})$, we obtain

$2^{-7}n\log(1/\alpha)+32\log(1/\sigma)\geq 2^{-6}n\log(1/\alpha),$

implying that $\log(1/\sigma)\geq 2^{-12}n\log(1/\alpha)$, i.e.,

$\sigma\leq\alpha^{2^{-12}n}.$

This proves the theorem. ∎

##  5 Decomposition of Generalized Protocols

To prove Lemma 26, we will decompose a generalized protocol $\pi$ for
$f^{\oplus k}$ into a protocol $\pi_{<k}$ for $f^{\oplus k-1}$ and a protocol
$\pi_{k}$ for $f$ such that the costs of $\pi_{<k}$ and $\pi_{k}$ “add up” to
the costs of $\pi$ pointwisely. For simplicity of notations, we will assume
that _$r$ is even_ from now on, the case of odd $r$ is similar.

###  5.1 Definition of $\pi_{<k}$ and $\pi_{k}$

Fix a generalized protocol $\pi$ with the rectangle property with respect to
$\mu^{k}$. Let $(X,Y,\mathbf{M})\sim\pi$. We view the following tuple as the
$r$-round generalized protocol $\pi_{<k}$ on inputs $(X_{<k},Y_{<k})$

$\left(X_{<k},Y_{<k},\left(M_{0}\circ
X_{k},M_{1},M_{2},\ldots,M_{r-1},M_{r}\right)\right),$

where we append $X_{k}$ to $M_{0}$. We view the following tuple as the
$r$-round generalized protocol $\pi_{k}$ on inputs $(X_{k},Y_{k})$

$\left(X_{k},Y_{k},\left(M_{0},Y_{<k}\circ
M_{1},M_{2},\ldots,M_{r-1},M_{r}\right)\right),$

where we prepend $Y_{<k}$ to $M_{1}$.

It is useful to think that $\pi_{<k}$, $\pi_{k}$ and $\pi$ are the _same_
distribution over the _same_ sample space, only their inputs and transcripts
are defined in different ways. Therefore, we may use
$\pi_{<k}(W),\pi_{k}(W),\pi(W)$ interchangeably when measuring the probability
of an event $W$.

For simplicity of notations, we use $\mathbf{M}^{(\pi_{<k})}$ to denote
$\left(M_{0}\circ X_{k},M_{1},M_{2},\ldots,M_{r}\right)$, the transcript of
$\pi_{<k}$, and use $\mathbf{M}^{(\pi_{k})}$ to denote
$\left(M_{0},Y_{<k}\circ M_{1},M_{2},\ldots,M_{r}\right)$, the transcript of
$\pi_{k}$. $M_{i}^{(\pi_{<k})}$ and $M_{i}^{(\pi_{k})}$ are defined similarly.
Since $(X,Y,\mathbf{M})$ determines $(X_{<k},Y_{<k},\mathbf{M}^{(\pi_{<k})})$,
we define $\theta$-cost of $\pi_{<k}$ at $(X,Y,\mathbf{M})$ as

$\theta_{\mu^{k-1}}(\pi_{<k}\,@\,X,Y,\mathbf{M}):=\theta_{\mu^{k-1}}(\pi_{<k}\,@\,X_{<k},Y_{<k},\mathbf{M}^{(\pi_{<k})}),$

where $(X_{<k},Y_{<k},\mathbf{M}^{(\pi_{<k})})$ is the triple determined by
$(X,Y,\mathbf{M})$. Note that this cost does not depend on $Y_{k}$ given the
other parts of $(X,Y,\mathbf{M})$. The $\chi^{2}$-costs of $\pi_{<k}$ and the
costs of $\pi_{k}$ at $(X,Y,\mathbf{M})$ are defined similarly.

In the remainder of this section, we will analyze $\pi_{<k}$ and $\pi_{k}$.
First, we observe that the partial rectangle property of $\pi$ implies the
rectangle properties of $\pi_{<k}$ and $\pi_{k}$.

######  Proposition 27.

Let $W$ be an event such that $\pi\mid W$ has the partial rectangle property
with respect to $\mu^{k}$. Then $\pi_{<k}\mid W$ has the rectangle property
with respect to $\mu^{k-1}$, and $\pi_{k}\mid W$ has the rectangle property
with respect to $\mu$.

###### Proof.

Since $\pi\mid W$ has the partial rectangle property, there exists
$g_{1},g_{2},g_{3}$ such that

$\pi(X,Y,\mathbf{M}\mid W)=\mu^{k}(X,Y)\cdot g_{1}(X,\mathbf{M})\cdot
g_{2}(Y,\mathbf{M})\cdot g_{3}(X_{k},Y_{<k},\mathbf{M}).$

Thus,

$\displaystyle\pi_{<k}(X_{<k},Y_{<k},\mathbf{M}^{(\pi_{<k})}\mid W)$
$\displaystyle=\pi(X,Y_{<k},\mathbf{M}\mid W)$
$\displaystyle=\sum_{Y_{k}}\mu^{k}(X,Y)\cdot g_{1}(X,\mathbf{M})\cdot
g_{2}(Y,\mathbf{M})\cdot g_{3}(X_{k},Y_{<k},\mathbf{M})$
$\displaystyle=\mu^{k-1}(X_{<k},Y_{<k})\cdot
g_{1}(X,\mathbf{M})\cdot\left(\sum_{Y_{k}}\mu(X_{k},Y_{k})\cdot
g_{2}(Y,\mathbf{M})\cdot g_{3}(X_{k},Y_{<k},\mathbf{M})\right).$

Note that the second factor is a function of only $X_{<k}$ and
$\mathbf{M}^{(\pi_{<k})}$, the third factor is a function of only $Y_{<k}$ and
$\mathbf{M}^{(\pi_{<k})}$.

For $\pi_{k}$, we have

$\displaystyle\pi_{k}(X_{k},Y_{k},\mathbf{M}^{(\pi_{k})}\mid W)$
$\displaystyle=\pi(X_{k},Y,\mathbf{M}\mid W)$
$\displaystyle=\sum_{X_{<k}}\mu^{k}(X,Y)\cdot g_{1}(X,\mathbf{M})\cdot
g_{2}(Y,\mathbf{M})\cdot g_{3}(X_{k},Y_{<k},\mathbf{M})$
$\displaystyle=\mu(X_{k},Y_{k})\cdot\left(\sum_{X_{<k}}g_{1}(X,\mathbf{M})\cdot
g_{3}(X_{k},Y_{<k},\mathbf{M})\right)\cdot g_{2}(Y,\mathbf{M}).$

The second factor depends only on $X_{k}$ and $\mathbf{M}^{(\pi_{k})}$, and
the third factor depends only on $Y_{k}$ and $\mathbf{M}^{(\pi_{k})}$. This
proves the lemma. ∎

Similarly, we have the following relation between
$\mathcal{S}_{\mathrm{rec}}(\pi_{<k}),\mathcal{S}_{\mathrm{rec}}(\pi_{k})$ and
$\mathcal{S}_{\mathrm{pt}}(\pi)$.

######  Proposition 28.

We have
$\mathcal{S}_{\mathrm{rec}}(\pi_{<k})\subseteq\mathcal{S}_{\mathrm{pt}}(\pi)$
and
$\mathcal{S}_{\mathrm{rec}}(\pi_{k})\subseteq\mathcal{S}_{\mathrm{pt}}(\pi)$.

###### Proof.

Let $S\in\mathcal{S}_{\mathrm{rec}}(\pi_{<k})$ be an event such that

$S=\\{(X,Y,\mathbf{M}):(X_{<k},\mathbf{M}^{(\pi_{<k})})\in
S_{X,M}\wedge(Y_{<k},\mathbf{M}^{(\pi_{<k})})\in S_{Y,M}\\},$

for sets $S_{X,M}\in\mathcal{U}_{X,M}(\pi_{<k})$ and
$S_{Y,M}\in\mathcal{U}_{Y,M}(\pi_{<k})$. Hence,

$S=\\{(X,Y,\mathbf{M}):(X,\mathbf{M})\in
S_{X,M}\wedge(X_{k},Y_{<k},\mathbf{M})\in S_{Y,M}\\}$

is a set in $\mathcal{S}_{\mathrm{pt}}(\pi)$.

The proof of
$\mathcal{S}_{\mathrm{rec}}(\pi_{k})\subseteq\mathcal{S}_{\mathrm{pt}}(\pi)$
is similar, and we omit the details. ∎

###  5.2 Decomposition of the costs

Below is the first main lemma of the decomposition, stating that the product
of $\theta$-costs of $\pi_{<k}$ and $\pi_{k}$ is equal to that of $\pi$
pointwisely.

######  Lemma 29.

The product of the $\theta$-costs of $\pi_{<k}$ and $\pi_{k}$ at
$(X,Y,\mathbf{M})$ is $\theta$-cost of $\pi$ at $(X,Y,\mathbf{M})$,

$\theta_{\mu^{k-1}}(\pi_{<k}\,@\,X,Y,\mathbf{M})\cdot\theta_{\mu}(\pi_{k}\,@\,X,Y,\mathbf{M})=\theta_{\mu^{k}}(\pi\,@\,X,Y,\mathbf{M}).$

###### Proof.

By definition, we have

$\displaystyle\kern 12.50002pt\theta_{\mu^{k-1}}(\pi_{<k}\,@\,X,Y,\mathbf{M})$
$\displaystyle=\frac{\pi_{<k}(X_{<k},Y_{<k},\mathbf{M}^{(\pi_{<k})}\mid
M_{0}^{(\pi_{<k})})}{\mu^{k-1}(X_{<k},Y_{<k})}\cdot\prod_{\mathrm{odd}\,i\in[r]}\frac{1}{\pi_{<k}(M_{i}^{(\pi_{<k})}\mid
X_{<k},M_{<i}^{(\pi_{<k})})}\cdot\prod_{\mathrm{even}\,i\in[r]}\frac{1}{\pi_{<k}(M_{i}^{(\pi_{<k})}\mid
Y_{<k},M_{<i}^{(\pi_{<k})})}$ $\displaystyle=\frac{\pi(X,Y_{<k},\mathbf{M}\mid
X_{k},M_{0})}{\mu^{k-1}(X_{<k},Y_{<k})}\cdot\prod_{\mathrm{odd}\,i\in[r]}\frac{1}{\pi(M_{i}\mid
X,M_{<i})}\cdot\prod_{\mathrm{even}\,i\in[r]}\frac{1}{\pi(M_{i}\mid
X_{k},Y_{<k},M_{<i})}$ $\displaystyle=\frac{\pi(X_{<k},Y_{<k},\mathbf{M}\mid
X_{k},M_{0})}{\mu^{k-1}(X_{<k},Y_{<k})}\cdot\prod_{\mathrm{odd}\,i\in[r]}\frac{1}{\pi(M_{i}\mid
X,M_{<i})}\cdot\prod_{\mathrm{even}\,i\in[r]}\frac{1}{\pi(M_{i}\mid
X_{k},Y_{<k},M_{<i})}.$ (2)

Similarly,

$\displaystyle\kern 12.50002pt\theta_{\mu}(\pi_{k}\,@\,X,Y,\mathbf{M})$
$\displaystyle=\frac{\pi_{k}(X_{k},Y_{k},\mathbf{M}^{(\pi_{k})}\mid
M_{0}^{(\pi_{k})})}{\mu(X_{k},Y_{k})}\cdot\prod_{\mathrm{odd}\,i\in[r]}\frac{1}{\pi_{k}(M_{i}^{(\pi_{k})}\mid
X_{k},M_{<i}^{(\pi_{k})})}\cdot\prod_{\mathrm{even}\,i\in[r]}\frac{1}{\pi_{k}(M_{i}^{(\pi_{k})}\mid
Y_{k},M_{<i}^{(\pi_{k})})}$ $\displaystyle=\frac{\pi(X_{k},Y,\mathbf{M}\mid
M_{0})}{\mu(X_{k},Y_{k})}\cdot\frac{1}{\pi(Y_{<k},M_{1}\mid
X_{k},M_{0})}\cdot\prod_{\mathrm{odd}\,i\in[3,r]}\frac{1}{\pi(M_{i}\mid
X_{k},Y_{<k},M_{<i})}\cdot\prod_{\mathrm{even}\,i\in[r]}\frac{1}{\pi(M_{i}\mid
Y,M_{<i})}$ $\displaystyle=\frac{\pi(X_{k},Y,\mathbf{M}\mid
M_{0})}{\mu(X_{k},Y_{k})\cdot\pi(Y_{<k}\mid
X_{k},M_{0})}\cdot\prod_{\mathrm{odd}\,i\in[r]}\frac{1}{\pi(M_{i}\mid
X_{k},Y_{<k},M_{<i})}\cdot\prod_{\mathrm{even}\,i\in[r]}\frac{1}{\pi(M_{i}\mid
Y,M_{<i})}.$ (3)

Combining Equation (2) and (3), we have

$\displaystyle\kern
12.50002pt\theta_{\mu^{k-1}}(\pi_{<k}\,@\,X,Y,\mathbf{M})\cdot\theta_{\mu}(\pi_{k}\,@\,X,Y,\mathbf{M})$
$\displaystyle=\frac{\pi(X_{<k},Y_{<k},\mathbf{M}\mid
X_{k},M_{0})}{\mu^{k-1}(X_{<k},Y_{<k})}\cdot\prod_{\mathrm{odd}\,i\in[r]}\frac{1}{\pi(M_{i}\mid
X,M_{<i})}\cdot\prod_{\mathrm{even}\,i\in[r]}\frac{1}{\pi(M_{i}\mid
X_{k},Y_{<k},M_{<i})}$
$\displaystyle\qquad\qquad\cdot\frac{\pi(X_{k},Y,\mathbf{M}\mid
M_{0})}{\mu(X_{k},Y_{k})\cdot\pi(Y_{<k}\mid
X_{k},M_{0})}\cdot\prod_{\mathrm{odd}\,i\in[r]}\frac{1}{\pi(M_{i}\mid
X_{k},Y_{<k},M_{<i})}\cdot\prod_{\mathrm{even}\,i\in[r]}\frac{1}{\pi(M_{i}\mid
Y,M_{<i})}$ $\displaystyle=\frac{\pi(X_{<k},Y_{<k},\mathbf{M}\mid
X_{k},M_{0})\pi(X_{k},Y,\mathbf{M}\mid M_{0})}{\mu^{k}(X,Y)\pi(Y_{<k}\mid
X_{k},M_{0})}\cdot\frac{1}{\pi(\mathbf{M}\mid X_{k},Y_{<k},M_{0})}$
$\displaystyle\qquad\qquad\cdot\prod_{\mathrm{odd}\,i\in[r]}\frac{1}{\pi(M_{i}\mid
X,M_{<i})}\cdot\prod_{\mathrm{even}\,i\in[r]}\frac{1}{\pi(M_{i}\mid Y,M_{i})}$
$\displaystyle=\frac{\pi(X_{<k}\mid
X_{k},Y_{<k},\mathbf{M})\pi(X_{k},Y,\mathbf{M}\mid
M_{0})}{\mu^{k}(X,Y)}\cdot\prod_{\mathrm{odd}\,i\in[r]}\frac{1}{\pi(M_{i}\mid
X,M_{<i})}\cdot\prod_{\mathrm{even}\,i\in[r]}\frac{1}{\pi(M_{i}\mid
Y,M_{<i})}.$

Then by the rectangle property of $\pi$ and Proposition 20, $Y_{k}$ is
independent of $X_{<k}$ conditioned on $(X_{k},Y_{<k},\mathbf{M})$. It is
equal to

$\displaystyle\kern-20.00003pt\frac{\pi(X_{<k}\mid
X_{k},Y,\mathbf{M})\pi(X_{k},Y,\mathbf{M}\mid
M_{0})}{\mu^{k}(X,Y)}\cdot\prod_{\mathrm{odd}\,i\in[r]}\frac{1}{\pi(M_{i}\mid
X,M_{<i})}\cdot\prod_{\mathrm{even}\,i\in[r]}\frac{1}{\pi(M_{i}\mid
Y,M_{<i})}$ $\displaystyle=\frac{\pi(X,Y,\mathbf{M}\mid
M_{0})}{\mu^{k}(X,Y)}\cdot\prod_{\mathrm{odd}\,i\in[r]}\frac{1}{\pi(M_{i}\mid
X,M_{<i})}\cdot\prod_{\mathrm{even}\,i\in[r]}\frac{1}{\pi(M_{i}\mid
Y,M_{<i})}$ $\displaystyle=\theta_{\mu^{k}}(\pi\,@\,X,Y,\mathbf{M}).$

This proves the lemma. ∎

The second main lemma of the decomposition states that the product of the
$\chi^{2}$-costs of $\pi_{<k}$ and $\pi_{k}$ is also equal to that of $\pi$
pointwisely.

######  Lemma 30.

The product of the $\chi^{2}$-costs of $\pi_{<k}$ and $\pi_{k}$ at
$(X,Y,\mathbf{M})$ is the $\chi^{2}$-cost of $\pi$ at $(X,Y,\mathbf{M})$ by
Alice and Bob respectively,

$\displaystyle\chi^{2}_{\mu^{k-1},A}(\pi_{<k}\,@\,X,Y,\mathbf{M})\cdot\chi^{2}_{\mu,A}(\pi_{k}\,@\,X,Y,\mathbf{M})$
$\displaystyle=\chi^{2}_{\mu^{k},A}(\pi\,@\,X,Y,\mathbf{M}),$
$\displaystyle\chi^{2}_{\mu^{k-1},B}(\pi_{<k}\,@\,X,Y,\mathbf{M})\cdot\chi^{2}_{\mu,B}(\pi_{k}\,@\,X,Y,\mathbf{M})$
$\displaystyle=\chi^{2}_{\mu^{k},B}(\pi\,@\,X,Y,\mathbf{M}).$

###### Proof.

For the $\chi^{2}$-cost by Alice, by definition, we have

$\displaystyle\chi^{2}_{\mu^{k-1},A}(\pi_{<k}\,@\,X,Y,\mathbf{M})$
$\displaystyle=\frac{\pi_{<k}(X_{<k}\mid
Y_{<k},\mathbf{M}^{(\pi_{<k})})}{\mu^{k-1}(X_{<k}\mid Y_{<k})}$
$\displaystyle=\frac{\pi(X_{<k}\mid
X_{k},Y_{<k},\mathbf{M})}{\mu^{k-1}(X_{<k}\mid Y_{<k})},$

and

$\displaystyle\chi^{2}_{\mu,A}(\pi_{k}\,@\,X,Y,\mathbf{M})$
$\displaystyle=\frac{\pi_{k}(X_{k}\mid
Y_{k},\mathbf{M}^{(\pi_{k})})}{\mu(X_{k}\mid Y_{k})}$
$\displaystyle=\frac{\pi(X_{k}\mid Y,\mathbf{M})}{\mu(X_{k}\mid Y_{k})}.$

Hence, by partial rectangle property of $\pi$ and Proposition 20, their
product is equal to

$\displaystyle\kern
12.50002pt\chi^{2}_{\mu^{k-1},A}(\pi_{<k}\,@\,X,Y,\mathbf{M})\cdot\chi^{2}_{\mu,A}(\pi_{k}\,@\,X,Y,\mathbf{M})$
$\displaystyle=\frac{\pi(X_{<k}\mid
X_{k},Y_{<k},\mathbf{M})}{\mu^{k-1}(X_{<k}\mid
Y_{<k})}\cdot\frac{\pi(X_{k}\mid Y,\mathbf{M})}{\mu(X_{k}\mid Y_{k})}$
$\displaystyle=\frac{\pi(X_{<k}\mid X_{k},Y,\mathbf{M})\cdot\pi(X_{k}\mid
Y,\mathbf{M})}{\mu^{k}(X\mid Y)}$ $\displaystyle=\frac{\pi(X\mid
Y,\mathbf{M})}{\mu^{k}(X\mid Y)}$
$\displaystyle=\chi^{2}_{\mu^{k},A}(\pi\,@\,X,Y,\mathbf{M}).$

The $\chi^{2}$-cost for Bob is similar,

$\displaystyle\kern
12.50002pt\chi^{2}_{\mu^{k-1},B}(\pi_{<k}\,@\,X,Y,\mathbf{M})\cdot\chi^{2}_{\mu,B}(\pi_{k}\,@\,X,Y,\mathbf{M})$
$\displaystyle=\frac{\pi(Y_{<k}\mid X,\mathbf{M})}{\mu^{k-1}(Y_{<k}\mid
X_{<k})}\cdot\frac{\pi(Y_{k}\mid X_{k},Y_{<k},\mathbf{M})}{\mu(Y_{k}\mid
X_{k})}$ $\displaystyle=\frac{\pi(Y_{<k}\mid X,\mathbf{M})\cdot\pi(Y_{k}\mid
X,Y_{<k},\mathbf{M})}{\mu^{k}(Y\mid X)}$
$\displaystyle=\chi^{2}_{\mu^{k},B}(\pi\,@\,X,Y,\mathbf{M}).$

This proves the lemma. ∎

##  6 Induction: Proof of Lemma 26

In this section, we will use the decomposition of $\pi$ to prove Lemma 26.

###  6.1 Identify event $U$

As we mentioned in Section 2, to obtain a new protocol for $f^{\oplus k-1}$
from $\pi$, we first identify an event $U$ such that the advantage of $\pi$ is
not concentrated on any $S$ for $S\in\mathcal{S}_{\mathrm{pt}}(\pi)$ and
$S\subseteq U$.

Let $U\in\mathcal{S}_{\mathrm{pt}}(\pi)$ and $U\subseteq V$ be an event that
maximizes

$\pi(U)^{1/2}\cdot\mathop{\mathbb{E}}_{\pi\mid U}\left[\mathrm{adv}(f^{\oplus
k}(X,Y)\mid X_{k},Y_{<k},\mathbf{M},U)\right].$ (4)

Since $\mathcal{S}_{\mathrm{pt}}(\pi)$ is a discrete set, such $U$ exists. If
there is a tie, we fix $U$ to be any maximizer. We first show that
conditioning on $U$ reduces the potential function value, and the reduction is
large when the probability $U$ is small.

######  Lemma 31.

$\pi\mid U$ has the _partial rectangle property_ with respect to $\mu^{k}$,
and

$\phi_{k,\mathrm{pt}}(\pi\mid U)\leq\phi_{k}(\pi\mid V)-13\log(1/\pi(U\mid
V)).$

###### Proof.

By definition, we have

$\displaystyle\phi_{k,\mathrm{pt}}(\pi\mid U)$
$\displaystyle=\log\theta_{\mu^{k}}(\pi\mid
U)+\frac{\log(1/\alpha)}{C_{A}-c\log(r/\alpha)}\cdot\log\chi^{2}_{\mu^{k},A}(\pi\mid
U)+\frac{\log(1/\alpha)}{C_{B}-c\log(r/\alpha)}\cdot\log\chi^{2}_{\mu^{k},B}(\pi\mid
U)$ $\displaystyle\qquad+32\log\left(\mathop{\mathbb{E}}_{\pi\mid
U}\left[\mathrm{adv}_{\pi}(f^{\oplus k}(X,Y)\mid
X_{k},Y_{<k},\mathbf{M},U)\right]^{-1}\right).$

By Proposition 14, Proposition 17 and the fact that $U\subseteq V$, we have

$\displaystyle\log\theta_{\mu^{k}}(\pi\mid U)$
$\displaystyle\leq\log\theta_{\mu^{k}}(\pi\mid V)+\log(1/\pi(U\mid V))$
$\displaystyle\log\chi^{2}_{\mu^{k},A}(\pi\mid U)$
$\displaystyle\leq\log\chi^{2}_{\mu^{k},A}(\pi\mid V)+\log(1/\pi(U\mid V))$
$\displaystyle\log\chi^{2}_{\mu^{k},B}(\pi\mid U)$
$\displaystyle\leq\log\chi^{2}_{\mu^{k},B}(\pi\mid V)+\log(1/\pi(U\mid V)).$

Then since $U$ is the maximizer of Equation (4) and
$V\in\mathcal{S}_{\mathrm{rec}}(\pi)\subseteq\mathcal{S}_{\mathrm{pt}}(\pi)$,

$\displaystyle\kern-20.00003pt\mathop{\mathbb{E}}_{\pi\mid
U}\left[\mathrm{adv}_{\pi}(f^{\oplus k}(X,Y)\mid
X_{k},Y_{<k},\mathbf{M},U)\right]$
$\displaystyle\geq\pi(U)^{-1/2}\cdot\pi(V)^{1/2}\cdot\mathop{\mathbb{E}}_{\pi\mid
V}\left[\mathrm{adv}_{\pi}(f^{\oplus k}(X,Y)\mid
X_{k},Y_{<k},\mathbf{M},V)\right]$ $\displaystyle=\pi(U\mid
V)^{-1/2}\cdot\mathop{\mathbb{E}}_{\pi\mid
V}\left[\mathrm{adv}_{\pi}(f^{\oplus k}(X,Y)\mid
X_{k},Y_{<k},\mathbf{M},V)\right].$

Since knowing less could only decrease the advantage (Proposition 11),

$\mathop{\mathbb{E}}_{\pi\mid V}\left[\mathrm{adv}_{\pi}(f^{\oplus k}(X,Y)\mid
X_{k},Y_{<k},\mathbf{M},V)\right]\geq\mathop{\mathbb{E}}_{\pi\mid
V}\left[\mathrm{adv}_{\pi}(f^{\oplus k}(X,Y)\mid\mathbf{M},V)\right].$

Combining the inequalities and using the fact that
$\log(1/\alpha)<C_{A}-c\log(r/a)$ and $\log(1/\alpha)<C_{B}-c\log(r/a)$, we
have

$\displaystyle\phi_{k,\mathrm{pt}}(\pi\mid U)$
$\displaystyle\leq\log\theta_{\mu^{k}}(\pi\mid
V)+\frac{\log(1/\alpha)}{C_{A}-c\log(r/\alpha)}\cdot\log\chi^{2}_{\mu^{k},A}(\pi\mid
V)+\frac{\log(1/\alpha)}{C_{B}-c\log(r/\alpha)}\cdot\log\chi^{2}_{\mu^{k},B}(\pi\mid
V)$ $\displaystyle\qquad+32\log\left(\mathop{\mathbb{E}}_{\pi\mid
V}\left[f^{\oplus k}(X,Y)\mid\mathbf{M},V\right]^{-1}\right)+3\log(1/\pi(U\mid
V))-16\log(1/\pi(U\mid V))$ $\displaystyle=\phi_{k}(\pi\mid
V)-13\log(1/\pi(U\mid V)).$

This proves the lemma. ∎

We need the following proposition in the later proof.

######  Proposition 32.

We have the following:

  1. (i)

for any $S\in\mathcal{S}_{\mathrm{pt}}(\pi)$ and $S\subseteq U$, we have

$\displaystyle\kern-20.00003pt\pi(S)\cdot\mathop{\mathbb{E}}_{\pi\mid
S}\left[\mathrm{adv}_{\pi}(f^{\oplus k}(X,Y)\mid
X_{k},Y_{<k},\mathbf{M},S)\right]$ $\displaystyle\qquad\leq\pi(S\mid
U)^{1/2}\cdot\pi(U)\cdot\mathop{\mathbb{E}}_{\pi\mid
U}\left[\mathrm{adv}_{\pi}(f^{\oplus k}(X,Y)\mid
X_{k},Y_{<k},\mathbf{M},U)\right].$

  2. (ii)

for any $S\in\mathcal{S}_{\mathrm{pt}}(\pi)$ and $S\subseteq U$, if

$\displaystyle\kern-20.00003pt\pi(U)\cdot\mathop{\mathbb{E}}_{\pi\mid
U}\left[\mathrm{adv}_{\pi}(f^{\oplus k}(X,Y)\mid
X_{k},Y_{<k},\mathbf{M},U)\right]$ $\displaystyle\leq
s\cdot\pi(S)\cdot\mathop{\mathbb{E}}_{\pi\mid
S}\left[\mathrm{adv}_{\pi}(f^{\oplus k}(X,Y)\mid
X_{k},Y_{<k},\mathbf{M},S)\right],$

for some $s\geq 1$, then for any $t\leq 32$, we have

$\phi_{k,\mathrm{pt}}^{\mathrm{adv}}(\pi\mid
U)+t\log(1/\pi(U))\geq\phi_{k,\mathrm{pt}}^{\mathrm{adv}}(\pi\mid
S)+t\log(1/\pi(S))-32\log s.$

###### Proof.

  1. (i)

Since $U$ is the maximizer of Equation (4),
$S\in\mathcal{S}_{\mathrm{pt}}(\pi)$ and $S\subseteq U$, we have

$\displaystyle\kern-20.00003pt\pi(S)\cdot\mathop{\mathbb{E}}_{\pi\mid
S}\left[\mathrm{adv}_{\pi}(f^{\oplus k}(X,Y)\mid
X_{k},Y_{<k},\mathbf{M},S)\right]$
$\displaystyle\leq\pi(S)^{1/2}\cdot\pi(U)^{1/2}\cdot\mathop{\mathbb{E}}_{\pi\mid
U}\left[\mathrm{adv}_{\pi}(f^{\oplus k}(X,Y)\mid
X_{k},Y_{<k},\mathbf{M},U)\right]$ $\displaystyle=\pi(S\mid
U)^{1/2}\cdot\pi(U)\cdot\mathop{\mathbb{E}}_{\pi\mid
U}\left[\mathrm{adv}_{\pi}(f^{\oplus k}(X,Y)\mid
X_{k},Y_{<k},\mathbf{M},U)\right].$

  2. (ii)

By taking the logarithm on both sides of the premise, we have

$\displaystyle\kern-20.00003pt\log\left(\mathop{\mathbb{E}}_{\pi\mid
U}\left[\mathrm{adv}_{\pi}(f^{\oplus k}(X,Y)\mid
X_{k},Y_{<k},\mathbf{M},U)\right]^{-1}\right)+\log(1/\pi(U))$
$\displaystyle\geq\log\left(\mathop{\mathbb{E}}_{\pi\mid
S}\left[\mathrm{adv}_{\pi}(f^{\oplus k}(X,Y)\mid
X_{k},Y_{<k},\mathbf{M},S)\right]^{-1}\right)+\log(1/\pi(S))-\log s,$

i.e., (recall Definition 23)

$\phi_{k,\mathrm{pt}}^{\mathrm{adv}}(\pi\mid
U)+32\log(1/\pi(U))\geq\phi_{k,\mathrm{pt}}^{\mathrm{adv}}(\pi\mid
S)+32\log(1/\pi(S))-32\log s.$

Since $\pi(U)\geq\pi(S)$, for any $t\leq 32$,

$\phi_{k,\mathrm{pt}}^{\mathrm{adv}}(\pi\mid
U)+t\log(1/\pi(U))\geq\phi_{k,\mathrm{pt}}^{\mathrm{adv}}(\pi\mid
S)+t\log(1/\pi(S))-32\log s.$

∎

Now we will divide the set of all $(X_{k},Y_{<k},\mathbf{M})$ with nonzero
probability under $\pi$ into subsets based on the costs and the advantages of
$\pi_{<k}$ and $\pi_{k}$. Then we show that for each subset, there is a way to
construct a generalized protocol for $f^{\oplus k-1}$ such that at least one
of the protocols satisfies the requirements of Lemma 26. To analyze the costs
of these protocols, which we will construct later in this section, we need the
following two lemmas.

######  Lemma 33.

Fix a set $S$ of triples $(X_{k},Y_{<k},\mathbf{M})$ and a parameter $\eta>0$.
If for all $(X_{k},Y_{<k},\mathbf{M})\in S$,

$\mathop{\mathbb{E}}_{Y_{k}\sim\pi\mid
X_{k},Y_{<k},\mathbf{M},U}\left[\theta_{\mu}(\pi_{k}\,@\,X_{k},Y_{k},\mathbf{M}^{(\pi_{k})})\right]\geq\eta,$

then we have

$\log\theta_{\mu^{k-1}}(\pi_{<k}\mid S\cap U)\leq\log\theta_{\mu^{k}}(\pi\mid
U)+\log(1/\pi(S\mid U))-\log\eta,$

where we abused the notation to let $S$ also denote the set
$\\{(X,Y,\mathbf{M}):(X_{k},Y_{<k},\mathbf{M})\in S\\}$.

###### Proof.

By Lemma 29, we have

$\displaystyle\quad\,\,\theta_{\mu^{k}}(\pi\mid S\cap U)$
$\displaystyle=\mathop{\mathbb{E}}_{\pi}\left[\theta_{\mu^{k}}(\pi\,@\,X,Y,\mathbf{M})\mid
S\cap U\right]$
$\displaystyle=\mathop{\mathbb{E}}_{\pi}\left[\theta_{\mu^{k-1}}(\pi_{<k}\,@\,X,Y,\mathbf{M})\cdot\theta_{\mu}(\pi_{k}\,@\,X,Y,\mathbf{M})\mid
S\cap U\right].$

By the construction of $\pi_{<k}$ and $\pi_{k}$,
$\theta_{\mu^{k-1}}(\pi_{<k}\,@\,X,Y,\mathbf{M})$ is a function of
$(X,Y_{<k},\mathbf{M})$ and does not depend on $Y_{k}$, and
$\theta_{\mu}(\pi_{k}\,@\,X_{k},Y,\mathbf{M})$ is a function of
$(X_{k},Y,\mathbf{M})$ does not depend on $X_{<k}$. Thus, it is equal to

$\mathop{\mathbb{E}}_{\pi}\left[\theta_{\mu^{k-1}}(\pi_{<k}\,@\,X,Y_{<k},\mathbf{M})\cdot\theta_{\mu}(\pi_{k}\,@\,X_{k},Y,\mathbf{M})\mid
S\cap U\right].$

Since $\mathcal{S}_{\mathrm{pt}}$ is closed under intersection and
$S\in\mathcal{S}_{\mathrm{pt}}$ by definition, we have that $S\cap
U\in\mathcal{S}_{\mathrm{pt}}$. Hence, $\pi\mid S\cap U$ has the partial
rectangle property by Proposition 22(ii). Then $X_{<k}$ and $Y_{k}$ are
independent conditioned on $(X_{k},Y_{<k},\mathbf{M},S\cap U)$ by Proposition
20. Hence, it is equal to

$\displaystyle\kern
12.50002pt\mathop{\mathbb{E}}_{(X_{k},Y_{<k},\mathbf{M})\sim\pi\mid S\cap
U}\left[\mathop{\mathbb{E}}_{X_{<k}\sim\pi\mid X_{k},Y_{<k},\mathbf{M},S\cap
U}[\theta_{\mu^{k-1}}(\pi_{<k}\,@\,X,Y_{<k},\mathbf{M})]\cdot\mathop{\mathbb{E}}_{Y_{k}\sim\pi\mid
X_{k},Y_{<k},\mathbf{M},S\cap
U}[\theta_{\mu}(\pi_{k}\,@\,X_{k},Y,\mathbf{M})]\right]$
$\displaystyle=\mathop{\mathbb{E}}_{(X_{k},Y_{<k},\mathbf{M})\sim\pi\mid S\cap
U}\left[\mathop{\mathbb{E}}_{X_{<k}\sim\pi\mid X_{k},Y_{<k},\mathbf{M},S\cap
U}[\theta_{\mu^{k-1}}(\pi_{<k}\,@\,X_{<k},Y_{<k},\mathbf{M}^{(\pi_{<k})})]\right.$
$\displaystyle\hskip 150.0pt\times\left.\mathop{\mathbb{E}}_{Y_{k}\sim\pi\mid
X_{k},Y_{<k},\mathbf{M},S\cap
U}[\theta_{\mu}(\pi_{k}\,@\,X_{k},Y_{k},\mathbf{M}^{(\pi_{k})})]\right].$

Since $S$ is a set of triples $(X_{k},Y_{<k},\mathbf{M})$, $(\pi\mid
X_{k},Y_{<k},\mathbf{M},S\cap U)$ is the same as $(\pi\mid
X_{k},Y_{<k},\mathbf{M},U)$ (for $(X_{k},Y_{<k},\mathbf{M})\in S$). It is
equal to

$\displaystyle\kern
12.50002pt\mathop{\mathbb{E}}_{(X_{k},Y_{<k},\mathbf{M})\sim\pi\mid S\cap
U}\left[\mathop{\mathbb{E}}_{X_{<k}\sim\pi\mid X_{k},Y_{<k},\mathbf{M},S\cap
U}[\theta_{\mu^{k-1}}(\pi_{<k}\,@\,X_{<k},Y_{<k},\mathbf{M}^{(\pi_{<k})})]\right.$
$\displaystyle\hskip 150.0pt\times\left.\mathop{\mathbb{E}}_{Y_{k}\sim\pi\mid
X_{k},Y_{<k},\mathbf{M},U}[\theta_{\mu}(\pi_{k}\,@\,X_{k},Y_{k},\mathbf{M}^{(\pi_{k})})]\right]$
$\displaystyle\geq\mathop{\mathbb{E}}_{(X_{k},Y_{<k},\mathbf{M})\sim\pi\mid
S\cap U}\left[\mathop{\mathbb{E}}_{X_{<k}\sim\pi\mid
X_{k},Y_{<k},\mathbf{M},S\cap
U}[\theta_{\mu^{k-1}}(\pi_{<k}\,@\,X_{<k},Y_{<k},\mathbf{M}^{(\pi_{<k})})]\cdot\eta\right]$
$\displaystyle=\theta_{\mu^{k-1}}(\pi_{<k}\mid S\cap U)\cdot\eta.$

Finally, by Proposition 14,

$\theta_{\mu^{k}}(\pi\mid S\cap U)\leq\frac{\theta_{\mu^{k}}(\pi\mid
U)missing}{\pi(S\mid U)}.$

Hence, we have

$\log\theta_{\mu^{k-1}}(\pi_{<k}\mid S\cap U)\leq\log\theta_{\mu^{k}}(\pi\mid
U)+\log(1/\pi(S\mid U))-\log\eta.$

This proves the lemma. ∎

Next, by applying Lemma 30 and Proposition 17 instead of Lemma 29 and
Proposition 14, the same proof gives the following lemma for the
$\chi^{2}$-costs.

######  Lemma 34.

Fix a set $S$ of triples $(X_{k},Y_{<k},\mathbf{M})$ and a parameter $\eta>0$.
If for all $(X_{k},Y_{<k},\mathbf{M})\in S$,

$\mathop{\mathbb{E}}_{Y_{k}\sim\pi\mid
X_{k},Y_{<k},\mathbf{M},U}\left[\chi^{2}_{\mu,A}(\pi_{k}\,@\,X_{k},Y_{k},\mathbf{M}^{(\pi_{k})})\right]\geq\eta,$

then we have

$\log\chi^{2}_{\mu^{k-1},A}(\pi_{<k}\mid S\cap
U)\leq\log\chi^{2}_{\mu^{k},A}(\pi\mid U)+\log(1/\pi(S\mid U))-\log\eta;$

similarly, if for all $(X_{k},Y_{<k},\mathbf{M})\in S$,

$\mathop{\mathbb{E}}_{Y_{k}\sim\pi\mid
X_{k},Y_{<k},\mathbf{M},U}\left[\chi^{2}_{\mu,B}(\pi_{k}\,@\,X_{k},Y_{k},\mathbf{M}^{(\pi_{k})})\right]\geq\eta,$

then we have

$\log\chi^{2}_{\mu^{k-1},B}(\pi_{<k}\mid S\cap
U)\leq\log\chi^{2}_{\mu^{k},B}(\pi\mid U)+\log(1/\pi(S\mid U))-\log\eta.$

We will also need the following lemma to relate the advantage for $f^{\oplus
k-1}$ to the advantage for $f^{\oplus k}$.

######  Lemma 35.

Fix a set $S\in\mathcal{S}_{\mathrm{pt}}(\pi)$ such that $\pi(S\cap U)>0$.
Suppose there exists $b\in\\{0,1\\}$ such that for any
$(X_{k},Y_{<k},\mathbf{M})$ with $\pi(X_{k},Y_{<k},\mathbf{M},S\cap U)>0$, we
have

$\pi(f^{\oplus k-1}(X_{<k},Y_{<k})=b\mid X_{k},Y_{<k},\mathbf{M},S\cap U)\geq
1/2.$

Then we have

$\mathop{\mathbb{E}}_{\pi\mid S\cap U}\left[\mathrm{adv}_{\pi}(f^{\oplus
k-1}(X_{<k},Y_{<k})\mid\mathbf{M}^{(\pi_{<k})},S\cap
U)\right]\geq\mathop{\mathbb{E}}_{\pi\mid S\cap
U}\left[\mathrm{adv}_{\pi}(f^{\oplus k}(X,Y)\mid X_{k},Y_{<k},\mathbf{M},S\cap
U)\right].$

Moreover, if we further have

$\mathop{\mathbb{E}}_{\pi\mid S\cap
U}\left[\mathrm{adv}_{\pi}(f(X_{k},Y_{k})\mid X_{k},Y_{<k},\mathbf{M},S\cap
U)\right]\leq\eta,$

for

$\eta^{1/4}\leq\frac{1}{2}\cdot\frac{\pi(S\cap
U)^{1/2}\cdot\mathop{\mathbb{E}}_{\pi\mid S\cap
U}\left[\mathrm{adv}_{\pi}(f^{\oplus k}(X,Y)\mid X_{k},Y_{<k},\mathbf{M},S\cap
U)\right]}{\pi(U)^{1/2}\cdot\mathop{\mathbb{E}}_{\pi\mid
U}\left[\mathrm{adv}_{\pi}(f^{\oplus k}(X,Y)\mid
X_{k},Y_{<k},\mathbf{M},U)\right]},$

then we have

$\displaystyle\kern-20.00003pt\mathop{\mathbb{E}}_{\pi\mid S\cap
U}\left[\mathrm{adv}_{\pi}(f^{\oplus
k-1}(X_{<k},Y_{<k})\mid\mathbf{M}^{(\pi_{<k})},S\cap U)\right]$
$\displaystyle\geq\frac{1}{2}\eta^{-1/2}\cdot\mathop{\mathbb{E}}_{\pi\mid
S\cap U}\left[\mathrm{adv}_{\pi}(f^{\oplus k}(X,Y)\mid
X_{k},Y_{<k},\mathbf{M},S\cap U)\right].$

The first condition $\pi(f^{\oplus k-1}(X_{<k},Y_{<k})=b\mid
X_{k},Y_{<k},\mathbf{M},S\cap U)\geq 1/2$ is used to ensure that the expected
advantage conditioned on $(\mathbf{M}^{(\pi_{<k})},S\cap U)$ is the same as
the expected advantage conditioned on $(Y_{<k},\mathbf{M}^{(\pi_{<k})},S\cap
U)$.

###### Proof.

We have

$\displaystyle\kern 12.50002pt\mathrm{adv}_{\pi}(f^{\oplus
k-1}(X_{<k},Y_{<k})\mid\mathbf{M}^{(\pi_{<k})},S\cap U)$
$\displaystyle=\mathrm{adv}_{\pi}(f^{\oplus k-1}(X_{<k},Y_{<k})\mid
X_{k},\mathbf{M},S\cap U)$ $\displaystyle=\left|2\pi(f^{\oplus
k-1}(X_{<k},Y_{<k})=b\mid X_{k},\mathbf{M},S\cap U)-1\right|$
$\displaystyle=\left|2\sum_{Y_{<k}}\pi(Y_{<k}\mid X_{k},\mathbf{M},S\cap
U)\cdot\pi(f^{\oplus k-1}(X_{<k},Y_{<k})=b\mid X_{k},Y_{<k},\mathbf{M},S\cap
U)-1\right|$ $\displaystyle=\left|\sum_{Y_{<k}}\pi(Y_{<k}\mid
X_{k},\mathbf{M},S\cap U)\cdot(2\pi(f^{\oplus k-1}(X_{<k},Y_{<k})=b\mid
X_{k},Y_{<k},\mathbf{M},S\cap U)-1)\right|.$

By the assumption that $\pi(f^{\oplus k-1}(X_{<k},Y_{<k})=b\mid
X_{k},Y_{<k},\mathbf{M},S\cap U)\geq 1/2$, the absolute value of the sum is
equal to the sum of absolute values:

$\displaystyle\kern-20.00003pt\left|\sum_{Y_{<k}}\pi(Y_{<k}\mid
X_{k},\mathbf{M},S\cap U)\cdot(2\pi(f^{\oplus k-1}(X_{<k},Y_{<k})=b\mid
X_{k},Y_{<k},\mathbf{M},S\cap U)-1)\right|$
$\displaystyle=\sum_{Y_{<k}}\pi(Y_{<k}\mid X_{k},\mathbf{M},S\cap
U)\cdot\left|2\pi(f^{\oplus k-1}(X_{<k},Y_{<k})=b\mid
X_{k},Y_{<k},\mathbf{M},S\cap U)-1\right|$
$\displaystyle=\mathop{\mathbb{E}}_{Y_{<k}\sim\pi\mid X_{k},\mathbf{M},S\cap
U}\left[\mathrm{adv}_{\pi}(f^{\oplus k-1}(X_{<k},Y_{<k})\mid
X_{k},Y_{<k},\mathbf{M},S\cap U)\right].$

By taking the expectation over $(X_{k},\mathbf{M})$ conditioned on $S\cap U$,
we obtain

$\displaystyle\kern-20.00003pt\mathop{\mathbb{E}}_{\pi\mid{S\cap
U}}\left[\mathrm{adv}_{\pi}(f^{\oplus
k-1}(X_{<k},Y_{<k})\mid\mathbf{M}^{(\pi_{<k})},S\cap U)\right]$
$\displaystyle=\mathop{\mathbb{E}}_{\pi\mid S\cap
U}\left[\mathrm{adv}_{\pi}(f^{\oplus k-1}(X_{<k},Y_{<k})\mid
X_{k},Y_{<k},\mathbf{M},S\cap U)\right].$ (5)

Since $S,U\in\mathcal{S}_{\mathrm{pt}}(\pi)$, we have $S\cap
U\in\mathcal{S}_{\mathrm{pt}}(\pi)$. Therefore, $X_{<k}$ and $Y_{k}$ are
independent conditioned on $(X_{k},Y_{<k},\mathbf{M},S\cap U)$ by Proposition
22(ii) and Proposition 20. In particular, $f^{\oplus k-1}(X_{<k},Y_{<k})$ and
$f(X_{k},Y_{k})$ are independent conditioned on
$(X_{k},Y_{<k},\mathbf{M},S\cap U)$. By the fact that $f(X,Y)=f^{\oplus
k-1}(X_{<k},Y_{<k})\oplus f(X_{k},Y_{k})$ and Proposition 5, we have

$\displaystyle\kern-20.00003pt\mathrm{adv}_{\pi}(f^{\oplus k}(X,Y)\mid
X_{k},Y_{<k},\mathbf{M},S\cap U)$ $\displaystyle=\mathrm{adv}_{\pi}(f^{\oplus
k-1}(X_{<k},Y_{<k})\mid X_{k},Y_{<k},\mathbf{M},S\cap
U)\cdot\mathrm{adv}_{\pi}(f(X,Y)\mid X_{k},Y_{<k},\mathbf{M},S\cap U)$ (6)
$\displaystyle\leq\mathrm{adv}_{\pi}(f^{\oplus k-1}(X_{<k},Y_{<k})\mid
X_{k},Y_{<k},\mathbf{M},S\cap U).$

Thus, the expected advantage is at least

$\displaystyle\kern-20.00003pt\mathop{\mathbb{E}}_{\pi\mid{S\cap
U}}\left[\mathrm{adv}_{\pi}(f^{\oplus
k-1}(X_{<k},Y_{<k})\mid\mathbf{M}^{(\pi_{<k})},S\cap U)\right]$
$\displaystyle\geq\mathop{\mathbb{E}}_{\pi\mid S\cap
U}\left[\mathrm{adv}_{\pi}(f^{\oplus k}(X,Y)\mid X_{k},Y_{<k},\mathbf{M},S\cap
U)\right].$

This proves the first part of the lemma.

For the second part, let $T$ be the set of all triples
$(X_{k},Y_{<k},\mathbf{M})$ such that

$\pi(X_{k},Y_{<k},\mathbf{M},S\cap U)>0$

and

$\mathrm{adv}_{\pi}(f(X_{k},Y_{k})\mid X_{k},Y_{<k},\mathbf{M},S\cap
U)\geq\eta^{1/2}.$

Then by Markov’s inequality, if we have

$\mathop{\mathbb{E}}_{\pi\mid S\cap
U}\left[\mathrm{adv}_{\pi}(f(X_{k},Y_{k})\mid X_{k},Y_{<k},\mathbf{M},S\cap
U)\right]\leq\eta,$

then $\pi(T\mid S\cap U)\leq\eta^{1/2}$.

Hence, for $(X_{k},Y_{<k},\mathbf{M})\notin T$ and
$\pi(X_{k},Y_{<k},\mathbf{M},S\cap U)>0$, Equation (6) implies that

$\displaystyle\kern-20.00003pt\mathrm{adv}_{\pi}(f^{\oplus k}(X,Y)\mid
X_{k},Y_{<k},\mathbf{M},S\cap U)$
$\displaystyle\leq\eta^{1/2}\cdot\mathrm{adv}_{\pi}(f^{\oplus
k-1}(X_{<k},Y_{<k})\mid X_{k},Y_{<k},\mathbf{M},S\cap U).$

Hence, we have

$\displaystyle\kern-20.00003pt\mathop{\mathbb{E}}_{\pi\mid S\cap
U}\left[\mathrm{adv}_{\pi}(f^{\oplus k-1}(X_{<k},Y_{<k})\mid
X_{k},Y_{<k},\mathbf{M},S\cap U)\right]$
$\displaystyle\geq\sum_{(X_{k},Y_{<k},\mathbf{M})\notin
T}\pi(X_{k},Y_{<k},\mathbf{M}\mid S\cap U)\cdot\mathrm{adv}_{\pi}(f^{\oplus
k-1}(X_{<k},Y_{<k})\mid X_{k},Y_{<k},\mathbf{M},S\cap U)$
$\displaystyle\geq\eta^{-1/2}\cdot\sum_{(X_{k},Y_{<k},\mathbf{M})\notin
T}\pi(X_{k},Y_{<k},\mathbf{M}\mid S\cap U)\cdot\mathrm{adv}_{\pi}(f^{\oplus
k}(X,Y)\mid X_{k},Y_{<k},\mathbf{M},S\cap U)$
$\displaystyle\geq\eta^{-1/2}\cdot\mathop{\mathbb{E}}_{\pi\mid S\cap
U}\left[\mathrm{adv}_{\pi}(f^{\oplus k}(X,Y)\mid X_{k},Y_{<k},\mathbf{M},S\cap
U)\right]$ $\displaystyle\qquad-\eta^{-1/2}\cdot\pi(T\mid S\cap
U)\cdot\mathop{\mathbb{E}}_{\pi\mid T\cap S\cap
U}\left[\mathrm{adv}_{\pi}(f^{\oplus k}(X,Y)\mid X_{k},Y_{<k},\mathbf{M},S\cap
U)\right].$

Next we show that (the absolute value of) the second term is at most half of
the first term. First since $T$ is a set of $(X_{k},Y_{<k},\mathbf{M})$, we
have

$\mathrm{adv}_{\pi}(f^{\oplus k}(X,Y)\mid X_{k},Y_{<k},\mathbf{M},S\cap
U)=\mathrm{adv}_{\pi}(f^{\oplus k}(X,Y)\mid X_{k},Y_{<k},\mathbf{M},T\cap
S\cap U)$

for any $(X_{k},Y_{<k},\mathbf{M})\in T$. Hence, by the fact that $T\cap S\cap
U\in\mathcal{S}_{\mathrm{pt}}(\pi)$ and $U$ maximizes Equation (4), we have
that

$\displaystyle\kern 12.50002pt\pi(T\mid S\cap
U)\cdot\mathop{\mathbb{E}}_{\pi\mid T\cap S\cap
U}\left[\mathrm{adv}_{\pi}(f^{\oplus k}(X,Y)\mid X_{k},Y_{<k},\mathbf{M},S\cap
U)\right]$ $\displaystyle=\pi(S\cap U)^{-1/2}\cdot\pi(T\mid S\cap
U)^{1/2}\cdot\left(\pi(T\cap S\cap U)^{1/2}\cdot\mathop{\mathbb{E}}_{\pi\mid
T\cap S\cap U}\left[\mathrm{adv}_{\pi}(f^{\oplus k}(X,Y)\mid
X_{k},Y_{<k},\mathbf{M},T\cap S\cap U)\right]\right)$
$\displaystyle\leq\pi(S\cap
U)^{-1/2}\cdot\eta^{1/4}\cdot\left(\pi(U)^{1/2}\cdot\mathop{\mathbb{E}}_{\pi\mid
U}\left[\mathrm{adv}_{\pi}(f^{\oplus k}(X,Y)\mid
X_{k},Y_{<k},\mathbf{M},U)\right]\right),$

which by the bound on $\eta$, is at most

$\frac{1}{2}\cdot\mathop{\mathbb{E}}_{\pi\mid S\cap
U}\left[\mathrm{adv}_{\pi}(f^{\oplus k}(X,Y)\mid X_{k},Y_{<k},\mathbf{M},S\cap
U)\right].$

Thus, we have

$\displaystyle\kern-20.00003pt\mathop{\mathbb{E}}_{\pi\mid S\cap
U}\left[\mathrm{adv}_{\pi}(f^{\oplus k-1}(X_{<k},Y_{<k})\mid
X_{k},Y_{<k},\mathbf{M},S\cap U)\right]$
$\displaystyle\geq\frac{1}{2}\eta^{-1/2}\cdot\mathop{\mathbb{E}}_{\pi\mid
S\cap U}\left[\mathrm{adv}_{\pi}(f^{\oplus k}(X,Y)\mid
X_{k},Y_{<k},\mathbf{M},S\cap U)\right].$

Combining it with Equation (5) proves the lemma. ∎

###  6.2 High costs

We first consider all $(X_{k},Y_{<k},\mathbf{M})$ at which $\pi_{k}$ has high
costs. We will show that it leads to significant lower
$\phi_{k-1}^{\mathrm{cost}}$.

#### High $\theta$-cost.

The first set of triples consists of all $(X_{k},Y_{<k},\mathbf{M})$ such that

$\displaystyle\alpha^{-1/2}$
$\displaystyle\leq\mathop{\mathbb{E}}_{Y_{k}\sim\pi\mid
X_{k},Y_{<k},\mathbf{M},U}\left[\theta_{\mu}(\pi_{k}\,@\,X_{k},Y_{k},\mathbf{M}^{(\pi_{k})})\right],$
$\displaystyle 2^{-2^{-5}(C_{A}-c\log(r/\alpha))}\cdot\pi(U)$
$\displaystyle\leq\mathop{\mathbb{E}}_{Y_{k}\sim\pi\mid
X_{k},Y_{<k},\mathbf{M},U}\left[\chi^{2}_{\mu,A}(\pi_{k}\,@\,X_{k},Y_{k},\mathbf{M}^{(\pi_{k})})\right],$
$\displaystyle 2^{-2^{-5}(C_{B}-c\log(r/\alpha))}\cdot\pi(U)$
$\displaystyle\leq\mathop{\mathbb{E}}_{Y_{k}\sim\pi\mid
X_{k},Y_{<k},\mathbf{M},U}\left[\chi^{2}_{\mu,B}(\pi_{k}\,@\,X_{k},Y_{k},\mathbf{M}^{(\pi_{k})})\right].$

This is the set of triples at which $\pi_{k}$ has high $\theta$-cost and not-
too-low $\chi^{2}$-costs.

Note that $\theta_{\mu}(\pi_{k}\,@\,X_{k},Y_{k},\mathbf{M}^{(\pi_{k})})$,
$\chi^{2}_{\mu,A}(\pi_{k}\,@\,X_{k},Y_{k},\mathbf{M}^{(\pi_{k})})$ and
$\chi^{2}_{\mu,B}(\pi_{k}\,@\,X_{k},Y_{k},\mathbf{M}^{(\pi_{k})})$ are
functions of $(X_{k},Y,\mathbf{M})$, hence, they do _not_ depend on $X_{<k}$.
Denote this set of $(X_{k},Y_{<k},\mathbf{M})$ by
$S_{\textnormal{high-$\theta$}}$. We will also abuse the notation, and use
$S_{\textnormal{high-$\theta$}}$ to denote the set
$\\{(X,Y,\mathbf{M}):(X_{k},Y_{<k},\mathbf{M})\in
S_{\textnormal{high-$\theta$}}\\}$, which can also be treated as an event.

By applying Lemma 33 and Lemma 34 to $S_{\textnormal{high-$\theta$}}$ and the
corresponding $\eta$, we obtain the following bounds on the costs of
$\pi_{<k}$ conditioned on $S_{\textnormal{high-$\theta$}\cap U}$:

$\displaystyle\log\theta_{\mu^{k-1}}(\pi_{<k}\mid
S_{\textnormal{high-$\theta$}}\cap U)$
$\displaystyle\leq\log\theta_{\mu^{k}}(\pi\mid
U)+\log(1/\pi(S_{\textnormal{high-$\theta$}}\mid
U))-\frac{1}{2}\log(1/\alpha),$
$\displaystyle\log\chi^{2}_{\mu^{k-1},A}(\pi_{<k}\mid
S_{\textnormal{high-$\theta$}}\cap U)$
$\displaystyle\leq\log\chi^{2}_{\mu^{k},A}(\pi\mid
U)+\log(1/\pi(S_{\textnormal{high-$\theta$}}\mid U))$ $\displaystyle\hskip
100.0pt+2^{-5}(C_{A}-c\log(r/\alpha))+\log(1/\pi(U)),$
$\displaystyle\log\chi^{2}_{\mu^{k-1},B}(\pi_{<k}\mid
S_{\textnormal{high-$\theta$}}\cap U)$
$\displaystyle\leq\log\chi^{2}_{\mu^{k},B}(\pi\mid
U)+\log(1/\pi(S_{\textnormal{high-$\theta$}}\mid U))$ $\displaystyle\hskip
100.0pt+2^{-5}(C_{B}-c\log(r/\alpha))+\log(1/\pi(U)).$

Thus, it implies that (recall Definition 23)

$\phi_{k-1}^{\mathrm{cost}}(\pi_{<k}\mid S_{\textnormal{high-$\theta$}}\cap
U)\leq\phi_{k}^{\mathrm{cost}}(\pi\mid
U)+3\log(1/\pi(S_{\textnormal{high-$\theta$}}\mid
U))+2\log(1/\pi(U))-\frac{1}{4}\log(1/\alpha),$ (7)

where we used the assumption that
$C_{A}-c\log(r/\alpha)>\log(1/\alpha),C_{B}-c\log(r/\alpha)>\log(1/\alpha)$.

#### High $\chi^{2}$-cost by Alice.

The next set consists of all $(X_{k},Y_{<k},\mathbf{M})$ such that

$\displaystyle\alpha^{2^{-5}}\cdot\pi(U)$
$\displaystyle\leq\mathop{\mathbb{E}}_{Y_{k}\mid
X_{k},Y_{<k},\mathbf{M}\sim\pi\mid
U}\left[\theta_{\mu}(\pi_{k}\,@\,X_{k},Y_{k},\mathbf{M}^{(\pi_{k})})\right]<\alpha^{-1/2},$
$\displaystyle 2^{C_{A}-c\log(r/\alpha)}$
$\displaystyle\leq\mathop{\mathbb{E}}_{Y_{k}\mid
X_{k},Y_{<k},\mathbf{M}\sim\pi\mid
U}\left[\chi^{2}_{\mu,A}(\pi_{k}\,@\,X_{k},Y_{k},\mathbf{M}^{(\pi_{k})})\right],$
$\displaystyle 2^{-2^{-5}(C_{B}-c\log(r/\alpha))}\cdot\pi(U)$
$\displaystyle\leq\mathop{\mathbb{E}}_{Y_{k}\mid
X_{k},Y_{<k},\mathbf{M}\sim\pi\mid
U}\left[\chi^{2}_{\mu,B}(\pi_{k}\,@\,X_{k},Y_{k},\mathbf{M}^{(\pi_{k})})\right].$

This is the set of triples at which $\pi_{k}$ has high $\chi^{2}$-cost by
Alice and not-too-low $\theta$-cost and $\chi^{2}$-cost by Bob. Denote this
set of $(X_{k},Y_{<k},\mathbf{M})$ by $S_{\textnormal{high-$\chi^{2}$-A}}$.
The upper bound on the $\theta$-cost ensures that it is disjoint from
$S_{\textnormal{high-$\theta$}}$. Similarly, we also abuse the notation to let
$S_{\textnormal{high-$\chi^{2}$-A}}$ also denote the set
$\\{(X,Y,\mathbf{M}):(X_{k},Y_{<k},\mathbf{M})\in
S_{\textnormal{high-$\chi^{2}$-A}}\\}$.

By applying Lemma 33 and Lemma 34 to $S_{\textnormal{high-$\chi^{2}$-A}}$ and
the corresponding $\eta$, we have the following bounds:

$\displaystyle\log\theta_{\mu^{k-1}}(\pi_{<k}\mid
S_{\textnormal{high-$\chi^{2}$-A}}\cap U)$
$\displaystyle\leq\log\theta_{\mu^{k}}(\pi\mid
U)+\log(1/\pi(S_{\textnormal{high-$\chi^{2}$-A}}\mid U))$ $\displaystyle\hskip
100.0pt+2^{-5}\log(1/\alpha)+\log(1/\pi(U)),$
$\displaystyle\log\chi^{2}_{\mu^{k-1},A}(\pi_{<k}\mid
S_{\textnormal{high-$\chi^{2}$-A}}\cap U)$
$\displaystyle\leq\log\chi^{2}_{\mu^{k},A}(\pi\mid
U)+\log(1/\pi(S_{\textnormal{high-$\chi^{2}$-A}}\mid U))$ $\displaystyle\hskip
100.0pt-(C_{A}-c\log(r/\alpha)),$
$\displaystyle\log\chi^{2}_{\mu^{k-1},B}(\pi_{<k}\mid
S_{\textnormal{high-$\chi^{2}$-A}}\cap U)$
$\displaystyle\leq\log\chi^{2}_{\mu^{k},B}(\pi\mid
U)+\log(1/\pi(S_{\textnormal{high-$\chi^{2}$-A}}\mid U))$ $\displaystyle\hskip
100.0pt+2^{-5}(C_{B}-c\log(r/\alpha))+\log(1/\pi(U)),$

which also implies

$\phi_{k-1}^{\mathrm{cost}}(\pi_{<k}\mid
S_{\textnormal{high-$\chi^{2}$-A}}\cap U)\leq\phi_{k}^{\mathrm{cost}}(\pi\mid
U)+3\log(1/\pi(S_{\textnormal{high-$\chi^{2}$-A}}\mid
U))+2\log(1/\pi(U))-\frac{1}{4}\log(1/\alpha).$ (8)

#### High $\chi^{2}$-cost by Bob.

The third case consists of all $(X_{k},Y_{<k},\mathbf{M})$ such that

$\displaystyle\alpha^{2^{-5}}\cdot\pi(U)$
$\displaystyle\leq\mathop{\mathbb{E}}_{Y_{k}\sim\pi\mid
X_{k},Y_{<k},\mathbf{M},U}\left[\theta_{\mu}(\pi_{k}\,@\,X_{k},Y_{k},\mathbf{M}^{(\pi_{k})})\right]<\alpha^{-1/2},$
$\displaystyle 2^{-2^{-5}(C_{A}-c\log(r/\alpha))}\cdot\pi(U)$
$\displaystyle\leq\mathop{\mathbb{E}}_{Y_{k}\sim\pi\mid
X_{k},Y_{<k},\mathbf{M},U}\left[\chi^{2}_{\mu,A}(\pi_{k}\,@\,X_{k},Y_{k},\mathbf{M}^{(\pi_{k})})\right]<2^{C_{A}-c\cdot\log(r/\alpha)},$
$\displaystyle 2^{C_{B}-c\log(r/\alpha)}$
$\displaystyle\leq\mathop{\mathbb{E}}_{Y_{k}\sim\pi\mid
X_{k},Y_{<k},\mathbf{M},U}\left[\chi^{2}_{\mu,B}(\pi_{k}\,@\,X_{k},Y_{k},\mathbf{M}^{(\pi_{k})})\right].$

This is the set of triples at which $\pi_{k}$ has high $\chi^{2}$-cost by Bob
and not-too-low $\theta$-cost and $\chi^{2}$-cost by Alice. Denote this set of
$(X_{k},Y_{<k},\mathbf{M})$ by $S_{\textnormal{high-$\chi^{2}$-B}}$. It is
disjoint from $S_{\textnormal{high-$\theta$}}$ and
$S_{\textnormal{high-$\chi^{2}$-A}}$. Similarly, we also use
$S_{\textnormal{high-$\chi^{2}$-B}}$ to denote the set
$\\{(X,Y,\mathbf{M}):(X_{k},Y_{<k},\mathbf{M})\in
S_{\textnormal{high-$\chi^{2}$-B}}\\}$.

By applying Lemma 33 and Lemma 34 to $S_{\textnormal{high-$\chi^{2}$-B}}$ and
the appropriate $\eta$, we have the following bounds:

$\displaystyle\log\theta_{\mu^{k-1}}(\pi_{<k}\mid
S_{\textnormal{high-$\chi^{2}$-B}}\cap U)$
$\displaystyle\leq\log\theta_{\mu^{k}}(\pi\mid
U)+\log(1/\pi(S_{\textnormal{high-$\chi^{2}$-B}}\mid U))$ $\displaystyle\hskip
100.0pt+2^{-5}\log(1/\alpha)+\log(1/\pi(U)),$
$\displaystyle\log\chi^{2}_{\mu^{k-1},A}(\pi_{<k}\mid
S_{\textnormal{high-$\chi^{2}$-B}}\cap U)$
$\displaystyle\leq\log\chi^{2}_{\mu^{k},A}(\pi\mid
U)+\log(1/\pi(S_{\textnormal{high-$\chi^{2}$-B}}\mid U))$ $\displaystyle\hskip
100.0pt+2^{-5}(C_{A}-c\log(r/\alpha))+\log(1/\pi(U)),$
$\displaystyle\log\chi^{2}_{\mu^{k-1},B}(\pi_{<k}\mid
S_{\textnormal{high-$\chi^{2}$-B}}\cap U)$
$\displaystyle\leq\log\chi^{2}_{\mu^{k},B}(\pi\mid
U)+\log(1/\pi(S_{\textnormal{high-$\chi^{2}$-B}}\mid U))$ $\displaystyle\hskip
100.0pt-(C_{B}-c\log(r/\alpha)),$

which also implies that

$\phi_{k-1}^{\mathrm{cost}}(\pi_{<k}\mid
S_{\textnormal{high-$\chi^{2}$-B}}\cap U)\leq\phi_{k}^{\mathrm{cost}}(\pi\mid
U)+3\log(1/\pi(S_{\textnormal{high-$\chi^{2}$-B}}\mid
U))+2\log(1/\pi(U))-\frac{1}{4}\log(1/\alpha).$ (9)

Equation (7), (8) and (9) implies that for
$\beta\in\\{\textnormal{high-$\theta$},\textnormal{high-$\chi^{2}$-A},\textnormal{high-$\chi^{2}$-B}\\}$,
we all have

$\displaystyle\phi_{k-1}^{\mathrm{cost}}(\pi_{<k}\mid S_{\beta}\cap U)$
$\displaystyle\leq\phi_{k}^{\mathrm{cost}}(\pi\mid
U)+3\log(1/\pi(S_{\beta}\mid U))+2\log(1/\pi(U))-\frac{1}{4}\log(1/\alpha)$
$\displaystyle\leq\phi_{k}^{\mathrm{cost}}(\pi\mid
U)+3\log(1/\pi(S_{\beta}\cap U))-\frac{1}{4}\log(1/\alpha).$ (10)

The main lemma of this subsection is the following, stating that if the above
three sets contribute a nontrival amount of total advantage in $U$ (weighted
by the probability), then we can construct a protocol for $f^{\oplus k-1}$
satisfying the requirements of Lemma 26 (by conditioning $\pi_{<k}$ on a
carefully chosen event).

######  Lemma 36.

Let $S_{\textnormal{high-cost}}$ be the union
$S_{\textnormal{high-$\theta$}}\cup S_{\textnormal{high-$\chi^{2}$-A}}\cup
S_{\textnormal{high-$\chi^{2}$-B}}$. If we have

$\displaystyle\kern-20.00003pt\pi(S_{\textnormal{high-cost}}\cap
U)\cdot\mathop{\mathbb{E}}_{\pi\mid S_{\textnormal{high-cost}}\cap
U}\left[\mathrm{adv}_{\pi}(f^{\oplus k}(X,Y)\mid
X_{k},Y_{<k},\mathbf{M},S_{\textnormal{high-cost}}\cap U)\right]$
$\displaystyle\geq\frac{1}{3}\cdot\pi(U)\cdot\mathop{\mathbb{E}}_{\pi\mid
U}\left[\mathrm{adv}_{\pi}(f^{\oplus k}(X,Y)\mid
X_{k},Y_{<k},\mathbf{M},U))\right],$

then Lemma 26 holds.

Protocol $\pi_{<k}$ and event $S_{\beta}\cap U$ may be one potential choice
for $\pi_{{\mathrm{new}}}$ and $V_{\mathrm{new}}$ in Lemma 26. However, Lemma
26 requires the probability of $V_{\mathrm{new}}$ to be $\Omega(1)$, which is
not necessarily true for any $\beta$, since $U$ may have very small
probability. On the other hand, we could also consider setting
$\pi_{{\mathrm{new}}}$ to the distribution of $\pi_{<k}$ conditioned on
$S_{\beta}\cap U$ and $V_{\mathrm{new}}$ to the entire sample space, but this
protocol may have very large costs.

To resolve this issue, we will use the following lemma, which turns
$(\pi_{<k}\mid S_{\beta}\cap U)$ into a protocol $(\pi_{<k})_{G}$ with bounded
costs for some event $G\approx S_{\beta}\cap U$. Moreover, by dividing $G$
into $G_{0}\cup G_{1}$ according to whether the function value is more likely
to be $0$ or $1$ conditioned on $Y$ and $\mathbf{M}$, the lemma guarantees
that the costs conditioned on $G_{b}$ are also bounded (for $b=0,1$). This
will allow us to apply Lemma 35 later to lower bound the advantage.

######  Lemma 37.

Fix any $\gamma\in(0,1/2)$. Let $\rho$ be an $r$-round generalized protocol
over $\mathcal{X}\times\mathcal{Y}\times\mathcal{M}$, $W$ be an event, $\nu$
be an input distribution and
$h:\mathcal{X}\times\mathcal{Y}\rightarrow\\{0,1\\}$ be a function of the
inputs. Then there exists a _partition_ of $W$ into three events
$G,B_{0},B_{1}$ and a _partition_ of $\mathcal{Y}\times\mathcal{M}$ into
$E_{0},E_{1}$ such that the following holds:

  1. 1.

all three events $G$, $B_{0}$, $B_{1}$ have the form $W\cap S$ for some
$S\in\mathcal{S}_{\mathrm{rec}}(\rho)$;

  2. 2.

$\rho(B_{0}\cup B_{1}\mid W)\leq\gamma$;

  3. 3.

let $\rho_{G}$ be the protocol $(\rho\mid G)$, $G_{0}=G\cap E_{0}$ and
$G_{1}=G\cap E_{1}$, then for $b=0,1$,

$\displaystyle\log\theta_{\nu}(\rho_{G}\mid G_{b})$
$\displaystyle\leq\log\theta_{\nu}(\rho\mid
W)+(r+1)\log\left((r+3)/\gamma\right)+\log\left(1/((1-\gamma)\rho(G_{b}))\right),$
$\displaystyle\log\chi^{2}_{\nu,A}(\rho_{G}\mid G_{b})$
$\displaystyle\leq\log\chi^{2}_{\nu,A}(\rho\mid
W)+\log((r+3)/\gamma)+\log(1/((1-\gamma)\rho(G_{b}))),$
$\displaystyle\log\chi^{2}_{\nu,B}(\rho_{G}\mid G_{b})$
$\displaystyle\leq\log\chi^{2}_{\nu,B}(\rho\mid
W)+\log((r+3)/\gamma)+\log(1/((1-\gamma)\rho(G_{b})));$

  4. 4.

for $b=0,1$, and all $(Y,\mathbf{M})$ such that $\rho(Y,\mathbf{M}\mid
G_{b})>0$,

$\rho(h(X,Y)=b\mid Y,\mathbf{M},G_{b})\geq 1/2.$

Note that we upper bound the costs of $\rho_{G}$ conditioned on $G_{b}$ by the
costs of $\rho$ conditioned on $W$ (plus some small quantity). Thus, for
$\rho=\pi_{<k}$ and $W=S_{\beta}\cap U$, the costs are bounded due to Equation
(10). To focus on our main proof, we will defer the proof of Lemma 37 to
Section 6.5. Now we use it to prove Lemma 36.

###### Proof of Lemma 36.

We first fix some
$\beta\in\\{\textnormal{high-$\theta$},\textnormal{high-$\chi^{2}$-A},\textnormal{high-$\chi^{2}$-B}\\}$.
By applying Lemma 37 to protocol $\rho=\pi_{<k}$, event $W=S_{\beta}\cap U$,
input distribution $\nu=\mu^{k-1}$ and function $h=f^{\oplus k-1}$ for
$\gamma=2^{-12}$, we obtain sets
$G_{\beta},B_{\beta,0},B_{\beta,1},E_{\beta,0},E_{\beta,1}$. Let
$G_{\beta,0}=G_{\beta}\cap E_{\beta,0}$, $G_{\beta,1}=G_{\beta}\cap
E_{\beta,1}$, and $(\pi_{<k})_{G_{\beta}}$ be the distribution $\pi_{<k}$
conditioned on $G_{\beta}$. The lemma guarantees that
$G_{\beta},B_{\beta,0},B_{\beta,1}$ all have the form $S_{\beta}\cap U\cap S$
for some
$S\in\mathcal{S}_{\mathrm{rec}}(\pi_{<k})\subseteq\mathcal{S}_{\mathrm{pt}}(\pi)$
(Proposition 28). Since $S_{\beta}\cap U\in\mathcal{S}_{\mathrm{pt}}(\pi)$, we
have that
$G_{\beta},B_{\beta,0},B_{\beta,1}\in\mathcal{S}_{\mathrm{pt}}(\pi)$. Since
$E_{\beta,0},E_{\beta,1}\in\mathcal{S}_{\mathrm{rec}}(\pi_{<k})$, we also have
$G_{\beta,0},G_{\beta,1}\in\mathcal{S}_{\mathrm{pt}}(\pi)$.

For each $\beta$, since $G_{\beta}\in\mathcal{S}_{\mathrm{pt}}(\pi)$,
Proposition 22(ii) implies that $(\pi\mid G_{\beta})$ has the partial
rectangle property with respect to $\mu^{k}$. Then Proposition 27 implies that
$(\pi_{<k}\mid G_{\beta})$, i.e., $(\pi_{<k})_{G_{\beta}}$, has the rectangle
property with respect to $\mu^{k-1}$. For each $\beta,b$, since
$E_{\beta,b}\in\mathcal{S}_{\mathrm{rec}}(\pi_{<k})=\mathcal{S}_{\mathrm{rec}}((\pi_{<k})_{G_{\beta}})$,
the protocol $(\pi_{<k})_{G_{\beta}}$ and the event $E_{\beta,b}$ are one
candidate for $\pi_{{\mathrm{new}}}$ and $V_{\mathrm{new}}$ in Lemma 26. We
will prove the following sufficient condition for them to satisfy the
requirements of Lemma 26.

######  Claim 38.

If we have

$\displaystyle\kern-20.00003pt\pi(G_{\beta,b})\cdot\mathop{\mathbb{E}}_{\pi\mid
G_{\beta,b}}\left[\mathrm{adv}_{\pi}(f^{\oplus k}(X,Y)\mid
X_{k},Y_{<k},\mathbf{M},G_{\beta,b}))\right]$ (11) $\displaystyle\geq
2^{-6}\cdot\pi(U)\cdot\mathop{\mathbb{E}}_{\pi\mid
U}\left[\mathrm{adv}_{\pi}(f^{\oplus k}(X,Y)\mid
X_{k},Y_{<k},\mathbf{M},U))\right],$

then $(\pi_{<k})_{G_{\beta}}$ and event $E_{\beta,b}$ satisfy the requirements
of Lemma 26 for $\pi_{{\mathrm{new}}}$ and $V_{\mathrm{new}}$.

Before proving the claim, we first show that it implies Lemma 36. If Equation
(11) holds for any
$\beta\in\\{\textnormal{high-$\theta$},\textnormal{high-$\chi^{2}$-A},\textnormal{high-$\chi^{2}$-B}\\}$
and $b\in\\{0,1\\}$, then the lemma holds. Otherwise we must have for every
$\beta$ and $b$,

$\displaystyle\kern-20.00003pt\pi(G_{\beta,b})\cdot\mathop{\mathbb{E}}_{\pi\mid
G_{\beta,b}}\left[\mathrm{adv}_{\pi}(f^{\oplus k}(X,Y)\mid
X_{k},Y_{<k},\mathbf{M},G_{\beta,b}))\right]$
$\displaystyle<2^{-6}\cdot\pi(U)\cdot\mathop{\mathbb{E}}_{\pi\mid
U}\left[\mathrm{adv}_{\pi}(f^{\oplus k}(X,Y)\mid
X_{k},Y_{<k},\mathbf{M},U))\right].$

On the other hand, since $B_{\beta,b}\in\mathcal{S}_{\mathrm{pt}}(\pi)$,
$B_{\beta,b}\subseteq S_{\beta}\cap U$ and $\pi(B_{\beta,b}\mid
U)\leq\pi(B_{\beta,b}\mid S_{\beta}\cap U)\leq 2^{-12}$, by Proposition 32(i),
we also have

$\displaystyle\kern-20.00003pt\pi(B_{\beta,b})\cdot\mathop{\mathbb{E}}_{\pi\mid
B_{\beta,b}}\left[\mathrm{adv}_{\pi}(f^{\oplus k}(X,Y)\mid
X_{k},Y_{<k},\mathbf{M},B_{\beta,b}))\right]$ $\displaystyle\leq
2^{-6}\cdot\pi(U)\cdot\mathop{\mathbb{E}}_{\pi\mid
U}\left[\mathrm{adv}_{\pi}(f^{\oplus k}(X,Y)\mid
X_{k},Y_{<k},\mathbf{M},U))\right].$

Since $G_{\beta,0}\cup G_{\beta,1}\cup B_{\beta,0}\cup
B_{\beta,1}=S_{\beta}\cap U$, $S_{\textnormal{high-
cost}}=S_{\textnormal{high-$\theta$}}\cup
S_{\textnormal{high-$\chi^{2}$-A}}\cup S_{\textnormal{high-$\chi^{2}$-B}}$,
and all 12 sets are disjoint, by summing up the above inequalities for all
$B_{\beta,b}$ and $G_{\beta,b}$ and applying Lemma 10, we have

$\displaystyle\kern-20.00003pt\pi(S_{\textnormal{high-cost}}\cap
U)\cdot\mathop{\mathbb{E}}_{\pi\mid S_{\textnormal{high-cost}}\cap
U}\left[\mathrm{adv}_{\pi}(f^{\oplus k}(X,Y)\mid
X_{k},Y_{<k},\mathbf{M},S_{\textnormal{high-cost}}\cap U))\right]$
$\displaystyle<\frac{1}{3}\cdot\pi(U)\cdot\mathop{\mathbb{E}}_{\pi\mid
U}\left[\mathrm{adv}_{\pi}(f^{\oplus k}(X,Y)\mid
X_{k},Y_{<k},\mathbf{M},U))\right],$

contradicting with the lemma premise.

Now it suffices to prove the claim. We first observe that by Proposition
32(i), Equation (11) also implies that $\pi\left(G_{\beta,b}\mid
U\right)^{1/2}\geq 2^{-6}$, which in turn, implies that $\pi(E_{\beta,b}\mid
G_{\beta})=\pi(G_{\beta,b}\mid G_{\beta})\geq 2^{-12}$, i.e., the probability
of $E_{\beta,b}$ in the distribution $(\pi_{<k})_{G_{\beta}}$ is at least
$2^{-12}$, as required by Lemma 26. In the following, we show that the bound
on $\phi_{k-1}\left((\pi_{<k})_{G_{\beta}}\mid
E_{\beta,b}\right)=\phi_{k-1}\left((\pi_{<k})_{G_{\beta}}\mid
G_{\beta,b}\right)$ also holds.

#### Bounding $\phi_{k-1}^{\mathrm{cost}}((\pi_{<k})_{G_{\beta}}\mid
G_{\beta,b})$.

We first bound its $\phi_{k-1}^{\mathrm{cost}}$ value. By Lemma 37 and the
fact that $\log(1/\alpha)<C_{A}-c\log(r/\alpha)$ and
$\log(1/\alpha)<C_{B}-c\log(r/\alpha)$, we have

$\displaystyle\kern
12.50002pt\phi_{k-1}^{\mathrm{cost}}((\pi_{<k})_{G_{\beta}}\mid G_{\beta,b})$
$\displaystyle=\log\theta_{\mu^{k-1}}((\pi_{<k})_{G_{\beta}}\mid
G_{\beta,b})+\frac{\log(1/\alpha)}{C_{A}-c\log(r/\alpha)}\cdot\log\chi^{2}_{\mu^{k-1},A}((\pi_{<k})_{G_{\beta}}\mid
G_{\beta,b})$
$\displaystyle\qquad+\frac{\log(1/\alpha)}{C_{B}-c\log(r/\alpha)}\cdot\log\chi^{2}_{\mu^{k-1},B}((\pi_{<k})_{G_{\beta}}\mid
G_{\beta,b})$ $\displaystyle\leq\log\theta_{\mu^{k-1}}(\pi_{<k}\mid
S_{\beta}\cap
U)+\frac{\log(1/\alpha)}{C_{A}-c\log(r/\alpha)}\cdot\log\chi^{2}_{\mu^{k-1},A}(\pi_{<k}\mid
S_{\beta}\cap U)$
$\displaystyle\qquad+\frac{\log(1/\alpha)}{C_{B}-c\log(r/\alpha)}\cdot\log\chi^{2}_{\mu^{k-1},B}(\pi_{<k}\mid
S_{\beta}\cap U)$
$\displaystyle\qquad+(r+3)\log\left((r+3)/\gamma\right)+3\log(1/\left((1-\gamma)\pi_{<k}(G_{\beta,b})\right))$
$\displaystyle=\phi_{k-1}^{\mathrm{cost}}(\pi_{<k}\mid S_{\beta}\cap
U)+(r+3)\log\left((r+3)/\gamma\right)+3\log(1/\left((1-\gamma)\pi_{<k}(G_{\beta,b})\right))$
which by Equation (10), is at most
$\displaystyle\leq\phi_{k}^{\mathrm{cost}}(\pi\mid U)+O(r\log
r)+3\log(1/\pi_{<k}(G_{\beta,b}))+3\log(1/\pi(S_{\beta}\cap
U))-\frac{1}{4}\log(1/\alpha)$
$\displaystyle\leq\phi_{k}^{\mathrm{cost}}(\pi\mid
U)+6\log(1/\pi(G_{\beta,b}))-\frac{1}{8}\log(1/\alpha),$ (12)

where we used the assumption that $\log(1/\alpha)>cr\log r$ for a sufficiently
large $c$, and the fact that $\pi(S_{\beta}\cap U)\geq\pi(G_{\beta,b})$, and
the fact that $G_{\beta,b}$ can also be viewed as an event in $\pi$.

#### Bounding $\phi_{k-1}^{\mathrm{adv}}((\pi_{<k})_{G_{\beta}}\mid
G_{\beta,b})$.

Next we bound its $\phi_{k-1}^{\mathrm{adv}}$ value. Lemma 37 also guarantees
that for all $(X_{k},Y_{<k},\mathbf{M})$ such that
$\pi(X_{k},Y_{<k},\mathbf{M}\mid G_{\beta,b})>0$ (recall that
$\mathbf{M}^{(\pi_{<k})}=(X_{k},\mathbf{M})$), we have

$\pi(f^{\oplus k-1}(X_{<k},Y_{<k})=b\mid
X_{k},Y_{<k},\mathbf{M},G_{\beta,b})\geq 1/2.$

This allows us to bound its advantage by applying the first part of Lemma 35
for $S=G_{\beta,b}\in\mathcal{S}_{\mathrm{pt}}(\pi)$ (note that
$G_{\beta,b}\subseteq U$). Thus, it implies

$\displaystyle\mathop{\mathbb{E}}_{\pi\mid
G_{\beta,b}}\left[\mathrm{adv}_{\pi}(f^{\oplus
k-1}(X_{<k},Y_{<k})\mid\mathbf{M}^{(\pi_{<k})},G_{\beta,b})\right]$
$\displaystyle\qquad\geq\mathop{\mathbb{E}}_{\pi\mid
G_{\beta,b}}\left[\mathrm{adv}_{\pi}(f^{\oplus k}(X,Y)\mid
X_{k},Y_{<k},\mathbf{M},G_{\beta,b})\right].$

Note that the LHS is exactly the expected advantage of protocol
$(\pi_{<k})_{G_{\beta}}$ _conditioned on_ $G_{\beta,b}$:

$\displaystyle\kern-20.00003pt\mathop{\mathbb{E}}_{\pi\mid
G_{\beta,b}}\left[\mathrm{adv}_{\pi}(f^{\oplus
k-1}(X_{<k},Y_{<k})\mid\mathbf{M}^{(\pi_{<k})},G_{\beta,b})\right]$
$\displaystyle=\mathop{\mathbb{E}}_{(\pi_{<k})\mid
G_{\beta},G_{\beta,b}}\left[\mathrm{adv}_{\pi_{<k}}(f^{\oplus
k-1}(X_{<k},Y_{<k})\mid\mathbf{M}^{(\pi_{<k})},G_{\beta},G_{\beta,b})\right]$
$\displaystyle=\mathop{\mathbb{E}}_{(\pi_{<k})_{G_{\beta}}\mid
G_{\beta,b}}\left[\mathrm{adv}_{(\pi_{<k})_{G_{\beta}}}(f^{\oplus
k-1}(X_{<k},Y_{<k})\mid\mathbf{M}^{((\pi_{<k})_{G_{\beta}})},G_{\beta,b})\right].$

Thus, by definition, that is

$\phi_{k-1}^{\mathrm{adv}}((\pi_{<k})_{G_{\beta}}\mid
G_{\beta,b})\leq\phi_{k,\mathrm{pt}}^{\mathrm{adv}}(\pi\mid{G_{\beta,b}}).$
(13)

#### Bounding $\phi_{k-1}((\pi_{<k})_{G_{\beta}}\mid G_{\beta,b})$.

Now we sum up the two parts of the potential function. By Equation (12) and
(13), we have

$\displaystyle\kern 12.50002pt\phi_{k-1}((\pi_{<k})_{G_{\beta}}\mid
G_{\beta,b})$
$\displaystyle=\phi_{k-1}^{\mathrm{cost}}((\pi_{<k})_{G_{\beta}}\mid
G_{\beta,b})+\phi_{k-1}^{\mathrm{adv}}((\pi_{<k})_{G_{\beta}}\mid
G_{\beta,b})$ $\displaystyle\leq\phi_{k}^{\mathrm{cost}}(\pi\mid
U)+\phi_{k,\mathrm{pt}}^{\mathrm{adv}}(\pi\mid{G_{\beta,b}})+6\log(1/\pi(G_{\beta,b}))-\frac{1}{8}\log(1/\alpha)$
$\displaystyle=\phi_{k,\mathrm{pt}}(\pi\mid
U)-\phi_{k,\mathrm{pt}}^{\mathrm{adv}}(\pi\mid
U)+\left(\phi_{k,\mathrm{pt}}^{\mathrm{adv}}(\pi\mid{G_{\beta,b}})+6\log(1/\pi(G_{\beta,b}))\right)-\frac{1}{8}\log(1/\alpha)$
which by Lemma 31, is $\displaystyle\leq\phi_{k}(\pi\mid V)-13\log(1/\pi(U\mid
V))-\phi_{k,\mathrm{pt}}^{\mathrm{adv}}(\pi\mid
U)+\left(\phi_{k,\mathrm{pt}}^{\mathrm{adv}}(\pi\mid{G_{\beta,b}})+6\log(1/\pi(G_{\beta,b}))\right)-\frac{1}{8}\log(1/\alpha)$
which by the fact that $\log(1/\pi(U\mid V))\geq 0$ and $\pi(V)\geq 2^{-12}$,
is $\displaystyle\leq\phi_{k}(\pi\mid
V)-6(\log(1/\pi(U))-\log(1/\pi(V)))-\phi_{k,\mathrm{pt}}^{\mathrm{adv}}(\pi\mid
U)+\left(\phi_{k,\mathrm{pt}}^{\mathrm{adv}}(\pi\mid{G_{\beta,b}})+6\log(1/\pi(G_{\beta,b}))\right)$
$\displaystyle\qquad-\frac{1}{8}\log(1/\alpha)$
$\displaystyle\leq\phi_{k}(\pi\mid
V)-\left(\phi_{k,\mathrm{pt}}^{\mathrm{adv}}(\pi\mid
U)+6\log(1/\pi(U))\right)+\left(\phi_{k,\mathrm{pt}}^{\mathrm{adv}}(\pi\mid{G_{\beta,b}})+6\log(1/\pi(G_{\beta,b}))\right)$
$\displaystyle\qquad-\frac{1}{8}\log(1/\alpha)+72.$ (14)

Finally, by Equation (11) and Proposition 32(ii) (for $s=2^{6}$ and $t=6$), we
have

$\left(\phi_{k,\mathrm{pt}}^{\mathrm{adv}}(\pi\mid
U)+6\log(1/\pi(U))\right)\geq\left(\phi_{k,\mathrm{pt}}^{\mathrm{adv}}(\pi\mid{G_{\beta,b}})+6\log(1/\pi(G_{\beta,b}))\right)-192.$

Plugging it into Equation (14), we obtain

$\phi_{k-1}((\pi_{<k})_{G_{\beta}}\mid G_{\beta,b})\leq\phi_{k}(\pi\mid
V)-\frac{1}{16}\log(1/\alpha),$

since $\alpha\leq r^{-cr}$ for a sufficiently large constant $c$. Hence,
$(\pi_{<k})_{G_{\beta}}$ and $E_{\beta,b}$ satisfy the requirements of Lemma
26. This proves the claim, completing the proof of Lemma 36. ∎

###  6.3 Low costs

Now we consider the case where $\pi_{k}$ has low costs. It consists of all
$(X_{k},Y_{<k},\mathbf{M})$ such that

$\displaystyle\alpha^{2^{-5}}\cdot\pi(U)$
$\displaystyle\leq\mathop{\mathbb{E}}_{Y_{k}\sim\pi\mid
X_{k},Y_{<k},\mathbf{M},U}\left[\theta_{\mu}(\pi_{k}\,@\,X_{k},Y_{k},\mathbf{M}^{(\pi_{k})})\right]<\alpha^{-1/2},$
$\displaystyle 2^{-2^{-5}(C_{A}-c\log(r/\alpha))}\cdot\pi(U)$
$\displaystyle\leq\mathop{\mathbb{E}}_{Y_{k}\sim\pi\mid