DNF DNFs AC^0 TC^0 MAJ MUX NAE OR AND Tribes LocalCorrect sgn sparsity rank
span quasipoly Bias DTdepth DTsize PARITY Dict Corr avg smooth dist ETH

# XOR Lemmas for Communication via Marginal Information

Siddharth Iyer
<EMAIL_ADDRESS>Supported by NSF award 2131899. Anup
Rao11footnotemark: 1
<EMAIL_ADDRESS>
###### Abstract

We define the _marginal information_ of a communication protocol, and use it
to prove XOR lemmas for communication complexity. We show that if every
$C$-bit protocol has bounded advantage for computing a Boolean function $f$,
then every $\widetilde{\Omega}(C\sqrt{n})$-bit protocol has advantage
$\exp(-\Omega(n))$ for computing the $n$-fold xor $f^{\oplus n}$. We prove
exponentially small bounds in the average case setting, and near optimal
bounds for product distributions and for bounded-round protocols.

###### Contents

  1. 1 Introduction
    1. 1.1 The evolution of information complexity
    2. 1.2 Using marginal information to prove XOR lemmas
  2. 2 Preliminaries
  3. 3 Marginal information of efficient protocols
  4. 4 Marginal information is subadditive
  5. 5 Trimming and advantage preserving sets
  6. 6 Consequences of small marginal information
  7. 7 Compressing marginal information
  8. 8 Smoothing protocols
  9. 9 Compressing external marginal information
  10. 10 Compressing bounded-round protocols
  11. 11 Compression independent of communication

##  1 Introduction

If a function is hard to compute, is it even harder to compute it many times?
This old question is often challenging, and new answers are usually
accompanied by foundational ideas. We give new answers in the framework of
communication complexity, accompanied by a new measure of complexity called
_marginal information_. This definition provides a new tool for proving lower
bounds in theoretical computer science.

A wide variety of important lower bounds in computer science ultimately rely
on information theoretic lower bounds in communication complexity, including
lower bounds on the depth of monotone circuits [KRW95], lower bounds on data
structures [Pǎt11] and lower bounds on the extension complexity of polytopes
[BP16, Rot17, Sin18, JSY23], to name a few nice examples. We refer the reader
to the textbook [RY20] for an introduction to the basic definitions and
concepts in communication complexity, the role played by the questions we
address here, and the connections to other areas.

Given a Boolean function $f:\mathcal{X}\times\mathcal{Y}\rightarrow\\{0,1\\}$,
define the functions
$f^{n}:\mathcal{X}^{n}\times\mathcal{Y}^{n}\rightarrow\\{0,1\\}^{n}$ and
$f^{\oplus n}:\mathcal{X}^{n}\times\mathcal{Y}^{n}\rightarrow\\{0,1\\}$ as
follows111Throughout, we drop the delimiters between variables. $f(xy)$ is to
be read as $f(x,y)$.:

$\displaystyle f^{n}(xy)$
$\displaystyle=(f(x_{1}y_{1}),f(x_{2}y_{2}),\ldots,f(x_{n}y_{n})),$
$\displaystyle f^{\oplus n}(xy)$ $\displaystyle=f(x_{1}y_{1})\oplus
f(x_{2}y_{2})\oplus\dotsb\oplus f(x_{n}y_{n}).$

So, $f^{n}$ computes $f$ on $n$ different pairs of inputs, and $f^{\oplus n}$
computes the parity of the outputs of $f^{n}$. If $f$ is hard to compute, are
$f^{n}$ and $f^{\oplus n}$ even harder to compute? For deterministic
communication complexity, Feder, Kushilevitz, Naor and Nisan [FKNN95] proved
that if $|\mathcal{X}|,|\mathcal{Y}|\leq 2^{\ell}$ and $f$ requires $C$ bits
of communication, then $f^{n}$ requires at least $n(\sqrt{C}-\log_{2}\ell-1)$
bits of communication. In this work, we study randomized communication
complexity. Let $\|\pi\|$ denote the communication complexity of a randomized
communication protocol $\pi$ and define the advantage:

$\displaystyle\mathsf{adv}(C,f)$ $\displaystyle=\sup_{\|\pi\|\leq
C}\inf_{xy}\mathop{\mathbb{E}\/}[(-1)^{\pi(xy)+f(xy)}].$

This quantity measures the best worst-case advantage achievable by a $C$-bit
protocol over random guessing. We can now state our main result:

######  Theorem 1.

There is a universal constant $\kappa>0$ such that if $C>1/\kappa$ and
$\mathsf{adv}(C,f)<1/2$, then

$\mathsf{adv}\Big{(}\frac{\kappa C\sqrt{n}}{\log(Cn)},f^{\oplus
n}\Big{)}\leq\exp(-\kappa n).$

The constant $1/2$ is not important, it can be replaced by any constant less
than $1$. Some assumption of the type $C>1/\kappa$ is necessary, because if
$x,y\in\\{0,1\\}$ and $f(xy)=x\oplus y$, then $\mathsf{adv}(2,f^{\oplus
n})=1$. Prior to our work, the best known upper bound was proved by the second
author with Barak, Braverman and Chen [BBCR10]. They showed that under a
similar bound on the communication, the advantage is bounded by $1/2$. Our
work builds on the work of Yu [Yu22], who proved exponentially small bounds in
the setting of bounded-round protocols. Our ideas lead to many results similar
to Theorem 1. Next, we review the history that led us to the notion of
marginal information, and explain the intuitions behind the choices made in
the definition before describing all of our results in Section 1.2.

###  1.1 The evolution of information complexity

Marginal information is the most recent advance in an evolution of definitions
about information. We relate bounds on the communication and advantage for
computing $f$ to the corresponding parameters for $f^{\oplus n}$ via a scheme
that has been applied many times before. We prove:

Step 1

Every protocol computing $f^{\oplus n}$ with significant advantage and small
communication has small marginal information; see Theorem 5.

Step 2

Marginal information is subadditive, so the marginal information for computing
$f$ is smaller by a factor of $n$; see Theorem 6.

Step 3

Small marginal information can be compressed to give protocols with small
communication; see Theorems 7, 8, 10 and 9.

Definitions of information are famously subtle. In order to make this strategy
work, the marginal information needs to permit all 3 steps, and even minor
changes to the definition can make one of the steps infeasible.

Our current definition builds on important insights and intuitions developed
in theoretical computer science over a period of decades. An early precursor
to the use of information theory in computer science is the work of
Kalyanasundaram and Schnitger, who used Kolmogorov complexity to prove lower
bounds on the randomized communication complexity of the disjointness function
[SK87]. The proof was subsequently simplified by Razborov [Raz92], who gave a
beautiful short argument that used Shannon’s notion of entropy [Sha48] and
implicitly followed the outline of the steps 1,2,3 described above. This is
related to the questions we study here because the disjointness function can
be thought of as a way to compute the AND of two bits $n$ times. Step 1 is
relatively easy for this problem. Step 2 involved a clever way to split the
dependence between random variables, and was accomplished using the
subadditivity of entropy. Step 3 is also not too difficult.

The next chapter of the story was written during the study of parallel
repetition, a vital tool in the development of probabilistically checkable
proofs. Raz [Raz95] proved the first exponentially small bounds in this
context using the Kullback-Liebler divergence as a measure of information.
Given a distribution $p(xy)$, and a carefully chosen event $W$, Raz measured
the divergence

$\displaystyle\mathop{\mathbb{E}\/}_{p(xy|W)}\Big{[}\mathsf{D}(p(x|yW)||p(x|y))+\mathsf{D}(p(y|xW)||p(y|x))\Big{]}$
$\displaystyle=\mathop{\mathbb{E}\/}_{p(xy|W)}\Big{[}\log\Big{(}\frac{p(x|yW)}{p(x|y)}\cdot\frac{p(y|xW)}{p(y|x)}\Big{)}\Big{]}.$
(1)

In the proof, it is crucial that the event $W$ is _rectangular_ , meaning that
if $x,y$ are independent, then they remain independent even after conditioning
on $W$. Once again, Step 1 is not too difficult. Raz used the subadditivity of
divergence and a similar set of clever random variables as in [Raz92] to split
the dependence and accomplish Step 2. Later, Holenstein [Hol07] introduced a
method called _correlated sampling_ to simplify the analogue of Step 3 in
Raz’s proof, and obtained better bounds. The second author used these tools to
prove optimal bounds for parallel repetition in the setting relevant to
probabilistically checkable proofs [Rao11].

Chakrabarti, Shi, Wirth and Yao [CSWY01] were the first to propose using
general measures of information complexity to address the questions we
consider in this paper. Let $xy$ denote the inputs, $m$ denote the public
randomness and transcript of a communication protocol and $p(xym)$ denote the
joint distribution induced by the protocol222We often say $p(xym)$ is a
protocol when we mean that it is a distribution induced by a protocol..
[CSWY01] proposed to measure the mutual information

$\displaystyle\mathsf{I}(M:XY)=\mathop{\mathbb{E}\/}_{p(xym)}\Big{[}\log\frac{p(xy|m)}{p(xy)}\Big{]}.$

Years later, this measure was renamed _external information_ by [BBCR10]. The
external information measures the information learned by an external observer
about the parties’ inputs. Step 1 is easy for this measure of information.
However, the subadditivity of Step 2 does not hold in general; the proof only
goes through when the input distribution $p(xy)$ is a product distribution.
Jain, Radhakrishnan and Sen [JRS03], and Harsha, Jain, McAllester and
Radhakrishnan [HJMR10] gave ways to implement Step 3 that led to bounds on the
success probability for computing $f^{n}$ in the setting where the inputs are
assumed to come from a product distribution and the communication protocols
are restricted to having a bounded number of rounds. Meanwhile, Bar-yossef,
Jayram, Kumar and Sivakumar [BYJKS02] showed how to reframe Razborov’s proof
using mutual information instead of entropy, and proved other results using
this formulation which contained hints of the definition of information that
came next.

The first upper bounds on the success probability in the general setting came
when the second author together with Barak, Braverman and Chen [BBCR10]
adapted the methods developed in the study of parallel repetition to these
problems. In contrast with the external information, they defined the
_internal information_ , which is the sum of two mutual information terms

$\displaystyle\mathsf{I}(M:X|Y)+\mathsf{I}(M:Y|X)=\mathop{\mathbb{E}\/}_{p(xym)}\Big{[}\log\Big{(}\frac{p(x|ym)}{p(x|y)}\cdot\frac{p(y|xm)}{p(y|x)}\Big{)}\Big{]}.$
(2)

The internal information measures what is learned by each party about the
other’s input. Equation 1 was the inspiration for Equation 2; indeed, each
setting of $m$ corresponds to a rectangular event. When the inputs come from a
product distribution, the internal and external information are the same, and
[BBCR10] proved that subadditivity holds for internal information using an
argument similar to the one used in the context of parallel repetition.
Moreover, they showed how to leverage the technique of correlated sampling
developed by Holenstein to simulate protocols with information $I$ and
communication $C$ using $\approx\sqrt{IC}/\log C$ communication. They gave
near optimal simulations of $\approx I\log^{2}C$ for protocols with small
external information using rejection sampling and a variant of Azuma’s
concentration inequality. These results proved that there is a constant
$\kappa$ such that if $\mathsf{adv}(C,f)\leq 1/2$, then

$\displaystyle\mathsf{adv}(\kappa C\sqrt{n}/\log(Cn),f^{\oplus n})$
$\displaystyle\leq 1/2,$

which was the first result along the lines of Theorem 1. Later, the second
author and Braverman [BR11] argued that this is the _right_ definition of
information, because the internal information cost of a function is equal to
the amortized communication complexity of that function. This suggested that
the internal information might well be the last word in this evolution of
definitions, because it could be defined purely using the concept of
communication complexity. It seemed like the only path to better results was
through better methods to compress internal information. This is a belief we
no longer hold.

Nevertheless, a flurry of ideas about compressing protocols with internal
information $I$ and communication $C$ followed. Braverman [Bra15] showed how
to obtain protocols with communication $\approx 2^{O(I)}$. The second author
and Ramamoorthy [RR15] showed that if $I_{A},I_{B}$ denote the internal
information learned by each party, then you can achieve communication $\approx
I_{A}\cdot 2^{O(I_{B})}$ and can also achieve communication $\approx
I_{A}+\sqrt[4]{I_{B}\cdot C^{3}}$. Two excellent papers, the first by Kol
[Kol16] and the second by Sherstov [She18], showed that $\approx I\log^{2}I$
communication can be achieved when the inputs come from a product
distribution. Ganor, Kol and Raz [GKR16] (see also [RS18]) gave a nice
counterexample: a function that can be computed with communication $\approx
2^{2^{O(I)}}$, and internal information $\approx I$, but cannot be computed
with communication $\approx 2^{I}$.

The next definition to evolve was proposed by the second author together with
Braverman, Weinstein and Yehudayoff [BRWY13b, BRWY13a], inspired by the work
of Jain, Pereszlényi and Yao [JPY12]. Rather than bounding the information
under the distribution $p(xym)$ induced by the protocol, they bounded the
infimum of information achieved in the ball of distributions that are close to
the protocol. They defined the information to be the infimum

$\displaystyle\inf_{q}\mathsf{I}_{q}(M:X|Y)+\mathsf{I}_{q}(M:Y|X)=\inf_{q}\mathop{\mathbb{E}\/}_{q(xym)}\Big{[}\log\Big{(}\frac{q(x|ym)}{q(x|y)}\cdot\frac{q(y|xm)}{q(y|x)}\Big{)}\Big{]},$
(3)

where here the infimum is taken over all distributions $q(xym)$ that are close
to $p(xym)$ in statistical distance. This quantity was ultimately bounded by
setting $q(xym)=p(xym|W)$, where here $W$ is a reasonably large event (not
necessarily rectangular) that implies that the protocol correctly computes the
function. The bound on Equation 3 does not lead to a bound on the information
according to $p(xym)$, because it is quite possible that the points outside
$W$ reveal a huge amount of information. Still, [BRWY13b] were able to follow
all 3 steps of the high-level approach to prove their results. Step 1 remained
easy, but Steps 2 and 3 became more difficult using Equation 3. [BRWY13b]
obtained exponentially small upper bounds for the success probability of
computing $f^{n}$, but did not manage to prove new bounds on the advantage for
$f^{\oplus n}$ using this approach. Equation 3 may not seem very different
from Equation 2, but it does involve a proxy $q$, and we pursue the use of
such proxies further in the definition of marginal information that we discuss
next.

In a paper full of new ideas, Yu [Yu22] recently proved exponentially small
bounds on the advantage of bounded-round protocols computing $f^{\oplus n}$.
Although Yu’s paper involves a potential function that superficially looks
like a definition of information, his proof does not involve a method to
compress protocols whose potential is small, and we are unable to extract a
definition of information from his work. Still, his ideas inspired many of the
choices made in our definition. To define the marginal information, we need
the concept of a rectangular distribution, which was defined in [Yu22]:

######  Definition 2.

Given a set $Q$ consisting of triples $(xym)$, we say that $Q$ is
_rectangular_ if its indicator function can be expressed as

$\mathds{1}_{Q}(xym)=\mathds{1}_{A}(xm)\cdot\mathds{1}_{B}(ym),$

for some Boolean functions $\mathds{1}_{A},\mathds{1}_{B}$. Given a
distribution $q(xym)$ and a distribution $\mu(xy)$, we say that $q$ is
_rectangular with respect to $\mu$_ if it can be expressed as

$q(xym)=\mu(xy)\cdot A(xm)\cdot B(ym),$

for some functions $A,B$.

For intuition, it is helpful to think of a rectangular distribution as the
result of conditioning a protocol distribution $p(xym)$ on a rectangular
event. That would produce a rectangular distribution, but the space of
rectangular distributions actually contains other distributions that cannot be
obtained in this way.

From our perspective, the most useful insight of Yu’s work is that if $q$ is
restricted to being rectangular, then one can allow $q$ to be quite far from
$p$ in Equation 3 and still carry out a meaningful compression of a protocol
$p$ to implement Step 3. That is because the rectangular nature of $q$ allows
the parties to use hashing and rejection sampling to convert a protocol that
samples from $p$ into a protocol that samples from $q$. If $q(xym)=p(xym|R)$
for a rectangular event $R$, this is easy to understand: the parties can
communicate $2$ bits to compute if $xym\in R$ and output the most likely value
of $f$ under $q$ with $xym\in R$. If $xym\notin R$ they can output a random
guess for the value of $f$. So, it is enough to bound the information terms
for $xym\in R$, and enough to guarantee that the compression is efficient for
such points. This observation is very powerful, because it allows us to throw
away problematic points in the support of the distributions we are working
with and pass to appropriate sub-rectangles throughout our proofs.

For all of this to work, it is crucial that the protocol retains some
advantage within the support of $q$. For this reason, we need to keep track of
the information in the support of $q$ as well as the advantage within the
support of $q$, and so, for the first time, the measure of information is
going to depend on the function $f$ that the protocol computes. We are ready
to state the definition:

######  Definition 3.

For $I\geq 1$ and333Even though $\delta$ is a fixed constant, we choose to
write it in the definition because it eases the notation throughout the paper.
$\delta=1/15$, define the _marginal information_ of a protocol $p$ for
computing $f$:

$\displaystyle\mathsf{M}_{I}(p,f)$
$\displaystyle=\inf_{q}\sup_{xym}\log\Big{(}\frac{q(x|ym)}{p(x|y)}\cdot\frac{q(y|xm)}{p(y|x)}\cdot\Big{(}\frac{q(xym)}{p(xym)}\Big{)}^{I}\cdot\Big{|}\mathop{\mathbb{E}\/}_{q(xy|m)}[(-1)^{f(xy)}]\Big{|}^{-12I/\delta}\Big{)},$

where the infimum is taken over all distributions $q$ that are rectangular
with respect to the input distribution $p(xy)$, and the supremum is taken over
all $xym$ in the support of $q$.

We use the letter $I$ above because it turns out that protocols computing $f$
can be efficiently compressed when $\mathsf{M}_{I}=O(I)$, and any compression
must have communication $\Omega(I)$. Compare Definition 3 with Equations 2 and
3. The fact that $q$ must be tethered to $p$ is ensured by including the term
$q(xym)/p(xym)$. If $q(xym)=p(xym|R)$ for a rectangular event $R$,
$q(xym)/p(xym)$ will be equal to $1/p(R)$. The last term in the product
computes the advantage of $q$ for computing $f$, because under $q$ and given
$m$, the best guess for the value of $f$ is determined by the sign of
$\mathop{\mathbb{E}\/}_{q(xy|m)}[(-1)^{f(xy)}]$, and its advantage is the
absolute value of this quantity. In words, the marginal information measures
the supremum over all $xym$ of the information per unit of advantage, of the
best rectangular approximation $q$.

In analogy with the external information, we define the external marginal
information:

######  Definition 4.

For $I\geq 1$ and $\delta=1/15$, define the _external marginal information_ of
a protocol $p$ for computing $f$:

$\displaystyle\mathsf{M}^{\mathsf{ext}}_{I}(p,f)$
$\displaystyle=\inf_{q}\sup_{xym}\log\Big{(}\frac{q(xy|m)}{p(xy)}\cdot\Big{(}\frac{q(xym)}{p(xym)}\Big{)}^{I}\cdot\Big{|}\mathop{\mathbb{E}\/}_{q(xy|m)}[(-1)^{f(xy)}]\Big{|}^{-12I/\delta}\Big{)},$

where the infimum is taken over all distributions $q$ that are rectangular
with respect to the input distribution $p(xy)$, and the supremum is taken over
all $xym$ in the support of $q$.

We prove that the external marginal information is equal to the marginal
information when the distribution on inputs is a product distribution in Lemma
21.

To state our results about marginal information, we first define the average-
case measure of advantage. Given a distribution $\mu(xy)$ on inputs, define

$\displaystyle\mathsf{adv}_{\mu}(C,f)$ $\displaystyle=\sup_{\|\pi\|\leq
C}\mathop{\mathbb{E}\/}[(-1)^{\pi(xy)+f(xy)}],$

where here the expectation is over the choice of inputs $xy$ as well as the
random coins of the communication protocol. To study the more restricted
setting where the protocols we are working with have a bounded number of
rounds, define the worst-case and average case quantities:

$\displaystyle\mathsf{adv}^{r}(C,f)$ $\displaystyle=\sup_{\|\pi\|\leq
C}\inf_{xy}\mathop{\mathbb{E}\/}[(-1)^{\pi(xy)+f(xy)}],$
$\displaystyle\mathsf{adv}^{r}_{\mu}(C,f)$ $\displaystyle=\sup_{\|\pi\|\leq
C}\mathop{\mathbb{E}\/}[(-1)^{\pi(xy)+f(xy)}],$

where throughout, the supremums are taken over $r$-round protocols.

Returning to our high-level approach, we prove the following results about
marginal information, which allow us to carry out Steps 1,2,3:

  1. 1.

In Section 3, we show that a protocol with small communication and large
advantage has small marginal information, to handle Step 1:

######  Theorem 5.

For every Boolean function $f(xy)$ and every protocol $p$ of communication
complexity $C$,

$\mathsf{M}_{I}(p,f)\leq 2C-\left(1+12/\delta\right)\cdot
I\cdot\log\Big{(}\mathop{\mathbb{E}\/}_{p(m)}\Big{|}\mathop{\mathbb{E}\/}_{p(xy|m)}\Big{[}(-1)^{f}\Big{]}\Big{|}\Big{)}+O(I).$

If $\mathsf{adv}_{\mu}(C,f^{\oplus n})\geq\exp(-m)$ via a protocol
corresponding to the distribution $p$, then the above theorem implies that
$\mathsf{M}_{I}(p,f^{\oplus n})\leq O(C+Im)$. Unlike all previous definitions,
for marginal information Step 1 involves significant work. Our proof crucially
uses the fact that the protocol has bounded communication complexity: for
example it would not be enough to start with a bound on the internal
information.

  2. 2.

In Section 4, we prove that marginal information is sub-additive with respect
to the $n$-fold xor of $f$. If the transcript $m=m_{0},m_{1},m_{2},\dotsc$
where $m_{j}$ denotes the $j$’th message of the protocol, we show

######  Theorem 6.

There is a universal constant $\Delta$ such that if $I\geq 1$ and $p$ is a
protocol distribution with $p(xy)=\prod_{i=1}^{n}p(x_{i}y_{i})$, then there is
a protocol $p_{i}$ such that $p_{i}(x_{i}y_{i})=p(x_{i}y_{i})$, $p_{i}$ has
the same number of messages as $p$, for $j>1$ the support of $m_{j}$ is
identical in $p_{i}$ and $p$, and moreover

$\mathsf{M}_{I}(p_{i},f)\leq\frac{\mathsf{M}_{I}(p,f^{\oplus n})}{n}+\Delta
I\cdot\Big{(}1+\log\frac{\mathsf{M}_{I}(p,f^{\oplus n})}{n\cdot I}\Big{)}.$

If $\mathsf{M}_{I}(p,f^{\oplus n})\leq O(In)$, this theorem proves that
$\mathsf{M}_{I}(p_{i},f)\leq O(I)$. This might well be the most technically
novel part of our proof; it is certainly where we spent the most time. The
heart of the matter is the case $n=2$. If $\mathsf{M}_{I}(p,f)$ is small and
$n=2$, then there is rectangular distribution $q$ such that the pair

$q(x_{1}x_{2}y_{1}y_{2}m),p(x_{1}x_{2}y_{1}y_{2}m)$

leads to a small value of $\mathsf{M}_{I}(p,f)$. We show how to use $q,p$ to
generate a new pair

$q(x_{1}y_{1}m^{(1)}),p(x_{1}y_{1}m^{(1)})$

or a new pair

$q(x_{2}y_{2}m^{(2)}),p(x_{2}y_{2}m^{(2)})$

so that the appropriate marginal information is more or less reduced by a
factor of $2$. This is accomplished by Theorem 27, and Theorem 6 is a
straightforward consequence. The proof of Theorem 27 is delicate. A
significant first step is the construction of two pairs of
rectangular/protocol distributions with the properties described in Equations
13, 14, 15 and 16. Given this step, we need to eliminate various problematic
points from the support of the distributions while preserving the rectangular
nature of the distribution to ultimately construct the promised pair of
distributions.

In Theorem 6 we are unable to bound the length of the first message of $p_{i}$
in terms of the length of the corresponding message of $p$, because in our
proof of Theorem 27 the first message $m^{(1)}_{1}$ or $m^{(2)}_{1}$ needs to
encode one of the inputs of the original protocol. Fortunately, this is not a
major obstacle for the high-level strategy.

  3. 3.

In Sections 7, 9, 10 and 11, we show how to compress marginal information to
handle Step 3. We have been able to match many of the prior results [BBCR10,
BR11, Bra15] about compressing information and external information with
corresponding results about compressing marginal information and external
marginal information, though our proofs are much more technical. Our most
general simulation is captured by the following theorem:

######  Theorem 7.

For every $\alpha>0$ there is a $\Delta>0$ such that if
$\mathsf{M}_{I}(p,f)\leq\alpha I$, $\mu(xy)=p(xy)$ and moreover the messages
$m=(m_{0},\dotsc,m_{C})$ are such that $m_{2},\dotsc,m_{C}\in\\{0,1\\}$, then
$\mathsf{adv}_{\mu}(\Delta(I+\sqrt{CI}\log(CI)),f)\geq 1/\Delta$.

Theorem 7 shows that if the marginal information is $O(I)$, then one can
obtain a protocol with communication $\widetilde{O}(\sqrt{CI})$ that has
$\Omega(1)$ advantage for computing $f$. For the external marginal
information, we prove:

######  Theorem 8.

For every $\alpha>0$ there is a $\Delta>0$ such that if
$\mathsf{M}^{\mathsf{ext}}_{I}(p,f)\leq\alpha I$, $\mu(xy)=p(xy)$, and
moreover the messages $m=(m_{0},\dotsc,m_{C})$ are such that
$m_{2},\dotsc,m_{C}\in\\{0,1\\}$, then $\mathsf{adv}_{\mu}(\Delta
I\log^{2}C,f)\geq 1/\Delta$.

This theorem gives improved results when the inputs come from a product
distribution. It is quite possible that even better simulations can be
obtained using the ideas of [Kol16, She18, BK18], but we have not managed to
obtain such results. We also obtain results that are independent of the
communication complexity:

######  Theorem 9.

For every $\alpha>0$ there is a $\Delta>0$ such that if
$\mathsf{M}_{I}(p,f)\leq\alpha I$ and $\mu(xy)=p(xy)$, then
$\mathsf{adv}_{\mu}(\Delta I,f)\geq\exp(-I\Delta)$.

When the number of rounds of the protocol is bounded, we prove:

######  Theorem 10.

For every $\alpha>0$ there is a $\Delta>0$ such that if
$\mathsf{M}_{I}(p,f)\leq\alpha I$, $\mu(xy)=p(xy)$, $p$ has $r$-rounds and
$m_{r}\in\\{0,1\\}$, then $\mathsf{adv}^{r}_{\mu}(\Delta r(I+\log r),f)\geq
1/\Delta$.

These results about the marginal information cost allow us to prove Theorem 1,
as well as several other results of that flavor.

###  1.2 Using marginal information to prove XOR lemmas

To state all of our results, let us define the average-case and worst-case
measures of success:

$\displaystyle\mathsf{suc}(C,f)$ $\displaystyle=\sup_{\|\pi\|\leq
C}\inf_{xy}\mathop{\bf Pr\/}[\pi(xy)=f(xy)]$
$\displaystyle\mathsf{suc}^{r}(C,f)$ $\displaystyle=\sup_{\|\pi\|\leq
C}\inf_{xy}\mathop{\bf Pr\/}[\pi(xy)=f(xy)]$
$\displaystyle\mathsf{suc}_{\mu}(C,f)$ $\displaystyle=\sup_{\|\pi\|\leq
C}\mathop{\bf Pr\/}[\pi(xy)=f(xy)]$ $\displaystyle\mathsf{suc}^{r}_{\mu}(C,f)$
$\displaystyle=\sup_{\|\pi\|\leq C}\mathop{\bf Pr\/}[\pi(xy)=f(xy)],$

where in $\mathsf{suc}^{r},\mathsf{suc}_{\mu}^{r}$ the supremum is taken over
$r$-round protocols, and in $\mathsf{suc}_{\mu},\mathsf{suc}^{r}_{\mu}$ the
probability is over inputs sampled from $\mu(xy)$. Yao’s min-max theorem
yields

$\displaystyle\mathsf{adv}(C,f)$
$\displaystyle=\inf_{\mu}\mathsf{adv}_{\mu}(C,f),$
$\displaystyle\mathsf{suc}(C,f)$
$\displaystyle=\inf_{\mu}\mathsf{suc}_{\mu}(C,f),$
$\displaystyle\mathsf{adv}^{r}(C,f)$
$\displaystyle=\inf_{\mu}\mathsf{adv}^{r}_{\mu}(C,f),$
$\displaystyle\mathsf{suc}^{r}(C,f)$
$\displaystyle=\inf_{\mu}\mathsf{suc}^{r}_{\mu}(C,f).$ (4)

Given any distribution $\mu$ on $\mathcal{X}\times\mathcal{Y}$, define the
$n$-fold product distribution $\mu^{n}$ on
$\mathcal{X}^{n}\times\mathcal{Y}^{n}$ by
$\mu^{n}(xy)=\prod_{j=1}^{n}\mu(x_{j}y_{j})$. Theorem 1 is proved by proving
this stronger bound:

######  Theorem 11.

There is a universal constant $\kappa>0$ such that if $C>1/\kappa$ and
$\mathsf{adv}_{\mu}(C,f)\leq\kappa$, then $\mathsf{adv}_{\mu^{n}}(\kappa
C\sqrt{n}/\log(Cn),f^{\oplus n})\leq\exp(-\kappa n).$

To prove Theorem 11, suppose that there is a protocol $p$ computing $f^{\oplus
n}$ with advantage $\exp(-\kappa n)$ and communication $T=\kappa
C\cdot\sqrt{n}/\log(Cn)$. If $T/n\geq 1$, we set $I=T/n$ and apply Theorem 5
to show that $\mathsf{M}_{I}(p,f^{\oplus n})\leq O(T+\kappa In)\leq O(In)$.
Next, apply Theorem 6 to find a protocol $p^{\prime}$ with
$\mathsf{M}_{I}(p^{\prime},f)\leq O(I)$. Finally, apply Theorem 7 to obtain a
protocol computing $f$ with advantage $\Omega(1)$ and communication
proportional to

$\displaystyle\frac{T}{n}+2\sqrt{IT}\log(T)$
$\displaystyle\leq\frac{T}{n}+2\frac{T\log T}{\sqrt{n}}$
$\displaystyle\lesssim\frac{\kappa C}{\log nC}\cdot\log T\lesssim\kappa C.$

If $T/n<1$, set $I=1$ and apply Theorem 5 to show that
$\mathsf{M}_{I}(p,f^{\oplus n})\leq O(In)$. Next, apply Theorem 6 to find a
protocol $p^{\prime}$ with $\mathsf{M}_{I}(p^{\prime},f)\leq O(I)=O(1)$.
Finally, we apply Theorem 9 to obtain a protocol computing $f$ with advantage
$\Omega(1)$ and communication $O(1)$. Setting $\kappa$ sufficiently small, we
obtain a contradiction in either case, which proves that there is no protocol
$p$ as above. Theorem 1 can be obtained from Theorem 11 using Equation 4 and
the fact that the worst-case success probability of a communication protocol
can be increased by taking the majority outcome of several runs of the
protocol. We leave these details to the reader.

Theorems 1 and 11 yield bounds on the success probability for computing
$f^{n}$ as well:

######  Corollary 12.

There is a universal constant $\kappa>0$ such that if $C>1/\kappa$ and
$\mathsf{adv}(C,f)<\kappa$, then $\mathsf{suc}(\kappa
C\sqrt{n}/\log(Cn)),f^{n})<\exp(-\kappa n)$.

######  Corollary 13.

There is a universal constant $\kappa>0$ such that if $C>1/\kappa$ and
$\mathsf{adv}_{\mu}(C,f)<\kappa$, then $\mathsf{suc}_{\mu^{n}}(\kappa
C\sqrt{n}/\log(Cn)),f^{n})<\exp(-\kappa n)$.

This matches the result proved by [BRWY13b] mentioned earlier. These
corollaries are obtained by observing that if $S\subseteq\\{1,2,\dotsc,n\\}$
is chosen uniformly at random, and $xy$ are sampled according to $\mu^{n}$,
then

$\displaystyle\mathop{\mathbb{E}\/}\Big{[}(-1)^{\sum_{j\in
S}\pi(xy)_{j}+f(x_{j}y_{j})}\Big{]}$ $\displaystyle=\mathop{\bf
Pr\/}[\pi(xy)=f^{n}(xy)],$

so a protocol computing $f^{n}$ with success probability $\exp(-n/2)$ yields a
set of $n^{\prime}=\Omega(n)$ coordinates where the protocol computes
$f^{\oplus n^{\prime}}$ with advantage $\exp(-\Omega(n))$. Again, we leave the
details to the reader. When the distribution $\mu(xy)=\mu(x)\cdot\mu(y)$ is a
product distribution, we obtain stronger bounds:

######  Theorem 14.

There is a universal constant $\kappa>0$ such that for every product
distribution $\mu$, if $C>1/\kappa$ and $\mathsf{adv}_{\mu}(C,f)<\kappa$, then
$\mathsf{adv}_{\mu^{n}}(\kappa Cn/\log^{2}(Cn),f^{\oplus n})<\exp(-\kappa n)$.

To prove Theorem 14, suppose we are given a protocol $p$ computing $f^{\oplus
n}$ with advantage $\exp(-\kappa n)$ and communication $T=\kappa
Cn/\log^{2}(Cn)$. If $T/n\geq 1$, we set $I=T/n$ and apply Theorem 5 to show
that $\mathsf{M}_{I}(p,f^{\oplus n})\leq O(nI)$. Next, apply Theorem 6 to find
a protocol $p^{\prime}$ with $\mathsf{M}_{I}(p^{\prime},f)\leq O(I)$. Finally,
using the fact that for product distributions,
$\mathsf{M}^{\mathsf{ext}}_{I}(p,f)=\mathsf{M}_{I}(p,f)$, we can apply Theorem
8 to obtain a protocol computing $f$ with advantage $\Omega(1)$ and
communication $O(I\log^{2}(Cn))\leq O(\kappa C)$. Otherwise, if $T/n<1$, set
$I=1$ and apply Theorem 5 to show that $\mathsf{M}_{I}(p,f^{\oplus n})\leq
O(n)$. Then, apply Theorem 6 to find a protocol $p^{\prime}$ with
$\mathsf{M}_{I}(p^{\prime},f)\leq O(I)=O(1)$. Lastly, we apply Theorem 9 to
obtain a protocol computing $f$ with advantage $\Omega(1)$ and communication
$O(1)$. Setting $\kappa$ to be small enough gives a contradiction in either
case.

As before, this yields a corollary for computing $f^{n}$:

######  Corollary 15.

There is a universal constant $\kappa>0$ such that for every product
distribution $\mu$, if $C>1/\kappa$ and $\mathsf{adv}_{\mu}(C,f)<\kappa$, then
$\mathsf{suc}_{\mu^{n}}(\kappa Cn/\log^{2}(Cn),f^{n})<\exp(-\kappa n).$

Again, this is identical to a bound proved by [BRWY13b] using a different
approach. For the bounded-round setting, we prove:

######  Theorem 16.

There is a universal constant $\kappa>0$ such that if $C>(r(\log
r)+1)/\kappa$, and $\mathsf{adv}^{r}_{\mu}(C,f)<\kappa$, then
$\mathsf{adv}^{r}_{\mu^{n}}((\kappa C/r-\log r)n,f^{\oplus n})<\exp(-\kappa
n).$

Yu [Yu22] proves the same bound on the advantage with a communication budget
that grows like $\Omega((C/r^{r}-O(1))n)$. Our bound eliminates the
exponential dependence on $r$. To prove Theorem 14, set $T=(\kappa C/r-\log
r)n$, and suppose there is a protocol computing $f$ with $r$ rounds,
communication $T$ and advantage $\exp(-\kappa n)$. Set $I=T/n\geq 1$. Then,
$\mathsf{M}_{I}$ can be bounded by $O(T+\kappa In)$ by Theorem 5. Applying
Theorem 6 gives an $r$-round protocol with $\mathsf{M}_{I}$ bounded by $O(I)$,
and applying Theorem 10 gives an $r$-round protocol with communication
complexity $O(r(I+\log r))=O(\kappa C)$ computing $f$ with advantage
$\Omega(1)$. Setting $\kappa$ to be small enough proves the result. As usual,
we obtain the following corollaries:

######  Corollary 17.

There is a universal constant $\kappa>0$ such that if $C>7(r\log r)/\kappa$
and $\mathsf{adv}^{r}_{\mu}(C,f)<\kappa$, then
$\mathsf{suc}^{r}_{\mu^{n}}((\kappa C/r-\log r)n,f^{n})<\exp(-\kappa n).$

######  Corollary 18.

There is a universal constant $\kappa>0$ such that if $C>7(r\log r)/\kappa$,
and $\mathsf{adv}^{r}(C,f)<\kappa$, then $\mathsf{suc}^{r}((\kappa C/r-\log
r)n,f^{n})<\exp(-\kappa n).$

In the rest of the paper, we prove Theorems 5, 6, 7, 8, 10 and 9. We prove
Theorem 5 in Section 3, and Theorem 6 in Section 4. In Section 5 we gather
several results related to the _trimming_ technique borrowed from [Yu22] that
are used in these first two steps. In Section 6 we gather several consequences
of small marginal information that are used to analyze our compression
schemes. We prove the general simulation for marginal information, Theorem 7,
in Section 7. In Section 8 we prove that if the external marginal information
is small, then there is a _smooth_ protocol with small external marginal
information, mirroring a similar result in [BBCR10]. We then show how to
compress smooth protocols to prove Theorem 8 in Section 9. We prove Theorem 10
in Section 10 and finally, in Section 11 we prove Theorem 9.

### Acknowledgements

Thanks to Paul Beame, Makrand Sinha, Oscar Sprumont, Michael Whitmeyer and
Amir Yehudayoff for helpful conversations.

##  2 Preliminaries

Throughout, we assume that $x\in\mathcal{X}$, $y\in\mathcal{Y}$ and
$m\in\mathcal{M}$ for some finite sets $\mathcal{X},\mathcal{Y},\mathcal{M}$.
Let $\mu(xy)$ be a distribution on pairs of inputs. To ease the notation, we
often write $ab$ instead of the tuple $(a,b)$. Everywhere in the paper, we
assume that $\delta>0$ is a sufficiently small constant; $\delta=1/15$ will
suffice.

######  Definition 19.

We say that $p(xym)$ is a protocol distribution if it can be expressed as

$p(xym)=p(xy)\cdot p(m_{0})\cdot\prod_{i=1,3,5,\dotsc}p(m_{i}|xm_{<i})\cdot
p(m_{i+1}|ym_{\leq i}).$

Every randomized worst-case protocol corresponds to some protocol distribution
$p(xym)$, where $p(xy)$ can be taken to be the uniform distribution on all
possible inputs. Given a distribution $\mu(xy)$ on inputs, and any protocol
generating the messages $m$, the joint distribution of $xym$ corresponds again
to a protocol distribution $p(xym)$, with $p(xy)=\mu(xy)$.

Recall Definition 2. Note that if $q$ is rectangular with respect to $\mu(xy)$
and $p$ is a protocol with $p(xy)=\mu(xy)$, it is not necessary that
$q(xy)=\mu(xy)$. For the purpose of intuition, it may be helpful to think of a
rectangular distribution as the result of conditioning $\mu(xy)$ on the event
that it lies in a disjoint union of rectangles indexed by $m$, though this
statement is not without loss of generality, and we do use the full generality
of Definition 2.

Let $x=x_{1}x_{2}$ and $y=y_{1}y_{2}$. Let
$\mu(xy)=\mu(x_{1}y_{1})\cdot\mu(x_{2}y_{2})$ be a product distribution. It
will be helpful to define $w=(x_{1}y_{2}m)$. Given $m=(m_{0},\ldots,m_{r})$
and $y_{2}$, we denote

$\displaystyle m^{(1)}$ $\displaystyle=(m_{0}y_{2},m_{1},m_{2},\ldots,m_{r}),$
$\displaystyle m^{(2)}$ $\displaystyle=(m_{0},x_{1}m_{1},m_{2},\ldots,m_{r}).$
(5)

Let us gather some basic facts about rectangular distributions in this
setting:

######  Proposition 20.

If $v$ is rectangular, then

  1. 1.

$v(xy|w)=v(y_{1}|w)\cdot v(x_{2}|w)$,

  2. 2.

$v(xw)\cdot v(yw)=v(xym)\cdot v(w)$,

  3. 3.

$v(x_{1}|y_{1}m^{(1)})\cdot v(x_{2}|y_{2}m^{(2)})=v(x|ym)$, and

  4. 4.

$v(y_{1}|x_{1}m^{(1)})\cdot v(y_{2}|x_{2}m^{(2)})=v(y|xm)$.

###### Proof.

For the first identity, let $A,B$ be such that $v(xym)=\mu(xy)\cdot A(xm)\cdot
B(ym)$. Then

$\displaystyle v(xy|w)=\frac{v(xyw)}{v(w)}$
$\displaystyle=\frac{\mu(x_{1}y_{1})\cdot\mu(x_{2}y_{2})\cdot A(xm)\cdot
B(ym)}{\sum_{x^{\prime}_{2}y^{\prime}_{1}}\mu(x_{1}y^{\prime}_{1})\cdot\mu(x^{\prime}_{2}y_{2})\cdot
A(x_{1}x^{\prime}_{2}m)\cdot B(y^{\prime}_{1}y_{2}m)}$
$\displaystyle=\frac{\mu(x_{1}y_{1})\cdot
B(y_{1}y_{2}m)}{\sum_{y^{\prime}_{1}}\mu(x_{1}y^{\prime}_{1})\cdot
B(y^{\prime}_{1}y_{2}m)}\cdot\frac{\mu(x_{2}y_{2})\cdot
A(x_{1}x_{2}m)}{\sum_{x^{\prime}_{2}}\mu(x^{\prime}_{2}y_{2})\cdot
A(x_{1}x^{\prime}_{2}m)}$ $\displaystyle=v(y_{1}|w)\cdot v(x_{2}|w).$

For the second identity,

$\displaystyle v(xw)\cdot v(yw)$ $\displaystyle=v(w)\cdot v(yw)\cdot v(x|w)$
$\displaystyle=v(w)\cdot v(yw)\cdot v(x_{2}|x_{1}ym)$ (by the first identity)
$\displaystyle=v(w)\cdot v(xym).$

For the third identity,

$\displaystyle v(x_{1}|y_{1}m^{(1)})\cdot v(x_{2}|y_{2}m^{(2)})$
$\displaystyle=v(x_{1}|ym)\cdot v(x_{2}|x_{1}y_{2}m)$
$\displaystyle=v(x_{1}|ym)\cdot v(x_{2}|x_{1}ym)$ (by the first identity)
$\displaystyle=v(x|ym).$

A similar calculation yields the fourth identity. ∎

It is easy to check that the external marginal inforamtion and marginal
information are the same when the distribution on inputs is product:

######  Lemma 21.

If $p(xy)=\mu(xy)$ is a product distribution then we have
$\mathsf{M}^{\mathsf{ext}}_{I}(p,f)=\mathsf{M}_{I}(p,f).$

###### Proof.

For all rectangular $q$, we have

$\displaystyle q(xy|m)$ $\displaystyle=\frac{q(xym)}{q(m)}$
$\displaystyle=\frac{\mu(xy)\cdot A(xm)\cdot
B(ym)}{\sum_{x^{\prime}y^{\prime}}\mu(x^{\prime}y^{\prime})\cdot
A(x^{\prime}m)\cdot B(y^{\prime}m)}$ $\displaystyle=\frac{\mu(x)\mu(y)\cdot
A(xm)\cdot
B(ym)}{\sum_{x^{\prime}y^{\prime}}\mu(x^{\prime})\mu(y^{\prime})\cdot
A(x^{\prime}m)\cdot B(y^{\prime}m)}$ $\displaystyle=\frac{\mu(x)\cdot
A(xm)}{\sum_{x^{\prime}}\mu(x^{\prime})\cdot
A(x^{\prime}m)}\cdot\frac{\mu(y)\cdot
B(ym)}{\sum_{y^{\prime}}\mu(y^{\prime})\cdot B(y^{\prime}m)},$

proving that $q(xy|m)$ is a product distribution.

Thus:

$\frac{q(x|ym)}{p(x|y)}\cdot\frac{q(y|xm)}{p(y|x)}=\frac{q(xy|m)}{p(xy)},$

and so $\mathsf{M}^{\mathsf{ext}}(p,f)=\mathsf{M}_{I}(p,f)$. ∎

We recall the definition of divergence and some relevant facts from
information theory.

######  Definition 22.

Given two distributions $a(u)$ and $b(u)$, the divergence of $a$ from $b$ is
defined as

$\mathop{\mathbb{E}\/}_{a(u)}\bigg{[}\log\frac{a(u)}{b(u)}\bigg{]}.$

######  Proposition 23.

For two distributions $a(u)$ and $b(u)$, we have that

$\displaystyle\mathop{\mathbb{E}\/}_{a(u)}\bigg{[}\log\frac{a(u)}{b(u)}\bigg{]}$
$\displaystyle\geq 0,$ (6)
$\displaystyle\sqrt{\mathop{\mathbb{E}\/}_{a(u)}\bigg{[}\log\frac{a(u)}{b(u)}\bigg{]}}$
$\displaystyle\geq\frac{\|a(u)-b(u)\|_{1}}{2}.$ (7)

The proof of this proposition can be found in [CT91].

The following version of a protocol due to [BR11] appears as Lemma 43 in
[Yu22], the parameters we cite here are clear from the proof.

######  Lemma 24.

Let $u,v$ denote two distributions on some finite set $\mathcal{M}$. For every
$\varepsilon>0$, there is a $1$-round protocol distribution $\pi(uvs)$ (here
$uv$ correspond to the inputs of the protocol, and $s$ corresponds to the
transcript), and functions
$a(us)\in\mathcal{M},b(vs)\in\mathcal{M}\cup\\{\bot\\}$ (here
$\bot\notin\mathcal{M}$), such that $\pi(uv)$ is supported on all pairs $uv$
and for every $uv$ and $z\in\mathcal{M}$,

  1. 1.

$\pi(a(us)=z|uv)=u(z)$,

  2. 2.

$\pi(a(us)\neq
b(vs)|uv,a(us))\leq\varepsilon+\max\\{0,1-2^{L}\cdot\frac{v(a(us))}{u(a(us))}\\}$.

  3. 3.

$\pi\left(b(vs)\notin\\{a(us),\bot\\}|uv\right)\leq\varepsilon$.

Moreover, the communication complexity of $\pi$ is $L+\log\log
1/\varepsilon+\log 1/\varepsilon+O(1)$.

Additionally, we need the following Lemma, which appears as Lemma 4.14 in
[BBCR10].

######  Lemma 25.

There is a randomized protocol $\tau$ with communication complexity at most
$O(\log(C/\varepsilon))$ such that on input two $C$-bit strings $m^{A},m^{B}$,
it outputs the first index $i\in[C]$ such that $m^{A}_{i}\neq m^{B}_{i}$ with
probability at least $1-\varepsilon$, if such an $i$ exists.

##  3 Marginal information of efficient protocols

In this section, we prove Theorem 5. Let $R$ be a rectangular set that
maximizes the quantity

$p(R)^{\delta}\cdot\mathop{\mathbb{E}\/}_{p(m|R)}\Big{|}\mathop{\mathbb{E}\/}_{p(xy|mR)}\Big{[}(-1)^{f}\Big{]}\Big{|}.$

We shall use trimming to prove the following claim:

######  Claim 26.

There exists a rectangular set $T\subseteq R$ with $p(T|R)\geq 1/4$ such that
for any $xym$ in the support of $T$, we have

$\displaystyle\frac{p(xym|T)}{p(xym)}$ $\displaystyle\leq\frac{4}{p(R)},$
$\displaystyle\log\frac{p(x|ymT)}{p(x|y)},\log\frac{p(y|xmT)}{p(y|x)}$
$\displaystyle\leq\frac{96\cdot 2^{C}}{p(R)},$
$\displaystyle\mathop{\mathbb{E}\/}_{p(m|T)}\Big{|}\mathop{\mathbb{E}\/}_{p(xy|mT)}\Big{[}(-1)^{f}\Big{]}\Big{|}$
$\displaystyle\geq\frac{\Omega(1)}{p(R)^{\delta}}\cdot\mathop{\mathbb{E}\/}_{p(m)}\Big{|}\mathop{\mathbb{E}\/}_{p(xy|m)}\Big{[}(-1)^{f}\Big{]}\Big{|}.$

We defer the proof of the above claim to the end of this section. Let
$Q\subseteq T$ be the sub-rectangle obtained by keeping only the messages
$m^{\prime}$ for which the advantage is at least half of the average
advantage:

$Q=\Big{\\{}x^{\prime}y^{\prime}m^{\prime}\in
T:\Big{|}\mathop{\mathbb{E}\/}_{p(xy|m^{\prime}T)}\Big{[}(-1)^{f}\Big{]}\Big{|}\geq\frac{1}{2}\cdot\mathop{\mathbb{E}\/}_{p(m|T)}\Big{|}\mathop{\mathbb{E}\/}_{p(xy|mT)}\Big{[}(-1)^{f}\Big{]}\Big{|}\Big{\\}}.$

Observe that

$\displaystyle\mathop{\mathbb{E}\/}_{p(m|T)}\Big{|}\mathop{\mathbb{E}\/}_{p(xy|mT)}\Big{[}(-1)^{f}\Big{]}\Big{|}$
$\displaystyle<p(Q|T)+\sum_{m^{\prime}:p(m^{\prime}|Q)=0}p(m^{\prime}|T)\cdot\frac{1}{2}\cdot\mathop{\mathbb{E}\/}_{p(m|T)}\Big{|}\mathop{\mathbb{E}\/}_{p(xy|mT)}\Big{[}(-1)^{f}\Big{]}\Big{|}$
$\displaystyle\leq
p(Q|T)+\frac{1}{2}\cdot\mathop{\mathbb{E}\/}_{p(m|T)}\Big{|}\mathop{\mathbb{E}\/}_{p(xy|mT)}\Big{[}(-1)^{f}\Big{]}\Big{|},$

and so by the choice of $R$,

$\displaystyle p(Q|T)$
$\displaystyle\geq\frac{1}{2}\cdot\mathop{\mathbb{E}\/}_{p(m|T)}\Big{|}\mathop{\mathbb{E}\/}_{p(xy|mT)}\Big{[}(-1)^{f}\Big{]}\Big{|}\geq\frac{\Omega(1)}{p(R)^{\delta}}\cdot\mathop{\mathbb{E}\/}_{p(m)}\Big{|}\mathop{\mathbb{E}\/}_{p(xy|m)}\Big{[}(-1)^{f}\Big{]}\Big{|}.$
(8)

Define the rectangular distribution $q(xym)=p(xym|Q)$. By the definition of
$Q$ and 26, we have that for all $m$ in the support of $q$:

$\displaystyle\Big{|}\mathop{\mathbb{E}\/}_{p(xy|mQ)}\Big{[}(-1)^{f}\Big{]}\Big{|}\geq\frac{1}{2}\cdot\mathop{\mathbb{E}\/}_{p(m|T)}\Big{|}\mathop{\mathbb{E}\/}_{p(xy|mT)}\Big{[}(-1)^{f}\Big{]}\Big{|}\geq\frac{\Omega(1)}{p(R)^{\delta}}\cdot\mathop{\mathbb{E}\/}_{p(m)}\Big{|}\mathop{\mathbb{E}\/}_{p(xy|m)}\Big{[}(-1)^{f}\Big{]}\Big{|}.$
(9)

Using 26, 8 and 9 and the definition of $Q$, we can bound the marginal
information cost by

$\displaystyle 2^{\mathsf{M}(p,f)}$
$\displaystyle\leq\sup_{xym}\left(\frac{p(x|ymQ)}{p(x|y)}\cdot\frac{p(y|xmQ)}{p(y|x)}\right)\cdot\left(\frac{p(xym|Q)}{p(xym)}\right)^{I}\cdot\left(\Big{|}\mathop{\mathbb{E}\/}_{p(xy|mQ)}\Big{[}(-1)^{f}\Big{]}\Big{|}\right)^{-12I/\delta}$
$\displaystyle\leq\sup_{xym}\left(\frac{p(x|ymT)}{p(x|y)}\cdot\frac{p(y|xmT)}{p(y|x)}\right)\cdot\left(\frac{p(xym|T)}{p(xym)\cdot
p(Q|T)}\right)^{I}\cdot\left(\Big{|}\mathop{\mathbb{E}\/}_{p(xy|mQ)}\Big{[}(-1)^{f}\Big{]}\Big{|}\right)^{-12I/\delta}$
$\displaystyle\leq O(1)\cdot 2^{2C}\cdot p(R)^{-2}\cdot 2^{O(I)}\cdot
p(R)^{-I(1-\delta)+12I}\cdot\left(\mathop{\mathbb{E}\/}_{p(m)}\Big{|}\mathop{\mathbb{E}\/}_{p(xy|m)}\Big{[}(-1)^{f}\Big{]}\Big{|}\right)^{-I(1+12/\delta)}$
$\displaystyle\leq O(1)\cdot 2^{2C}\cdot
2^{O(I)}\cdot\left(\mathop{\mathbb{E}\/}_{p(m)}\Big{|}\mathop{\mathbb{E}\/}_{p(xy|m)}\Big{[}(-1)^{f}\Big{]}\Big{|}\right)^{-I(1+12/\delta)},$

where in the last inequality we used the fact that $I(12+\delta-1)-2>0$ since
$I\geq 1$. This completes the proof of the theorem.

It only remains to prove 26. We have

$\mathop{\mathbb{E}\/}_{p(ym|R)}\left[\frac{1}{p(m|y)}\right]=\sum_{ym}\frac{p(ym|R)}{p(m|y)}\leq\frac{1}{p(R)}\sum_{ym}\frac{p(ym)}{p(m|y)}=\frac{\sum_{ym}p(y)}{p(R)}\leq\frac{2^{C}}{p(R)},$

since the communication complexity of $p$ is bounded by $C$. A similar
argument proves

$\mathop{\mathbb{E}\/}_{p(xm|R)}\left[\frac{1}{p(m|x)}\right]\leq\frac{2^{C}}{p(R)}.$

Define the rectangular set

$G=\left\\{xym\in R:\frac{1}{p(m|y)},\frac{1}{p(m|x)}\leq
4\cdot\frac{2^{C}}{p(R)}\right\\}.$

Markov’s inequality implies that $p(G|R)\geq 1/2$. We apply Lemma 29 with
$a(xym)=p(xym|G)$, $b(xym)=p(xym)$, and $\kappa=1/6$ to obtain a rectangular
set $T\subseteq G$ with $p(T|G)\geq 1/2$ and

$\displaystyle\frac{p(xm|T)}{p(xm)},\frac{p(ym|T)}{p(ym)}\geq\frac{1}{6},$
(10)

for all points in the support of $T$. We compute

$p(T|R)=p(G|R)\cdot p(T|G)\geq\frac{1}{4}.$

Let us verify that $T$ satisfies the remaining conditions promised by 26. We
have

$\frac{p(xym|T)}{p(xym)}=\frac{1}{p(T)}=\frac{1}{p(T|R)\cdot
p(R)}\leq\frac{4}{p(R)}.$

To prove the second identity, use the first identity, the definition of $G$
and Equation 10:

$\displaystyle\frac{p(x|ymT)}{p(x|y)}$
$\displaystyle=\frac{1}{p(ym|T)}\cdot\frac{p(xym|T)}{p(x|y)}$
$\displaystyle\leq\frac{6}{p(ym)}\cdot\frac{4\cdot p(xym)}{p(x|y)\cdot p(R)}$
$\displaystyle=\frac{24\cdot p(m|xy)}{p(m|y)\cdot p(R)}$
$\displaystyle\leq\frac{96\cdot 2^{C}}{p(R)}.$

A similar calculation yields

$\displaystyle\frac{p(y|xmT)}{p(y|x)}\leq\frac{96\cdot 2^{C}}{p(R)}.$

Finally, applying Lemma 30 with $v(xym)=p(xym)$, $Z=T$, and noting that
$p(Z|R)\geq 1/4$, we get

$\displaystyle\mathop{\mathbb{E}\/}_{p(m|T)}\Big{|}\mathop{\mathbb{E}\/}_{p(xy|mT)}\Big{[}(-1)^{f}\Big{]}\Big{|}$
$\displaystyle\geq\frac{1-\delta^{2}-4\delta}{p(R)^{\delta}}\cdot\mathop{\mathbb{E}\/}_{p(m)}\Big{|}\mathop{\mathbb{E}\/}_{p(xy|m)}\Big{[}(-1)^{f}\Big{]}\Big{|}$
$\displaystyle\geq\frac{\Omega(1)}{p(R)^{\delta}}\cdot\mathop{\mathbb{E}\/}_{p(m)}\Big{|}\mathop{\mathbb{E}\/}_{p(xy|m)}\Big{[}(-1)^{f}\Big{]}\Big{|}.$

This completes the proof of 26.

##  4 Marginal information is subadditive

In this section we prove Theorem 6. Recall the definitions of
$m^{(1)},m^{(2)}$, which are given in Equation 5. The core of the proof is the
following statement.

######  Theorem 27.

Let $f(x_{1}y_{1})$ and $g(x_{2}y_{2})$ be two Boolean functions and let
$p(xym)$ be a protocol distribution. Then, for every $1/3\leq\gamma\leq 2/3$,
there are protocol distributions $p_{1}(x_{1}y_{1}m^{(1)})$,
$p_{2}(x_{2}y_{2}m^{(2)})$ such that $p_{1}(x_{1}y_{1})=p(x_{1}y_{1})$,
$p_{2}(x_{2}y_{2})=p(x_{2}y_{2})$, and

$\displaystyle\min\big{\\{}\mathsf{M}_{I}(p_{1},f)-\gamma\cdot\mathsf{M}_{I}(p,f\oplus
g),\mathsf{M}_{I}(p_{2},g)-(1-\gamma)\cdot\mathsf{M}_{I}(p,f\oplus
g)\big{\\}}$ $\displaystyle\qquad\leq
3I\cdot\log\frac{\mathsf{M}_{I}(p,f\oplus g)}{I}+O(I).$

We shall prove Theorem 6 assuming Theorem 27, whose proof we supply right
after.

### Proof of Theorem 6

Let $k_{0}>1$ be a large constant, to be determined. Define
$f_{i}(x_{i}y_{i})=f(x_{i}y_{i})$. For $\ell=0,1,2,\dotsc,n$, define

$k(\ell)=\max\Big{\\{}\inf_{\begin{subarray}{c}S\subset[n],|S|=\ell\\\
p^{\prime}\end{subarray}}\mathsf{M}(p^{\prime},\oplus_{i\in
S}f_{i}),k_{0}I\Big{\\}},$

where the infimum is taken over all protocols $p^{\prime}$ with $C$ messages
such that the support of $m_{2},\dotsc,m_{C}$ is the same as in $p$. Define

$T=\max\\{k(n),k_{0}nI\\}.$

Note that

$k(n)\leq T\leq\frac{nT}{n}+12I\cdot\log\frac{nT}{I\cdot n}.$

For any $\ell>1$, suppose we have

$\displaystyle k(\ell)\leq\frac{\ell T}{n}+12I\cdot\log\frac{\ell T}{In},$
(11)

then set $\gamma=\lceil\ell/2\rceil/\ell$. Since $1/3\leq\gamma\leq 2/3$, for
$k_{0}$ chosen large enough, Theorem 27 shows that for some
$\ell^{\prime}\in\\{\lceil\ell/2\rceil,\lfloor\ell/2\rfloor\\}$, we have

$\displaystyle k(\ell^{\prime})$
$\displaystyle\leq\max\\{\frac{\ell^{\prime}}{\ell}\cdot
k(\ell)+3I\log\frac{k(\ell)}{I},k_{0}I\\}$
$\displaystyle\leq\frac{\ell^{\prime}}{\ell}\cdot\frac{\ell
T}{n}+\frac{\ell^{\prime}}{\ell}\cdot 12I\cdot\log\frac{\ell
T}{In}+3I\log\Big{(}\frac{\ell T}{In}+12\log\frac{\ell T}{In}\Big{)}$ (by the
choice of $T$ and Equation 11)
$\displaystyle\leq\frac{\ell^{\prime}T}{n}+8I\cdot\log\frac{\ell
T}{In}+3I\log\Big{(}13\cdot\frac{\ell T}{In}\Big{)}$
$\displaystyle=\frac{\ell^{\prime}T}{n}+11I\cdot\log\frac{\ell^{\prime}T}{In}+11I\cdot\log\frac{\ell}{\ell^{\prime}}+3I\log
13$
$\displaystyle\leq\frac{\ell^{\prime}T}{n}+11I\cdot\log\frac{\ell^{\prime}T}{In}+11I\cdot\log\frac{3}{2}+3I\log
13$
$\displaystyle\leq\frac{\ell^{\prime}T}{n}+12I\cdot\log\frac{\ell^{\prime}T}{In},$

for $k_{0}$ chosen large enough.

So, starting with $\ell=n$, we obtain a smaller and smaller $\ell$ satisfying
Equation 11, until $\ell=1$, which completes the proof.

### Proof of Theorem 27

Given a Boolean function $h(xy)$, a protocol distribution $p(xym)$ and
$q(xym)$ that is rectangular with respect to $p(xy)$, it will be convenient to
define

$\mathsf{M}(q,p,h)=\sup_{xym\in\mathsf{supp}(q)}\log\Bigg{(}\frac{q(x|ym)}{p(x|y)}\cdot\frac{q(y|xm)}{p(y|x)}\cdot\bigg{(}\frac{q(xym)}{p(xym)}\bigg{)}^{I}\cdot\bigg{|}\mathop{\mathbb{E}\/}_{q(xy|m)}\left[(-1)^{h}\right]\bigg{|}^{-12I/\delta}\Bigg{)},$

so $\mathsf{M}(p,h)=\inf_{q}\mathsf{M}(q,p,h)$. We shall prove that there are
protocol distributions $p_{1}(x_{1}y_{1}m^{(1)})$, $p_{2}(x_{2}y_{2}m^{(2)})$
with $p_{1}(x_{1}y_{1})=p(x_{1}y_{1})$ and $p_{2}(x_{2}y_{2})=p(x_{2}y_{2})$
and rectangular distributions $r_{1},r_{2}$ such that

$\displaystyle\min\big{\\{}\mathsf{M}_{I}(r_{1},p_{1},f)-\gamma\cdot\mathsf{M}_{I}(q,p,f\oplus
g),\mathsf{M}_{I}(r_{2},p_{2},g)-(1-\gamma)\cdot\mathsf{M}_{I}(q,p,f\oplus
g)\big{\\}}$ $\displaystyle\qquad\leq
3I\cdot\log\frac{\mathsf{M}_{I}(q,p,f\oplus g)}{I}+O(I),$

from which the theorem follows.

Before we give the actual proof, let us give a high level overview of all the
steps. Recall the definitions of $m^{(1)},m^{(2)}$ and $w$, given in the
preliminaries. We start by defining rectangular distributions
$q_{1}(x_{1}y_{1}m^{(1)}),q_{2}(x_{2}y_{2}m^{(2)})$ and protocol distributions
$p_{1}(x_{1}y_{1}m^{(1)}),p_{2}(x_{2}y_{2}m^{(2)})$ that satisfy the
identities described in Equations 13, 14, 15 and 16. The distributions
$q_{1},q_{2}$ are not be the same as our final rectangular distributions
$r_{1},r_{2}$, but they are closely related. We would like to prove that

$\mathsf{M}(q_{1},p_{1},f)+\mathsf{M}(q_{2},p_{2},g)\leq\mathsf{M}(q,p,f\oplus
g),$

but the advantage terms do not add nicely in the marginal information cost: in
Equation 16, the advantage is computed with respect to $w$, and not
$m^{(1)},m^{(2)}$ or $m$. For example, there may be some $mw$ in the support
for which

$\left|\mathop{\mathbb{E}\/}_{q(xy|w)}\left[(-1)^{f\oplus
g}\right]\right|\ll\left|\mathop{\mathbb{E}\/}_{q(xy|m)}\left[(-1)^{f\oplus
g}\right]\right|.$

To resolve this issue, we define a subset $G$ whose indicator function
$1_{G}(xym)$ depends only on $w$, and yet for all $mw$ in the support of $G$,
the advantage is preserved in the sense of Equation 18. This allows us to
convert the advantage term in $\mathsf{M}(q,p,f\oplus g)$ into the kind of
term where Equation 16 can be applied, and we use it to get subadditivity as
described in Equation 19. This equation shows that the costs add up pointwise,
and so we can pass to a large subset $U\cap L$ where the costs in, say, the
first coordinate are a $\gamma$-fraction of the total, see Equation 20. We are
left with our final obstacle: once again the advantage term that we have
control over is not exactly the one we want, it may well be that

$\displaystyle\Big{|}\mathop{\mathbb{E}\/}_{q_{1}(x_{1}y_{1}|m^{(1)})}\Big{[}(-1)^{f}\Big{]}\Big{|}\ll\Big{|}\mathop{\mathbb{E}\/}_{q_{1}(x_{1}y_{1}|w)}\Big{[}(-1)^{f}\Big{]}\Big{|}.$

To address this, we show that after passing to a suitable set $U^{\prime}\cap
L^{\prime}$ (whose indicator function depends only on $w$), the advantage for
each fixed $w$ is at least $2^{-\Omega(\mathsf{M}(q,p,f\oplus g)}$ (28). We
then cluster the $w$ and pass to a subset $B$ of density
$\Omega(\mathsf{M}(q,p,f\oplus g)^{-1})$ where the advantage terms for each
$w$ are within a factor of $2$ of each other. The low density of this set is
what leads to the $\log\mathsf{M}$ factor in the statement of the theorem.
This allows us to show that the advantage with respect to $m^{(1)}$ is
comparable to the advantage with respect to $w$ (Equation 23). All of these
steps leave us with a subset of the inputs $xym$ where the proof gives good
control on the quantity $\mathsf{M}(q_{1},p_{1},f)$, but we now need to define
a distribution $r_{1}$ supported on these points where
$\mathsf{M}(r_{1},p_{1},f)$ can be bounded. To do this we need to carefully
control the sizes of all the sets we encounter during the proof, and define
the distribution of $r_{1}$ carefully.

Now we begin the actual proof. Define

$\displaystyle q_{1}(x_{1}y_{1}m^{(1)})$
$\displaystyle=q(x_{1}y_{1}m^{(1)})=q(yw)$ $\displaystyle
q_{2}(x_{2}y_{2}m^{(2)})$ $\displaystyle=q(x_{2}y_{2}m^{(2)})=q(xw)$
$\displaystyle p_{1}(x_{1}y_{1}m^{(1)})$ $\displaystyle=p(x_{1}y_{1})\cdot
q(m_{0}y_{2})\cdot\prod_{i=1,3,5,\dotsc}q(m_{i}|x_{1}y_{2},m_{<i})\cdot
p(m_{i+1}|ym_{\leq i})$ $\displaystyle p_{2}(x_{2}y_{2}m^{(2)})$
$\displaystyle=p(x_{2}y_{2})\cdot p(m_{0})\cdot
q(x_{1}|m_{0}y_{2})\cdot\prod_{i=1,3,5,\dotsc}p(m_{i}|xm_{<i})\cdot
q(m_{i+1}|x_{1}y_{2}m_{\leq i})$

These distributions have been carefully chosen to have many nice properties.
First, observe that $q_{1}(x_{1}y_{1}m^{(1)}),q_{2}(x_{2}y_{2}m^{(2)})$ are
rectangular and $p_{1}(x_{1}y_{1}m^{(1)}),p_{2}(x_{2}y_{2}m^{(2)})$ are
protocol distributions. Using the fact that $p$ is a protocol and $x_{1}y_{1}$
and $x_{2}y_{2}$ are independent under $p$, we can compute:

$\displaystyle p_{1}(x_{1}y_{1}m^{(1)})\cdot p_{2}(x_{2}y_{2}m^{(2)})$
$\displaystyle=p(xy)\cdot p(m_{0})\cdot
q(x_{1}y_{2}m_{0})\cdot\prod_{i>0}p(m_{i}|xym_{<i})\cdot
q(m_{i}|x_{1}y_{2}m_{<i})$ $\displaystyle=p(xym)\cdot q(x_{1}y_{2}m)$
$\displaystyle=p(xym)\cdot q(w).$ (12)

The pairs $p_{1},p_{2},q_{1},q_{2}$ have been engineered so that the various
terms in the marginal cost add up nicely across the pairs. We have:

$\displaystyle\frac{q_{1}(x_{1}y_{1}m^{(1)})}{p_{1}(x_{1}y_{1}m^{(1)})}\cdot\frac{q_{2}(x_{2}y_{2}m^{(2)})}{p_{2}(x_{2}y_{2}m^{(2)})}$
$\displaystyle=\frac{q(xym)}{p(xym)},$ (13)
$\displaystyle\frac{q_{1}(x_{1}|y_{1}m^{(1)})}{p_{1}(x_{1}|y_{1})}\cdot\frac{q_{2}(x_{2}|y_{2}m^{(2)})}{p_{2}(x_{2}|y_{2})}$
$\displaystyle=\frac{q(x|ym)}{p(x|y)},$ (14)
$\displaystyle\frac{q_{1}(y_{1}|x_{1}m^{(1)})}{p_{1}(y_{1}|x_{1})}\cdot\frac{q_{2}(y_{2}|x_{2}m^{(2)})}{p_{2}(y_{2}|x_{2})}$
$\displaystyle=\frac{q(y|xm)}{p(y|x)},$ (15)
$\displaystyle\left|\mathop{\mathbb{E}\/}_{q_{1}(x_{1}y_{1}|w)}\left[(-1)^{f}\right]\right|\cdot\left|\mathop{\mathbb{E}\/}_{q_{2}(x_{2}y_{2}|w)}\left[(-1)^{g}\right]\right|$
$\displaystyle=\left|\mathop{\mathbb{E}\/}_{q(xy|w)}\left[(-1)^{f\oplus
g}\right]\right|.$ (16)

To prove Equation 13, use Equations 12 and 20 to obtain

$\displaystyle\frac{q_{1}(x_{1}y_{1}m^{(1)})}{p_{1}(x_{1}y_{1}m^{(1)})}\cdot\frac{q_{2}(x_{2}y_{2}m^{(2)})}{p_{2}(x_{2}y_{2}m^{(2)})}$
$\displaystyle=\frac{q(xym)}{p(xym)}\cdot\frac{q(w)}{q(w)}=\frac{q(xym)}{p(xym)}.$

Equations 14 and 15 follow directly from Proposition 20. We use the fact that
$q(xy|w)=q(x_{2}|w)\cdot q(y_{1}|w)$ from Proposition 20 to prove Equation 16:

$\displaystyle\left|\mathop{\mathbb{E}\/}_{q_{1}(x_{1}y_{1}|w)}\left[(-1)^{f}\right]\right|\cdot\left|\mathop{\mathbb{E}\/}_{q_{2}(x_{2}y_{2}|w)}\left[(-1)^{g}\right]\right|=\left|\mathop{\mathbb{E}\/}_{q(y_{1}|w)}\left[(-1)^{f}\right]\cdot\mathop{\mathbb{E}\/}_{q(x_{2}|w)}\left[(-1)^{g}\right]\right|=\left|\mathop{\mathbb{E}\/}_{q(xy|w)}\left[(-1)^{f\oplus
g}\right]\right|.$

These identities suggest that the costs in the first and second coordinates
should sum to $\mathsf{M}(q,p,f\oplus g)$. The main challenge in applying this
intuition is that the advantage terms in Equation 16 are not the ones needed
for $\mathsf{M}(q_{1},p_{1},f)$ and $\mathsf{M}(q_{2},p_{2},g)$. To resolve
this, we need to remove some problematic points in the support of $q$. We need
to do this while retaining the rectangular structure of $q_{1},q_{2}$ and
preserving the sub-additivity of the other terms in the marginal cost.

Let $G$ be a subset of triples $xym$ such that the indicator function
$1_{G}(xyw)$ depends only on $w$, and for each fixed $m$, the set $G$
maximizes

$\displaystyle
q(G|m)^{\delta}\cdot\Big{|}\mathop{\mathbb{E}\/}_{q(xy|mG)}\Big{[}(-1)^{f\oplus
g}\Big{]}\Big{|},$ (17)

among all such sets. In Lemma 31, we prove that for all $w$ in the support of
$G$:

$\displaystyle\left|\mathop{\mathbb{E}\/}_{q(xy|w)}\left[(-1)^{f\oplus
g}\right]\right|\geq(1-\delta)\cdot
q(G|m)^{-\delta}\cdot\left|\mathop{\mathbb{E}\/}_{q(xy|m)}\left[(-1)^{f\oplus
g}\right]\right|.$ (18)

This gives us an effective way to split the costs for $q,p$. Using Equations
13, 14, 15 and 16, we obtain that for all $xym$ in the support of $G$,

$\displaystyle\frac{q_{1}(x_{1}|y_{1}m^{(1)})}{p_{1}(x_{1}|y_{1})}\frac{q_{1}(y_{1}|x_{1}m^{(1)})}{p_{1}(y_{1}|x_{1})}$
$\displaystyle\cdot$
$\displaystyle\bigg{(}\frac{q_{1}(x_{1}y_{1}m^{(1)})}{p_{1}(x_{1}y_{1}m^{(1)})}\bigg{)}^{I}$
$\displaystyle\cdot$
$\displaystyle\left|\mathop{\mathbb{E}\/}_{q_{1}(x_{1}y_{1}|w)}\left[(-1)^{f}\right]\right|^{-12I/\delta}$
$\displaystyle\times$
$\displaystyle\frac{q_{2}(x_{2}|y_{2}m^{(2)})}{p_{2}(x_{2}|y_{2})}\frac{q_{2}(y_{2}|x_{2}m^{(2)})}{p_{2}(y_{2}|x_{2})}$
$\displaystyle\cdot$
$\displaystyle\bigg{(}\frac{q_{2}(x_{2}y_{2}m^{(2)})}{p_{2}(x_{2}y_{2}m^{(2)})}\bigg{)}^{I}$
$\displaystyle\cdot$
$\displaystyle\left|\mathop{\mathbb{E}\/}_{q_{2}(x_{2}y_{2}|w)}\left[(-1)^{g}\right]\right|^{-12I/\delta}$
$\displaystyle=$ $\displaystyle\frac{q(x|ym)}{p(x|y)}\frac{q(y|xm)}{p(y|x)}$
$\displaystyle\cdot$ $\displaystyle\bigg{(}\frac{q(xym)}{p(xym)}\bigg{)}^{I}$
$\displaystyle\cdot$
$\displaystyle\left|\mathop{\mathbb{E}\/}_{q(xy|w)}\left[(-1)^{f\oplus
g}\right]\right|^{-12I/\delta}$ $\displaystyle\leq$
$\displaystyle\frac{q(x|ym)}{p(x|y)}\frac{q(y|xm)}{p(y|x)}$
$\displaystyle\cdot$ $\displaystyle\bigg{(}\frac{q(xym)}{p(xym)}\bigg{)}^{I}$
$\displaystyle\cdot$
$\displaystyle\left|\mathop{\mathbb{E}\/}_{q(xy|m)}\left[(-1)^{f\oplus
g}\right]\right|^{-12I/\delta}\cdot O(q(G|m))^{12I}$ $\displaystyle\leq$
$\displaystyle 2^{\mathsf{M}(q,p,f\oplus g)}$ $\displaystyle\cdot$
$\displaystyle O(q(G|m))^{12I}$

In this product, the quantity in the first line does not depend on the choice
of $x_{2}$, and the quantity in the second line does not depend on $y_{1}$.
Thus, for every fixed value of $w$, we obtain:

$\displaystyle\left|\mathop{\mathbb{E}\/}_{q_{1}(x_{1}y_{1}|w)}\left[(-1)^{f}\right]\right|^{-12I/\delta}\cdot\sup_{y_{1}}\bigg{(}\frac{q_{1}(x_{1}y_{1}m^{(1)})}{p_{1}(x_{1}y_{1}m^{(1)})}\bigg{)}^{I}\cdot\frac{q_{1}(x_{1}|y_{1}m^{(1)})}{p_{1}(x_{1}|y_{1})}\frac{q_{1}(y_{1}|x_{1}m^{(1)})}{p_{1}(y_{1}|x_{1})}$
$\displaystyle\times$
$\displaystyle\left|\mathop{\mathbb{E}\/}_{q_{2}(x_{2}y_{2}|w)}\left[(-1)^{g}\right]\right|^{-12I/\delta}\cdot\sup_{x_{2}}\bigg{(}\frac{q_{2}(x_{2}y_{2}m^{(2)})}{p_{2}(x_{2}y_{2}m^{(2)})}\bigg{)}^{I}\cdot\frac{q_{2}(x_{2}|y_{2}m^{(2)})}{p_{2}(x_{2}|y_{2})}\frac{q_{2}(y_{2}|x_{2}m^{(2)})}{p_{2}(y_{2}|x_{2})}$
$\displaystyle\leq$ $\displaystyle 2^{\mathsf{M}(q,p,f\oplus g)}\cdot
O(q(G|m))^{12I}.$ (19)

Let $L\subseteq G$ be a subset whose indicator function $1_{L}(xym)$ depends
only on $w$, such that $1_{L}(w)=1$ if and only if

$\displaystyle\left(\left|\mathop{\mathbb{E}\/}_{q_{1}(x_{1}y_{1}|w)}\left[(-1)^{f}\right]\right|^{-12I/\delta}\cdot\sup_{y_{1}}\bigg{(}\frac{q_{1}(x_{1}y_{1}m^{(1)})}{p_{1}(x_{1}y_{1}m^{(1)})}\bigg{)}^{I}\cdot\frac{q_{1}(x_{1}|y_{1}m^{(1)})}{p_{1}(x_{1}|y_{1})}\frac{q_{1}(y_{1}|x_{1}m^{(1)})}{p_{1}(y_{1}|x_{1})}\right)^{1/\gamma}$
$\displaystyle\leq\left(\left|\mathop{\mathbb{E}\/}_{q_{2}(x_{2}y_{2}|w)}\left[(-1)^{g}\right]\right|^{-12I/\delta}\cdot\sup_{x_{2}}\bigg{(}\frac{q_{2}(x_{2}y_{2}m^{(2)})}{p_{2}(x_{2}y_{2}m^{(2)})}\bigg{)}^{I}\cdot\frac{q_{2}(x_{2}|y_{2}m^{(2)})}{p_{2}(x_{2}|y_{2})}\frac{q_{2}(y_{2}|x_{2}m^{(2)})}{p_{2}(y_{2}|x_{2})}\right)^{1/(1-\gamma)}.$

Let $U$ denote the set whose indicator function depends only on $m$, such that
$1_{U}(m)=1$ if and only if $q(L|mG)\geq 1/2$. If $q(U)\geq 1/2$, we carry out
the reduction in the first coordinate. Otherwise, we carry out the reduction
in the second coordinate, using the complements of $U,L$ instead. Without loss
of generality, we assume that $q(U)\geq 1/2$. By the definition of $U,L$, and
by Equation 19, for all $w$ in the support of $U\cap L$ we have

$\displaystyle\left|\mathop{\mathbb{E}\/}_{q_{1}(x_{1}y_{1}|w)}\left[(-1)^{f}\right]\right|^{-12I/\delta}\cdot\bigg{(}\sup_{y_{1}}\frac{q_{1}(x_{1}y_{1}m^{(1)})}{p_{1}(x_{1}y_{1}m^{(1)})}\bigg{)}^{I}\cdot\frac{q_{1}(x_{1}|y_{1}m^{(1)})}{p_{1}(x_{1}|y_{1})}\frac{q_{1}(y_{1}|x_{1}m^{(1)})}{p_{1}(y_{1}|x_{1})}$
$\displaystyle\leq 2^{\gamma\cdot\mathsf{M}(q,p,f\oplus g)}\cdot
O(q(G|m))^{12\gamma\cdot I}.$ (20)

Our next barrier is that in $\mathsf{M}(q_{1},p_{1},f)$ the advantage term is
not exactly the same as what we have bounded in the above expressions; it
might well be that for most $w$ consistent with $m^{(1)}$

$\displaystyle\Big{|}\mathop{\mathbb{E}\/}_{q_{1}(x_{1}y_{1}|m^{(1)})}\Big{[}(-1)^{f}\Big{]}\Big{|}\ll\Big{|}\mathop{\mathbb{E}\/}_{q_{1}(x_{1}y_{1}|w)}\Big{[}(-1)^{f}\Big{]}\Big{|}.$
(21)

To resolve this issue, we condition on a dense subset $B$ of the $w$’s such
that given any two $w,w^{\prime}\in B$ that are consistent with the same $m$,

$\Big{|}\mathop{\mathbb{E}\/}_{q_{1}(x_{1}y_{1}|w)}\Big{[}(-1)^{f}\Big{]}\Big{|}\geq\frac{1}{2}\cdot\Big{|}\mathop{\mathbb{E}\/}_{q_{1}(x_{1}y_{1}|w^{\prime})}\Big{[}(-1)^{f}\Big{]}\Big{|}.$

This will ensure that Equation 21 does not happen. To find this subset $B$, we
first prune away some problematic points to ensure all advantage terms in
Equation 20 are reasonably large. This is accomplished by 28 below.

######  Claim 28.

There are subsets $U^{\prime}\subseteq U,L^{\prime}\subseteq L$ such that
$1_{U^{\prime}}(xym)$ only depends on $m$, $1_{L^{\prime}}(xym)$ only depends
on $w$, $q(U^{\prime})\geq 1/4$, and for all $mw$ in the support of
$U^{\prime}\cap L^{\prime}$, we have $q(L^{\prime}|mG)\geq 1/4$ and

$\left|\mathop{\mathbb{E}\/}_{q_{1}(x_{1}y_{1}|w)}\left[(-1)^{f}\right]\right|^{-1}\leq\alpha,$

for some $\alpha\leq 2^{O(\mathsf{M}(q,p,f\oplus g)/I)}\cdot O(1).$

We defer the proof of 28 to the end of this section. Assuming the claim, we
can now bucket the $w$ according to their advantage. For each fixing of
$m^{(1)}$, partition the space of $w$ consistent with $m^{(1)}$ into disjoint
buckets according to the sign of
$\mathop{\mathbb{E}\/}_{q_{1}(x_{1}y_{1}|w)}\left[(-1)^{f}\right]$, and the
value of

$\left\lceil\log\left|\mathop{\mathbb{E}\/}_{q_{1}(x_{1}y_{1}|w)}\left[(-1)^{f}\right]\right|\right\rceil.$

There can be at most $O(\log\alpha)$ such buckets, and so by picking the
heaviest bucket for each $m^{(1)}$, we obtain a set $B\subseteq L^{\prime}$
whose indicator function $1_{B}(x_{1}y_{1}m^{(1)})$ is determined by $w$, such
that for every $m^{(1)}$,

$\displaystyle q_{1}(B|m^{(1)}L^{\prime})\geq\frac{1}{O(\log\alpha)},$ (22)

and moreover, for every $wm^{(1)}$ in the support of $B$,

$\displaystyle\left|\mathop{\mathbb{E}\/}_{q_{1}(x_{1}y_{1}|m^{(1)}B)}\Big{[}(-1)^{f}\Big{]}\right|\geq\frac{1}{2}\cdot\left|\mathop{\mathbb{E}\/}_{q_{1}(x_{1}y_{1}|w)}\Big{[}(-1)^{f}\Big{]}\right|.$
(23)

Let $R\subseteq B\subseteq L^{\prime}$ be the rectangular set in
$x_{1}y_{1}m^{(1)}$ such that for every $m^{(1)}$, $R$ maximizes

$\displaystyle
q_{1}(R|m^{(1)}B)^{\delta}\cdot\Big{|}\mathop{\mathbb{E}\/}_{q_{1}(x_{1}y_{1}|m^{(1)}R)}\Big{[}(-1)^{f}\Big{]}\Big{|}.$
(24)

Define the rectangular distribution

$\displaystyle r(x_{1}y_{1}m^{(1)})$
$\displaystyle=q_{1}(x_{1}y_{1}m^{(1)})\cdot\frac{1_{U^{\prime}}(m)\cdot
1_{R}(x_{1}y_{1}m^{(1)})}{q_{1}(U^{\prime})\cdot q_{1}(L^{\prime}|m)\cdot
q_{1}(R|m^{(1)}L^{\prime})}$
$\displaystyle=\frac{q_{1}(m)1_{U^{\prime}}(m)}{q_{1}(U^{\prime})}\cdot\frac{q_{1}(y_{2}|m)q_{1}(L^{\prime}|m^{(1)})}{q_{1}(L^{\prime}|m)}\cdot\frac{q_{1}(x_{1}y_{1}|m^{(1)})\cdot
1_{R}(x_{1}y_{1}m^{(1)})}{q_{1}(L^{\prime}|m^{(1)})\cdot
q_{1}(R|m^{(1)}L^{\prime})}$ $\displaystyle=q_{1}(m|U^{\prime})\cdot
q_{1}(y_{2}|mL^{\prime})\cdot\frac{q_{1}(x_{1}y_{1}|m^{(1)})\cdot
1_{R}(x_{1}y_{1}m^{(1)})}{q_{1}(R|m^{(1)})}$
$\displaystyle=q_{1}(m|U^{\prime})\cdot q_{1}(y_{2}|mL^{\prime})\cdot
q_{1}(x_{1}y_{1}|m^{(1)}R).$ (25)

Because $r$ is defined as the product of a rectangular distribution with a
function that is also rectangular, $r$ is rectangular. From the last line in
Equation 25, it is clear that $r$ is a distribution. We have the following
bound:

$\displaystyle\frac{r(x_{1}y_{1}m^{(1)})}{q_{1}(x_{1}y_{1}m^{(1)})}$
$\displaystyle=\frac{1_{U^{\prime}}(m)\cdot
1_{R}(x_{1}y_{1}m^{(1)})}{q_{1}(U^{\prime})\cdot q_{1}(L^{\prime}|m)\cdot
q_{1}(R|m^{(1)}L^{\prime})}$
$\displaystyle\leq\frac{O(1)}{q_{1}(L^{\prime}|mG)\cdot q_{1}(G|m)\cdot
q_{1}(R|m^{(1)}B)\cdot q_{1}(B|m^{(1)}L^{\prime})}$
$\displaystyle\leq\frac{O(\log\alpha)}{q_{1}(G|m)\cdot q_{1}(R|m^{(1)}B)},$
(26)

where here we used 28 and Equation 22. Apply Lemma 29 with $a=r$, $b=q_{1}$
and $\kappa=1/6$ to obtain a rectangular set $T$ with $r(T)\geq 1/2$ such that

$\displaystyle\frac{r(x_{1}m^{(1)}|T)}{q_{1}(x_{1}m^{(1)})},\frac{r(y_{1}m^{(1)}|T)}{q_{1}(y_{1}m^{(1)})},\frac{r(m^{(1)}|T)}{r(m^{(1)})}\geq\frac{1}{6}.$
(27)

Finally, we define $r_{1}(x_{1}y_{1}m^{(1)})=r(x_{1}y_{1}m^{(1)}|T)$. Because
$r$ is a rectangular distribution and $T$ is a rectangular set, $r_{1}$ is a
rectangular distribution. It only remains to bound
$\mathsf{M}(r_{1},p_{1},f)$. For all $x_{1}y_{1}m^{(1)}$ in the support of
$r_{1}$, we have

$\displaystyle\frac{r_{1}(x_{1}y_{1}m^{(1)})}{p_{1}(x_{1}y_{1}m^{(1)})}$
$\displaystyle=\frac{q_{1}(x_{1}y_{1}m^{(1)})}{p_{1}(x_{1}y_{1}m^{(1)})}\cdot\frac{r(x_{1}y_{1}m^{(1)})}{q_{1}(x_{1}y_{1}m^{(1)})}\cdot\frac{1}{r(T)}$
$\displaystyle\leq\frac{q_{1}(x_{1}y_{1}m^{(1)})}{p(x_{1}y_{1}m^{(1)})}\cdot\frac{O(\log\alpha)}{q_{1}(G|m)\cdot
q_{1}(R|m^{(1)}B)},$ (28)

using Section 4 and the fact that $r(T)\geq 1/2$. For the next term,

$\displaystyle\frac{r_{1}(x_{1}|y_{1}m^{(1)})}{p_{1}(x_{1}|y_{1}m^{(1)})}$
$\displaystyle=\frac{q_{1}(x_{1}|y_{1}m^{(1)})}{p_{1}(x_{1}|y_{1}m^{(1)})}\cdot\frac{r_{1}(x_{1}|y_{1}m^{(1)})}{q_{1}(x_{1}|y_{1}m^{(1)})}$
$\displaystyle=\frac{q_{1}(x_{1}|y_{1}m^{(1)})}{p_{1}(x_{1}|y_{1}m^{(1)})}\cdot\frac{r(x_{1}y_{1}m^{(1)})}{q_{1}(x_{1}y_{1}m^{(1)})}\cdot\frac{1}{r(T)}\cdot\frac{q_{1}(y_{1}m^{(1)})}{r(y_{1}m^{(1)}|T)}$
$\displaystyle\leq\frac{q_{1}(x_{1}|y_{1}m^{(1)})}{p_{1}(x_{1}|y_{1}m^{(1)})}\cdot\frac{O(\log\alpha)}{q_{1}(G|m)\cdot
q_{1}(R|m^{(1)}B)},$ (29)

using Sections 4 and 27, and the fact that $r(T)\geq 1/2$. The symmetric
argument gives:

$\displaystyle\frac{r_{1}(y_{1}|x_{1}m^{(1)})}{p_{1}(y_{1}|x_{1}m^{(1)})}$
$\displaystyle\leq\frac{q_{1}(y_{1}|x_{1}m^{(1)})}{p_{1}(y_{1}|x_{1}m^{(1)})}\cdot\frac{O(\log\alpha)}{q_{1}(G|m)\cdot
q_{1}(R|m^{(1)}B)}.$ (30)

To bound the advantage, first note that

$\displaystyle q_{1}(T|m^{(1)}R)$ $\displaystyle=\frac{q_{1}(T|R)\cdot
q_{1}(m^{(1)}|T)}{q_{1}(m^{(1)}|R)}=\frac{r(T)\cdot
r(m^{(1)}|T)}{r(m^{(1)})}\geq\frac{1}{12},$ (31)

by Equation 27. For each $m^{(1)}$, we apply Lemma 30 with
$v(x_{1}y_{1}m^{(1)})=q_{1}(x_{1}y_{1}m^{(1)}|m^{(1)}B)$, $R$ and $Z=T$. Note
here that $v(m^{(1)})=1$. We obtain the bound:

$\displaystyle\Big{|}\mathop{\mathbb{E}\/}_{r_{1}(x_{1}y_{1}|m^{(1)})}\big{[}(-1)^{f}\big{]}\Big{|}$
$\displaystyle=\Big{|}\mathop{\mathbb{E}\/}_{q_{1}(x_{1}y_{1}|m^{(1)}T)}\big{[}(-1)^{f}\big{]}\Big{|}$
$\displaystyle\geq\frac{1-\delta^{2}-\delta/q_{1}(T|m^{(1)}R)}{q_{1}(R|m^{(1)}B)^{\delta}}\cdot\Big{|}\mathop{\mathbb{E}\/}_{q_{1}(x_{1}y_{1}|m^{(1)}B)}\Big{[}(-1)^{f}\Big{]}\Big{|}$
$\displaystyle\geq\frac{\Omega(1)}{q_{1}(R|m^{(1)}B)^{\delta}}\cdot\Big{|}\mathop{\mathbb{E}\/}_{q_{1}(x_{1}y_{1}|m^{(1)}B)}\Big{[}(-1)^{f}\Big{]}\Big{|},$
(32)

by the choice of $\delta$ and Equation 31.

Now, we are ready to put all these bounds together to complete the proof of
the theorem. By Equation 23, Section 4, Section 4, Equation 30, Section 4, we
get that for every $x_{1}y_{1}m^{(1)}$ in the support of $r_{1}$,

$\displaystyle\frac{r_{1}(x_{1}|y_{1}m^{(1)})}{p_{1}(x_{1}|y_{1})}\cdot\frac{r_{1}(y_{1}|x_{1}m^{(1)})}{p(y_{1}|x_{1})}\cdot\bigg{(}\frac{r_{1}(x_{1}y_{1}m^{(1)})}{p_{1}(x_{1}y_{1}m^{(1)})}\bigg{)}^{I}\cdot\Big{|}\mathop{\mathbb{E}\/}_{r_{1}(x_{1}y_{1}|m^{(1)})}\big{[}(-1)^{f}\big{]}\Big{|}^{-12I/\delta}$
$\displaystyle\leq\frac{q_{1}(x_{1}|y_{1}m^{(1)})}{p_{1}(x_{1}|y_{1})}\cdot\frac{q_{1}(y_{1}|x_{1}m^{(1)})}{p(y_{1}|x_{1})}\cdot\bigg{(}\frac{q_{1}(x_{1}y_{1}m^{(1)})}{p_{1}(x_{1}y_{1}m^{(1)})}\bigg{)}^{I}\cdot\Big{|}\mathop{\mathbb{E}\/}_{q_{1}(x_{1}y_{1}|w)}\big{[}(-1)^{f}\big{]}\Big{|}^{-12I/\delta}$
$\displaystyle\qquad\times\frac{O(\log(\alpha))^{I+2}}{q_{1}(G|m)^{I+2}\cdot
q_{1}(R|m^{(1)}B)^{I+2-12I}}$ $\displaystyle\leq
2^{\gamma\cdot\mathsf{M}(q,p,f\oplus g)}\cdot O(\log(\alpha))^{3I}\cdot
q_{1}(G|m)^{12\gamma\cdot I-I-2}\cdot 2^{O(I)}\cdot q_{1}(R|m^{(1)}B)^{11I-2}$
$\displaystyle\leq 2^{\gamma\cdot\mathsf{M}(q,p,f\oplus g)}\cdot
O(\log(\alpha))^{3I}\cdot q_{1}(G|m)^{3I-2}\cdot 2^{O(I)}$ $\displaystyle\leq
2^{\gamma\cdot\mathsf{M}(q,p,f\oplus g)}\cdot
O\left(\frac{\mathsf{M}(q,p,f\oplus g)}{I}\right)^{3I},$

where in the last three inequalities we used Equation 20, the fact that $I\geq
1$ and 28. This implies that

$\mathsf{M}(r_{1},p_{1},f)\leq\gamma\cdot\mathsf{M}(q,p,f\oplus
g)+3I\log\frac{\mathsf{M}(q,p,f\oplus g)}{I}+O(I),$

completing the proof of the theorem.

Proof of 28: We have

$\mathop{\mathbb{E}\/}_{q_{1}(m)}\left[\frac{p_{1}(m)}{q_{1}(m)}\right]\leq
1,$

and so by Markov’s inequality, the total mass of $m\in\mathsf{supp}(q)$ for
which

$\displaystyle\frac{q_{1}(m)}{p_{1}(m)}\leq 1/4$ (33)

is at most $1/4$. We delete all such $m$ from the support of $U$. We are left
with a set $U^{\prime}$ with

$\displaystyle q(U^{\prime})\geq 1/2-1/4=1/4.$ (34)

Next, we delete $w$ from $L$ if either

$\displaystyle\frac{q_{1}(w|m)}{p_{1}(w|m)}<\frac{q_{1}(G|m)}{8},$ (35)

or

$\displaystyle\mathop{\mathbb{E}\/}_{q_{1}(y_{1}|w)}\left[\log\frac{q_{1}(x_{1}|y_{1}m^{(1)})}{p_{1}(x_{1}|y_{1})}\right]<\log\frac{q_{1}(G|m)}{8}.$
(36)

We claim that for all $m$ in the support of $U^{\prime}$,
$q(L^{\prime}|mG)\geq 1/4$. To see this, observe that

$\displaystyle
q_{1}(G|m)\cdot\mathop{\mathbb{E}\/}_{q_{1}(w|mG)}\left[\frac{p_{1}(w|m)}{q_{1}(w|m)}\right]\leq\mathop{\mathbb{E}\/}_{q_{1}(w|m)}\left[\frac{p_{1}(w|m)}{q_{1}(w|m)}\right]\leq
1,$

so Markov’s inequality implies that for each $m$ the total mass of $w$ for
which Equation 35 is violated is at most $1/8$. By the concavity of the $\log$
function, the $w$ deleted because of Equation 36 satisfy

$\displaystyle\log\mathop{\mathbb{E}\/}_{q_{1}(y_{1}|w)}\left[\frac{p_{1}(x_{1}|y_{1}m^{(1)})}{q_{1}(x_{1}|y_{1})}\right]\geq\mathop{\mathbb{E}\/}_{q_{1}(y_{1}|w)}\left[\log\frac{p_{1}(x_{1}|y_{1}m^{(1)})}{q_{1}(x_{1}|y_{1})}\right]>\log\frac{8}{q_{1}(G|m)}.$

On the other hand, because $w$ determines $1_{G}$,

$\displaystyle
q_{1}(G|m)\cdot\mathop{\mathbb{E}\/}_{q_{1}(w|mG)}\left[\mathop{\mathbb{E}\/}_{q_{1}(y_{1}|w)}\left[\frac{p_{1}(x_{1}|y_{1})}{q_{1}(x_{1}|y_{1}m^{(1)})}\right]\right]$
$\displaystyle\leq\mathop{\mathbb{E}\/}_{q_{1}(y_{1}w|m)}\left[\frac{p_{1}(x_{1}|y_{1})}{q_{1}(x_{1}|y_{1}m^{(1)})}\right]$
$\displaystyle=\mathop{\mathbb{E}\/}_{q_{1}(y|m)}\left[\mathop{\mathbb{E}\/}_{q_{1}(x_{1}|ym)}\left[\frac{p_{1}(x_{1}|y_{1})}{q_{1}(x_{1}|y_{1}m^{(1)})}\right]\right]\leq
1,$

so once again, Markov’s inequality implies that the total mass of $w$ deleted
using this rule is at most $1/8$. This gives

$\displaystyle q(L^{\prime}|mG)\geq 1/2-1/8-1/8=1/4.$ (37)

The result of these pruning steps is that we are left with large sets
$U^{\prime},L^{\prime}\subseteq G$ such that for all $m,w$ that are consistent
with $U^{\prime},L^{\prime}$, we have

$\displaystyle\sup_{y_{1}}\bigg{(}\frac{q_{1}(x_{1}y_{1}m^{(1)})}{p_{1}(x_{1}y_{1}m^{(1)})}\bigg{)}^{I}\cdot\frac{q_{1}(x_{1}|y_{1}m^{(1)})}{p_{1}(x_{1}|y_{1})}\cdot\frac{q_{1}(y_{1}|x_{1}m^{(1)})}{p_{1}(y_{1}|x_{1})}$
$\displaystyle=\bigg{(}\frac{q_{1}(m)\cdot q_{1}(w|m)}{p_{1}(m)\cdot
p_{1}(w|m)}\bigg{)}^{I}\cdot\sup_{y_{1}}\bigg{(}\frac{q_{1}(y_{1}|w)}{p_{1}(y_{1}|w)}\bigg{)}^{I}\cdot\frac{q_{1}(x_{1}|y_{1}m^{(1)})}{p_{1}(x_{1}|y_{1})}\cdot\frac{q_{1}(y_{1}|x_{1}m^{(1)})}{p_{1}(y_{1}|x_{1})}$
$\displaystyle=\bigg{(}\frac{q_{1}(m)\cdot q_{1}(w|m)}{p_{1}(m)\cdot
p_{1}(w|m)}\bigg{)}^{I}\cdot\exp\Bigg{(}\sup_{y_{1}}\log\bigg{(}\bigg{(}\frac{q_{1}(y_{1}|w)}{p_{1}(y_{1}|w)}\bigg{)}^{I}\cdot\frac{q_{1}(x_{1}|y_{1}m^{(1)})}{p_{1}(x_{1}|y_{1})}\cdot\frac{q_{1}(y_{1}|x_{1}m^{(1)})}{p_{1}(y_{1}|x_{1})}\bigg{)}\Bigg{)}$
$\displaystyle\geq\bigg{(}\frac{q_{1}(m)\cdot q_{1}(w|m)}{p_{1}(m)\cdot
p_{1}(w|m)}\bigg{)}^{I}\cdot\exp\Bigg{(}\mathop{\mathbb{E}\/}_{q(y_{1}|w)}\log\bigg{(}\bigg{(}\frac{q_{1}(y_{1}|w)}{p_{1}(y_{1}|w)}\bigg{)}^{I}\cdot\frac{q_{1}(x_{1}|y_{1}m^{(1)})}{p_{1}(x_{1}|y_{1})}\cdot\frac{q_{1}(y_{1}|x_{1}m^{(1)})}{p_{1}(y_{1}|x_{1})}\bigg{)}\Bigg{)},$

where here $\exp(z)$ denotes $2^{z}$. Now we use the fact that all the $m,w$
violating Equations 33, 35 and 36 have been deleted and use Equation 6 to
bound

$\displaystyle\geq\bigg{(}\frac{1}{4}\cdot\frac{q_{1}(G|m)}{8}\bigg{)}^{I}$
$\displaystyle\qquad\cdot\exp\Bigg{(}\mathop{\mathbb{E}\/}_{q_{1}(y_{1}|w)}\left[I\log\frac{q_{1}(y_{1}|w)}{p_{1}(y_{1}|w)}+\log\left(\frac{q_{1}(x_{1}|y_{1}m^{(1)})}{p_{1}(x_{1}|y_{1})}\right)+\log\left(\frac{q_{1}(y_{1}|x_{1}m^{(1)})}{p_{1}(y_{1}|x_{1})}\right)\right]\Bigg{)}$
$\displaystyle\geq\bigg{(}\frac{1}{4}\cdot\frac{q_{1}(G|m)}{8}\bigg{)}^{I}\cdot\exp\Bigg{(}\mathop{\mathbb{E}\/}_{q_{1}(y_{1}|w)}\left[\log\left(\frac{q_{1}(x_{1}|y_{1}m^{(1)})}{p_{1}(x_{1}|y_{1})}\right)\right]\Bigg{)}$
$\displaystyle\geq\Omega(q_{1}(G|m))^{1+I}.$

Combining this bound with Equation 20, we get that for all $w$ consistent with
$U^{\prime},L^{\prime}$,

$\displaystyle\left|\mathop{\mathbb{E}\/}_{q_{1}(x_{1}y_{1}|w)}\left[(-1)^{f}\right]\right|^{-12I/\delta}\leq
2^{\gamma\cdot\mathsf{M}(q,p,f\oplus g)}\cdot O(q(G|m))^{12\cdot\gamma
I-I-1},$

so since $I\geq 1$ and $\gamma\geq 1/3$, this implies

$\displaystyle\left|\mathop{\mathbb{E}\/}_{q_{1}(x_{1}y_{1}|w)}\left[(-1)^{f}\right]\right|^{-1}\leq
O(2^{\mathsf{M}(q,p,f\oplus g)\cdot(\delta\gamma/12I)})=\alpha,$ (38)

as required.

##  5 Trimming and advantage preserving sets

In this section, we gather a few lemmas about trimming rectangular sets to
pass to subrectangles with nice features. The idea of trimming comes from the
work of Yu [Yu22].

######  Lemma 29.

For every $1>\kappa>0$, if $a(xym),b(xym)$ are two distributions, there exists
a rectangular set $T$ such that $a(T)\geq 1-3\kappa$ and for all $xym\in T$,
we have

$\frac{a(xm|T)}{b(xm)},\frac{a(ym|T)}{b(ym)},\frac{a(m|T)}{a(m)}\geq\kappa.$

###### Proof.

The set $T$ is constructed by an iterative process. Initially, $T$ is the set
of all triples $xym$. In each iteration, if there is $xm$ such that

$\displaystyle\frac{a(xm|T)}{b(xm)}<\kappa,$ (39)

then delete $xm$ from the support of $T$, if there is $ym$ such that

$\frac{a(ym|T)}{b(ym)}<\kappa,$

then delete $ym$ from the support of $T$, and if there is $m$ such that

$\frac{a(m|T)}{a(m)}<\kappa,$

then delete $m$ from the support of $T$. The process halts when there are no
more elements to delete. Because the distributions we are working with have
finite support, this process must eventually terminate. Initially, $T$ is
rectangular, and each deletion step leaves us with another rectangular set
$T$, so the final $T$ is also rectangular.

Let us bound $a(T)$. For each pair $xm$ that was deleted from the support of
$T$ because of Equation 39, let $T_{xm}$ denote the set $T$ right before $xm$
was deleted. If $xm$ was not deleted, let $T_{xm}$ denote the empty set.

The total mass deleted using Equation 39 is exactly

$\displaystyle\sum_{xm}a(xmT_{xm})=\sum_{xm}a(T_{xm})\cdot
a(xm|T_{xm})<\sum_{xm}\kappa\cdot b(xm)=\kappa.$

Similarly, the total mass deleted using each of the other rules is also at
most $\kappa$. By the union bound, this proves that $a(T)\geq 1-3\kappa$ when
the process terminates. ∎

Next, we gather a couple of nice lemmas about finding subrectangles with nice
properties.

######  Lemma 30.

For any distribution $v(xym)$ and a Boolean function $h(xy)$, suppose $R$ is a
rectangular set maximizing

$\displaystyle
v(R)^{\delta}\cdot\mathop{\mathbb{E}\/}_{v(m|R)}\Big{|}\mathop{\mathbb{E}\/}_{v(xy|mR)}\big{[}(-1)^{h}\big{]}\Big{|}.$
(40)

Then, for any rectangular $Z\subseteq R$, we have

$\mathop{\mathbb{E}\/}_{v(m|Z)}\Big{|}\mathop{\mathbb{E}\/}_{v(xy|mZ)}\big{[}(-1)^{h}\big{]}\Big{|}\geq\frac{1-\delta^{2}-\delta/v(Z|R)}{v(R)^{\delta}}\cdot\mathop{\mathbb{E}\/}_{v(m)}\Big{|}\mathop{\mathbb{E}\/}_{v(xy|m)}\big{[}(-1)^{h}\big{]}\Big{|}.$

###### Proof.

Since $R$ and $Z$ are rectangular, we have

$1_{R}(xym)=1_{A}(xm)\cdot 1_{B}(ym),$

and

$1_{Z}(xym)=1_{A^{\prime}}(xm)\cdot 1_{B^{\prime}}(ym),$

for appropriate sets $A,A^{\prime}$ and $B,B^{\prime}$. $R$ can be partitioned
into three rectangular sets, $Z_{0}=Z,Z_{1}$ and $Z_{2}$, where

$\displaystyle 1_{Z_{1}}(xym)=1_{A\setminus A^{\prime}}(xm)\cdot 1_{B}(ym)$

and

$\displaystyle 1_{Z_{2}}(xym)=1_{A^{\prime}}(xm)\cdot 1_{B\setminus
B^{\prime}}(ym).$

By the triangle inequality, we get

$\displaystyle\mathop{\mathbb{E}\/}_{v(m|R)}\Big{|}\mathop{\mathbb{E}\/}_{v(xy|Rm)}\Big{[}(-1)^{h}\Big{]}\Big{|}\leq\sum_{i=0}^{2}v(Z_{i}|R)\cdot\mathop{\mathbb{E}\/}_{v(m|Z_{i})}\Big{|}\mathop{\mathbb{E}\/}_{v(xy|mZ_{i})}\Big{[}(-1)^{h}\Big{]}\Big{|}$
(41)

Let us bound the contribution of $Z_{1},Z_{2}$:

$\displaystyle\sum_{i=1}^{2}v(Z_{i}|R)\cdot\mathop{\mathbb{E}\/}_{v(m|Z_{i})}\Big{|}\mathop{\mathbb{E}\/}_{v(xy|mZ_{i})}\Big{[}(-1)^{h}\Big{]}\Big{|}$
$\displaystyle=\sum_{i=1}^{2}v(Z_{i}|R)^{1-\delta}\cdot\Big{(}\frac{v(Z_{i})}{v(R)}\Big{)}^{\delta}\cdot\mathop{\mathbb{E}\/}_{v(m|Z_{i})}\Big{|}\mathop{\mathbb{E}\/}_{v(xy|mZ_{i})}\Big{[}(-1)^{h}\Big{]}\Big{|}$
$\displaystyle\leq\sum_{i=1}^{2}v(Z_{i}|R)^{1-\delta}\cdot\mathop{\mathbb{E}\/}_{v(m|R)}\Big{|}\mathop{\mathbb{E}\/}_{v(xy|mR)}\Big{[}(-1)^{h}\Big{]}\Big{|}$
(because $R$ is the maximizer of Equation 40) $\displaystyle\leq
2^{\delta}\cdot\Big{(}\sum_{i=1}^{2}v(Z_{i}|R)\Big{)}^{1-\delta}\cdot\mathop{\mathbb{E}\/}_{v(m|R)}\Big{|}\mathop{\mathbb{E}\/}_{v(xy|mR)}\Big{[}(-1)^{h}\Big{]}\Big{|}$
(by Hölder’s inequality)
$\displaystyle=2^{\delta}\cdot\Big{(}1-v(Z|R)\Big{)}^{1-\delta}\cdot\mathop{\mathbb{E}\/}_{v(m|R)}\Big{|}\mathop{\mathbb{E}\/}_{v(xy|mR)}\Big{[}(-1)^{h}\Big{]}\Big{|}.$

Using the inequalities $(1-t)^{1-\delta}\leq 1-t(1-\delta))$ and
$2^{\delta}\leq 1+\delta$ which hold for $t,\delta\in[0,1]$:

$\displaystyle\leq(1+\delta)\cdot(1-(1-\delta)v(Z|R))\cdot\mathop{\mathbb{E}\/}_{v(m|R)}\Big{|}\mathop{\mathbb{E}\/}_{v(xy|mR)}\Big{[}(-1)^{h}\Big{]}\Big{|}.$

Putting this back into Equation 41 and reaarranging, we get:

$\displaystyle\mathop{\mathbb{E}\/}_{v(m|Z)}\Big{|}\mathop{\mathbb{E}\/}_{v(xy|mZ)}\Big{[}(-1)^{h}\Big{]}\Big{|}$
$\displaystyle\geq\frac{-\delta+(1-\delta^{2})v(Z|R)}{v(Z|R)}\mathop{\mathbb{E}\/}_{v(m|R)}\Big{|}\mathop{\mathbb{E}\/}_{v(xy|mR)}\Big{[}(-1)^{h}\Big{]}\Big{|}$
$\displaystyle\geq(1-\delta^{2}-\delta/v(Z|R))\cdot
v(R)^{-\delta}\cdot\mathop{\mathbb{E}\/}_{v(m)}\Big{|}\mathop{\mathbb{E}\/}_{v(xy|m)}\Big{[}(-1)^{h}\Big{]}\Big{|},$

where we again used the fact that $R$ maximizes Equation 40. ∎

######  Lemma 31.

Let $q(xym)$ be a rectangular distribution, with $x=x_{1}x_{2}$ and
$y=y_{1}y_{2}$. Let $f(x_{1}y_{1}),g(x_{2}y_{2})$ be Boolean functions. Let
$G$ be a subset of triples $xym$ such that the indicator function $1_{G}(xym)$
depends only on $w=x_{1}y_{2}m$, and for each $m$, $G$ maximizes

$\displaystyle
q(G|m)^{\delta}\cdot\Big{|}\mathop{\mathbb{E}\/}_{q(xy|mG)}\Big{[}(-1)^{f\oplus
g}\Big{]}\Big{|},$ (42)

among all such sets. Then for any $w$ in the support of $G$, we have

$\left|\mathop{\mathbb{E}\/}_{q(xy|w)}\left[(-1)^{f\oplus
g}\right]\right|\geq(1-\delta)\cdot
q(G|m)^{-\delta}\cdot\left|\mathop{\mathbb{E}\/}_{q(xy|m)}\left[(-1)^{f\oplus
g}\right]\right|.$

###### Proof.

Fix $w=x_{1}y_{2}m$ and define $G^{\prime}\subseteq G$ to be the subset of $G$
obtained by deleting all triples $xym$ consistent with $w$. Using the triangle
inequality, we can write

$\displaystyle\Big{|}\mathop{\mathbb{E}\/}_{q(xy|mG)}\Big{[}(-1)^{f\oplus
g}\Big{]}\Big{|}$ $\displaystyle\leq
q(w|mG)\cdot\Big{|}\mathop{\mathbb{E}\/}_{q(xy|w)}\Big{[}(-1)^{f\oplus
g}\Big{]}\Big{|}+q(G^{\prime}|mG)\cdot\Big{|}\mathop{\mathbb{E}\/}_{q(xy|mG^{\prime})}\Big{[}(-1)^{f\oplus
g}\Big{]}\Big{|}$
$\displaystyle=q(w|mG)\cdot\Big{|}\mathop{\mathbb{E}\/}_{q(xy|w)}\Big{[}(-1)^{f\oplus
g}\Big{]}\Big{|}+q(G^{\prime}|mG)^{1-\delta}\cdot\frac{q(G^{\prime}|m)^{\delta}}{q(G|m)^{\delta}}\cdot\Big{|}\mathop{\mathbb{E}\/}_{q(xy|mG^{\prime})}\Big{[}(-1)^{f\oplus
g}\Big{]}\Big{|}$ $\displaystyle\leq
q(w|mG)\cdot\Big{|}\mathop{\mathbb{E}\/}_{q(xy|w)}\Big{[}(-1)^{f\oplus
g}\Big{]}\Big{|}+q(G^{\prime}|mG)^{1-\delta}\cdot\Big{|}\mathop{\mathbb{E}\/}_{q(xy|mG)}\Big{[}(-1)^{f\oplus
g}\Big{]}\Big{|},$

where in the last line we used the fact that $G$ is the maximizer of Equation
42.

Because $q(G^{\prime}|mG)=1-q(w|mG)$, and using the inequality
$(1-t)^{\gamma}\leq 1-t\gamma$, which holds for $t,\gamma\in[0,1]$, we obtain

$\displaystyle\Big{|}\mathop{\mathbb{E}\/}_{q(xy|mG)}\Big{[}(-1)^{f\oplus
g}\Big{]}\Big{|}$ $\displaystyle\leq
q(w|mG)\cdot\Big{|}\mathop{\mathbb{E}\/}_{q(xy|w)}\Big{[}(-1)^{f\oplus
g}\Big{]}\Big{|}+(1-(1-\delta)q(w|mG))\cdot\Big{|}\mathop{\mathbb{E}\/}_{q(xy|mG)}\Big{[}(-1)^{f\oplus
g}\Big{]}\Big{|}.$

Rearranging gives:

$\displaystyle\Big{|}\mathop{\mathbb{E}\/}_{q(xy|w)}\Big{[}(-1)^{f\oplus
g}\Big{]}\Big{|}$
$\displaystyle\geq(1-\delta)\cdot\Big{|}\mathop{\mathbb{E}\/}_{q(xy|mG)}\Big{[}(-1)^{f\oplus
g}\Big{]}\Big{|}$ $\displaystyle\geq(1-\delta)\cdot
q(G|m)^{-\delta}\cdot\Big{|}\mathop{\mathbb{E}\/}_{q(xy|m)}\Big{[}(-1)^{f\oplus
g}\Big{]}\Big{|},$

where in the second inequality we once again used the fact that $G$ is the
maximizer of Equation 42. ∎

##  6 Consequences of small marginal information

Let $q$ be a rectangular distribution achieving $\mathsf{M}_{I}(p,f)$. Since
$q$ is rectangular, we can write

$\displaystyle\frac{q(xym)}{p(xym)}=\frac{\mu(xy)\cdot A(xm)\cdot
B(ym)}{\mu(xy)\cdot p(m_{0})\cdot\prod_{i=1,3,5,\dotsc}p(m_{i}|xm_{<i})\cdot
p(m_{i+1}|ym_{\leq i})}=g_{1}(xm)\cdot g_{2}(ym),$ (43)

for appropriate functions $g_{1}$ and $g_{2}$.

For every $K\geq 1$, define the sets

$\displaystyle S_{K}$ $\displaystyle=\\{xym:\left|\lceil\log
g_{1}(xm)\rceil+\log g_{2}(ym)\right|\leq 3(\mathsf{M}_{I}(p,f)+KI)/I\\},$
(44) $\displaystyle R_{K}$ $\displaystyle=\\{xym:p(m_{1}|xm_{0})\leq
2^{6(\mathsf{M}_{I}(p,f)+KI)}\cdot p(m_{1}|ym_{0})\\}..$ (45)

######  Proposition 32.

For $xym\in S_{K}$,

$\displaystyle-\frac{3(\mathsf{M}_{I}(p,f)+KI)}{I}-1\leq\log\frac{q(xym)}{p(xym)}\leq\frac{3(\mathsf{M}_{I}(p,f)+KI)}{I}.$
(46)

###### Proof.

Because $\log(q(xym)/p(xym))=\log g_{1}(xm)+\log g_{2}(ym)$,

$\displaystyle\log\frac{q(xym)}{p(xym)}\geq\lceil\log g_{1}(xm)\rceil+\log
g_{2}(ym)-1\geq-\frac{3(\mathsf{M}_{I}(p,f)+KI)}{I}-1,$

and

$\displaystyle\log\frac{q(xym)}{p(xym)}\leq\lceil\log g_{1}(xm)\rceil+\log
g_{2}(ym)\leq\frac{3(\mathsf{M}_{I}(p,f)+KI)}{I}.$

∎

######  Claim 33.

If $K\geq 3$, $q(S_{K}^{c}),q(R_{K}^{c}|S_{K})\leq 5\cdot
2^{-(\mathsf{M}_{I}(p,f)+KI)/I}$.

###### Proof.

Define

$\displaystyle G_{1}$ $\displaystyle=\\{xym:q(x|ym)\geq
2^{-(\mathsf{M}_{I}(p,f)+KI)/I}\cdot p(x|y)\\},$ $\displaystyle G_{2}$
$\displaystyle=\\{xym:q(y|xm)\geq 2^{-(\mathsf{M}_{I}(p,f)+KI)/I}\cdot
p(y|x)\\},$ $\displaystyle G_{3}$ $\displaystyle=\\{xym:q(xym)\geq
2^{-3(\mathsf{M}_{I}(p,f)+KI)/I}\cdot p(xym)\\},\text{ and }$ $\displaystyle
G_{4}$ $\displaystyle=\\{xym:q(x|ym)\geq 2^{-(\mathsf{M}_{I}(p,f)+KI)/I}\cdot
p(x|m_{0}m_{1}y)\\}.$

If $xym\in G_{1}\cap G_{2}$, then

$\displaystyle\mathsf{M}_{I}(p,f)$
$\displaystyle\geq\log\Bigg{(}\frac{q(x|ym)}{p(x|y)}\cdot\frac{q(y|xm)}{p(y|x)}\cdot\left(\frac{q(xym)}{p(xym)}\right)^{I}\cdot\bigg{|}\mathop{\mathbb{E}\/}_{q(xy|m)}\left[(-1)^{f}\right]\bigg{|}^{-12I/\delta}\Bigg{)}$
$\displaystyle\geq-\frac{2(\mathsf{M}_{I}(p,f)+KI)}{I}+I\cdot\log\frac{q(xym)}{p(xym)}$
(because $xym\in G_{1}\cap G_{2}$)
$\displaystyle\geq-2\mathsf{M}_{I}(p,f)-2KI+I\cdot(\lceil\log
g_{1}(xm)\rceil+\log g_{2}(ym)-1)$ (using $I\geq 1$)

and rearranging this and using the fact that $KI\geq 1$ gives

$\displaystyle\lceil\log g_{1}(xm)\rceil+\log g_{2}(ym)\leq
3(\mathsf{M}_{I}(p,f)+KI)/I.$

Moreover, for $xym\in G_{3}$,

$\lceil\log g_{1}(xm)\rceil+\log
g_{2}(ym)\geq\log\frac{q(xym)}{p(xym)}\geq-3(\mathsf{M}_{I}(p,f)+KI)/I,$

so we have $G_{1}\cap G_{2}\cap G_{3}\subseteq S_{K}$. We shall prove that
$q(S_{K}^{c})\leq 3\cdot 2^{-(\mathsf{M}_{I}(p,f)+KI)/I}$ by proving that
$q(G_{1}^{c}),q(G_{2}^{c}),q(G_{3}^{c})$ and $q(G_{4}^{c})$ are all less than
$2^{-(\mathsf{M}_{I}(p,f)+KI)/I}$. We have

$\displaystyle q(G_{1}^{c})=\sum_{xym\notin G_{1}}q(xym)$
$\displaystyle<\sum_{xym\notin G_{1}}q(ym)\cdot p(x|y)\cdot
2^{-(\mathsf{M}_{I}(p,f)+KI)/I}$ $\displaystyle\leq
2^{-(\mathsf{M}_{I}(p,f)+KI)/I}\cdot\sum_{xym}q(ym)\cdot p(x|y)$
$\displaystyle\leq 2^{-(\mathsf{M}_{I}(p,f)+KI)/I},$

and similar calculations show that
$q(G_{2}^{c}),q(G_{3}^{c}),q(G_{4}^{c})<2^{-(\mathsf{M}_{I}(p,f)+KI)/I}$.

It only remains to bound $q(R_{K}^{c}|S_{K})$. We have

$\displaystyle\frac{p(m_{1}|xm_{0})}{p(m_{1}|ym_{0})}=\frac{p(m_{1}|xym_{0})}{p(m_{1}|ym_{0})}=\frac{p(x|ym_{0}m_{1})}{p(x|ym_{0})}=\frac{p(x|ym_{0}m_{1})}{q(x|ym)}\cdot\frac{q(x|ym)}{p(x|y)},$

so, for every $xym\in G_{2}\cap G_{3}\cap G_{4}$,

$\displaystyle\mathsf{M}_{I}(p,f)$
$\displaystyle\geq\log\Bigg{(}\frac{q(x|ym)}{p(x|y)}\cdot\frac{q(y|xm)}{p(y|x)}\cdot\left(\frac{q(xym)}{p(xym)}\right)^{I}\cdot\bigg{|}\mathop{\mathbb{E}\/}_{q(xy|m)}\left[(-1)^{f}\right]\bigg{|}^{-12I/\delta}\Bigg{)}$
$\displaystyle\geq\log\Bigg{(}\frac{p(m_{1}|xm_{0})}{p(m_{1}|ym_{0})}\cdot\frac{q(x|ym)}{p(x|ym_{0}m_{1})}\cdot\frac{q(y|xm)}{p(y|x)}\cdot\left(\frac{q(xym)}{p(xym)}\right)^{I}\Bigg{)}$
$\displaystyle\geq\log\frac{p(m_{1}|xm_{0})}{p(m_{1}|ym_{0})}-\frac{2(\mathsf{M}_{I}(p,f)+KI)}{I}-3(\mathsf{M}_{I}(p,f)+KI)$
$\displaystyle\geq\log\frac{p(m_{1}|xm_{0})}{p(m_{1}|ym_{0})}-5(\mathsf{M}_{I}(p,f)+KI),$

since $I\geq 1$. Rearranging, we get $p(m_{1}|xm_{0})\leq
2^{6(\mathsf{M}_{I}(p,f)+KI)}\cdot p(m_{1}|ym_{0})$, so $G_{2}\cap G_{3}\cap
G_{4}\subseteq R_{K}$. The union bound then gives:

$\displaystyle q(R_{K}^{c}|S_{K})$
$\displaystyle\leq\frac{q(G_{2}^{c})+q(G_{3}^{c})+q(G_{4}^{c})}{q(S_{K})}<\frac{3\cdot
2^{-(\mathsf{M}_{I}(p,f)+KI)/I}}{1-3\cdot 2^{-(\mathsf{M}_{I}(p,f)+KI)/I}}\leq
5\cdot 2^{-3(\mathsf{M}_{I}(p,f)+KI)/I},$

since $K\geq 3$. ∎

An argument analogous to the one in the previous claim allows us to obtain
similar bounds if marginal information cost is replaced by external marginal
information cost:

######  Claim 34.

Let $q$ be a rectangular distribution achieving
$\mathsf{M}^{\mathsf{ext}}_{I}(p,f)$ and let $g_{1},g_{2}$ be as defined in
Equation 43. For every $K$, define

$\displaystyle S_{K}$ $\displaystyle=\\{xym:\left|\lceil\log
g_{1}(xm)\rceil+\log g_{2}(ym)\right|\leq
3(\mathsf{M}^{\mathsf{ext}}_{I}(p,f)+KI)/I\\}\text{ and }$ (47) $\displaystyle
R_{K}$ $\displaystyle=\\{xym:p(m_{1}|xm_{0})\leq
2^{5(\mathsf{M}^{\mathsf{ext}}_{I}(p,f)+KI)}\cdot p(m_{1}|m_{0})\\}.$ (48)

Then, for all $K\geq 2$, it holds that $q(S_{K}^{c}),q(R_{K}^{c}|S_{K})\leq
4\cdot 2^{-(\mathsf{M}^{\mathsf{ext}}_{I}(p,f)+KI)/I}$.

###### Proof.

Define

$\displaystyle G_{1}$ $\displaystyle=\\{xym:q(xy|m)\geq
2^{-(\mathsf{M}^{\mathsf{ext}}_{I}(p,f)+KI)/I}\cdot p(xy)\\},$ $\displaystyle
G_{2}$ $\displaystyle=\\{xym:q(xym)\geq
2^{-3(\mathsf{M}^{\mathsf{ext}}_{I}(p,f)+KI)/I}\cdot p(xym)\\},$
$\displaystyle G_{3}$ $\displaystyle=\\{xym:q(xy|m)\geq
2^{-(\mathsf{M}^{\mathsf{ext}}_{I}(p,f)+KI)/I}\cdot p(xy|m_{0}m_{1})\\}.$

For $xym\in G_{1}\cap G_{2}$, we have

$\displaystyle\mathsf{M}^{\mathsf{ext}}_{I}(p,f)$
$\displaystyle\geq\log\Bigg{(}\frac{q(xy|m)}{p(xy)}\cdot\left(\frac{q(xym)}{p(xym)}\right)^{I}\cdot\bigg{|}\mathop{\mathbb{E}\/}_{q(xy|m)}\left[(-1)^{f}\right]\bigg{|}^{-12I/\delta}\Bigg{)}$
$\displaystyle\geq-\frac{(\mathsf{M}^{\mathsf{ext}}_{I}(p,f)+KI)}{I}+I\cdot\log\frac{q(xym)}{p(xym)}$
$\displaystyle\geq-(\mathsf{M}^{\mathsf{ext}}_{I}(p,f)+KI)+I\cdot(\lceil\log
g_{1}(xm)\rceil+\log g_{2}(ym)-1),$

since $K,I\geq 1$. Rearranging gives

$\lceil\log g_{1}(xm)\rceil+\log
g_{2}(ym)\leq\frac{3(\mathsf{M}^{\mathsf{ext}}_{I}(p,f)+KI)}{I}.$

Moreover, for $xym\in G_{2}$

$\lceil\log g_{1}(xm)\rceil+\log
g_{2}(ym)\geq\log\frac{q(xym)}{p(xym)}\geq-\frac{3(\mathsf{M}^{\mathsf{ext}}_{I}(p,f)+KI)}{I},$

proving that $G_{1}\cap G_{2}\subseteq S_{K}$.

We show that $q(G_{1}^{c}),q(G_{2}^{c})$ and $q(G_{3}^{c})$ are all less than
$2^{-(\mathsf{M}^{\mathsf{ext}}_{I}(p,f)+KI)/I}$, which implies that
$q(S_{K}^{c})\leq 2\cdot 2^{-(\mathsf{M}^{\mathsf{ext}}_{I}(p,f)+KI)/I}$ as
desired. To see the upper bound on $q(G_{1}^{c})$, we may write

$\displaystyle q(G_{1}^{c})=\sum_{xym\notin G_{1}}q(xym)$
$\displaystyle<\sum_{xym\notin G_{1}}q(m)\cdot p(xy)\cdot
2^{-3(\mathsf{M}^{\mathsf{ext}}_{I}(p,f)+KI)/I}\leq
2^{-(\mathsf{M}^{\mathsf{ext}}_{I}(p,f)+KI)/I}.$

A similar calculation shows that $q(G_{2}^{c})$ and
$q(G_{3}^{c})<2^{-(\mathsf{M}^{\mathsf{ext}}_{I}(p,f)+KI)/I}$.

Now, we prove that $q(R_{K}^{c}|S_{K})\leq 5\cdot
2^{-(\mathsf{M}^{\mathsf{ext}}_{I}(p,f)+KI)/I}$. We have

$\displaystyle\frac{p(m_{1}|xm_{0})}{p(m_{1}|m_{0})}=\frac{p(m_{1}|xym_{0})}{p(m_{1}|m_{0})}=\frac{p(xy|m_{0}m_{1})}{p(xy)}=\frac{p(xy|m_{0}m_{1})}{q(xy|m)}\cdot\frac{q(xy|m)}{p(xy)},$

so for every $xym\in G_{2}\cap G_{3}$,

$\displaystyle\mathsf{M}^{\mathsf{ext}}_{I}(p,f)$
$\displaystyle\geq\log\Bigg{(}\frac{q(xy|y)}{p(xy)}\cdot\left(\frac{q(xym)}{p(xym)}\right)^{I}\cdot\bigg{|}\mathop{\mathbb{E}\/}_{q(xy|m)}\left[(-1)^{f}\right]\bigg{|}^{-12I/\delta}\Bigg{)}$
$\displaystyle\geq\log\Bigg{(}\frac{p(m_{1}|xm_{0})}{p(m_{1}|m_{0})}\cdot\frac{q(xy|m)}{p(xy|m_{0}m_{1})}\cdot\left(\frac{q(xym)}{p(xym)}\right)^{I}\Bigg{)}$
$\displaystyle\geq\log\frac{p(m_{1}|xym_{0})}{p(m_{1}|m_{0})}-\frac{(\mathsf{M}^{\mathsf{ext}}_{I}(p,f)+KI)}{I}-(\mathsf{M}^{\mathsf{ext}}_{I}(p,f)+KI)$
$\displaystyle\geq\log\frac{p(m_{1}|xym_{0})}{p(m_{1}|m_{0})}-4(\mathsf{M}^{\mathsf{ext}}_{I}(p,f)+KI),$

since $I\geq 1$. Rearranging, we get $p(m_{1}|xym_{0})\leq
2^{5(\mathsf{M}^{\mathsf{ext}}_{I}(p,f)+KI)}\cdot p(m_{1}|m_{0})$ for all
$xym\in G_{2}\cap G_{3}$, and so $G_{2}\cap G_{3}\subseteq R_{K}$. The union
bound then gives:

$\displaystyle q(R_{K}^{c}|S_{K})$
$\displaystyle\leq\frac{q(G_{2}^{c})+q(G_{3}^{c})}{q(S_{K})}<\frac{2\cdot
2^{-(\mathsf{M}^{\mathsf{ext}}_{I}(p,f)+KI)/I}}{1-2\cdot
2^{-(\mathsf{M}^{\mathsf{ext}}_{I}(p,f)+KI)/I}}\leq 4\cdot
2^{-(\mathsf{M}^{\mathsf{ext}}_{I}(p,f)+KI)/I},$

since $K\geq 2$. ∎

For the bounded-round simulation protocol, we need the following claim.

######  Claim 35.

Let $K\geq 3$, and $S_{K}$ be the set defined in Equation 44. Let $p(xym)$ be
an $r$-round protocol and define

$\displaystyle T_{K}=\Big{\\{}xym:\forall
i,\frac{p(m_{i}|xym_{<i})}{p(m_{i}|ym_{<i})},\frac{p(m_{i}|xym_{<i})}{p(m_{i}|xm_{<i})}\leq
2^{14(\mathsf{M}_{I}(p,f)+KI)}\cdot(r+1)^{5}\Big{\\}}.$

Then $q(T_{K}^{c}|S_{K})\leq 22\cdot 2^{-(\mathsf{M}_{I}(p,f)+KI)/I}$.

###### Proof.

Define the sets

$\displaystyle G_{1}$ $\displaystyle=\\{xm:\forall i,q(xm_{\leq i})\geq
2^{-(\mathsf{M}_{I}(p,f)+KI)/I}\cdot(r+1)^{-1}\cdot p(xm_{\leq i})\\},$
$\displaystyle G_{1}^{\prime}$ $\displaystyle=\\{ym:\forall i:q(ym_{\leq
i})\geq 2^{-(\mathsf{M}_{I}(p,f)+KI)/I}\cdot(r+1)^{-1}\cdot p(ym_{<i})\\},$
$\displaystyle G_{2}$ $\displaystyle=\\{xym:\forall i,q(x|ym_{\leq i})\geq
2^{-(\mathsf{M}_{I}(p,f)+KI)/I}\cdot(r+1)^{-1}\cdot p(x|y)\\},$ $\displaystyle
G_{2}^{\prime}$ $\displaystyle=\\{xym:\forall i,q(y|xm_{\leq i})\geq
2^{-(\mathsf{M}_{I}(p,f)+KI)/I}\cdot(r+1)^{-1}\cdot p(y|x)\\},$ $\displaystyle
G_{3}$ $\displaystyle=\\{xym:\forall i,q(x|ym)\geq
2^{-(\mathsf{M}_{I}(p,f)+KI)/I}\cdot(r+1)^{-1}\cdot p(x|ym_{\leq i})\\},$
$\displaystyle G_{3}^{\prime}$ $\displaystyle=\\{xym:\forall i,q(y|xm)\geq
2^{-(\mathsf{M}_{I}(p,f)+KI)/I}\cdot(r+1)^{-1}\cdot p(y|xm_{\leq i})\\},$
$\displaystyle G_{4}$ $\displaystyle=\\{xym:\forall i,q(m_{\geq
i}|xym_{<i})\geq 2^{-(\mathsf{M}_{I}(p,f)+KI)/I}\cdot(r+1)^{-1}\cdot p(m_{\geq
i}|xym_{<i})\\}.$

We claim that

$\displaystyle\bigcap_{j=1}^{3}(G_{j}\cap G_{j}^{\prime})\cap G_{4}\cap
S_{K}\subseteq T_{K}.$ (49)

For $xym\in G_{2}^{\prime}\cap G_{2}\cap S_{K}$,

$\displaystyle\mathsf{M}_{I}(p,f)$
$\displaystyle\geq\log\Bigg{(}\frac{q(x|ym)}{p(x|y)}\cdot\frac{q(y|xm)}{p(y|x)}\cdot\left(\frac{q(xym)}{p(xym)}\right)^{I}\cdot\bigg{|}\mathop{\mathbb{E}\/}_{q(xy|m)}\left[(-1)^{f}\right]\bigg{|}^{-12I/\delta}\Bigg{)}$
$\displaystyle\geq\log\frac{q(x|ym)}{p(x|y)}-\frac{(\mathsf{M}_{I}(p,f)+KI)}{I}-\log(r+1)-3(\mathsf{M}_{I}(p,f)+KI)-I$
$\displaystyle\geq\log\frac{q(x|ym)}{p(x|y)}-4\mathsf{M}_{I}(p,f)-5KI-\log(r+1),$

becase $I\geq 1$, and by the definition of $G_{2}^{\prime}$ and Equation 46.
Rearranging implies the first inequality below, and the second has a similar
proof:

$\displaystyle\frac{q(x|ym)}{p(x|y)},\frac{q(y|xm)}{p(y|x)}\leq
2^{5(\mathsf{M}_{I}(p,f)+KI)/I}\cdot(r+1).$ (50)

By Equation 50, for $xym\in\bigcap_{j=1}^{3}(G_{j}\cap G_{j}^{\prime})\cap
G_{4}\cap S_{K}$ and all $i$,

$\displaystyle\frac{p(m_{\leq i}|xy)}{p(m_{\leq i}|y)}=\frac{p(x|ym_{\leq
i})}{p(x|y)}=\frac{p(x|ym_{\leq i})}{q(x|ym)}\cdot\frac{q(x|ym)}{p(x|y)}\leq
2^{(\mathsf{M}_{I}(p,f)+KI)/I}\cdot
2^{5(\mathsf{M}_{I}(p,f)+KI)}\cdot(r+1)^{2}.$

Moreover,

$\displaystyle\frac{p(m_{\leq i}|xy)}{p(m_{\leq i}|y)}$
$\displaystyle=\frac{p(x|ym_{\leq i})}{p(x|y)}$
$\displaystyle=\frac{p(x|ym_{\leq i})}{q(x|ym_{\leq
i})}\cdot\frac{q(x|ym_{\leq i})}{p(x|y)}$ $\displaystyle=\frac{p(xym_{\leq
i})}{q(xym_{\leq i})}\cdot\frac{q(ym_{\leq i})}{p(ym_{\leq
i})}\cdot\frac{q(x|ym_{\leq i})}{p(x|y)}$
$\displaystyle=\frac{p(xym)}{q(xym)}\cdot\frac{q(m_{>i}|xym_{\leq
i})}{p(m_{>i}|xym_{\leq i})}\cdot\frac{q(ym_{\leq i})}{p(ym_{\leq
i})}\cdot\frac{q(x|ym_{\leq
i})}{p(x|y)}\geq\frac{2^{-6(\mathsf{M}_{I}(p,f)+KI)/I}}{(r+1)^{3}},$

where we used Equation 46 as well as the definitions of $G_{4},G_{1}^{\prime}$
and $G_{2}$ in the last step. Thus,

$\displaystyle\frac{p(m_{i}|xym_{<i})}{p(m_{i}|ym_{<i})}=\frac{p(m_{\leq
i}|xy)}{p(m_{\leq i}|y)}\cdot\frac{p(m_{<i}|y)}{p(m_{<i}|xy)}$
$\displaystyle\leq 2^{9(\mathsf{M}_{I}(p,f)+KI)/I}\cdot
2^{5(\mathsf{M}_{I}(p,f)+KI)}\cdot(r+1)^{5}$ $\displaystyle\leq
2^{14(\mathsf{M}_{I}(p,f)+KI)}\cdot(r+1)^{5},$

since $I\geq 1$. A similar calculation shows that
$\frac{p(m_{i}|xym_{<i})}{p(m_{i}|xm_{<i})}<2^{14(\mathsf{M}_{I}(p,f)+KI)}\cdot(r+1)^{5}$.
We conclude that Equation 49 holds.

Next, we show that $q(G_{4}^{c})<2^{-(\mathsf{M}_{I}(p,f)+KI)/I}$. Define

$\displaystyle t(xym)$ $\displaystyle=\begin{cases}\min\\{i:q(m_{\geq
i}|xym_{<i})<\frac{2^{-(\mathsf{M}_{I}(p,f)+KI)/I}\cdot p(m_{\geq
i}|xym_{<i})}{r+1}\\}&\text{if such $i$ exists,}\\\
\bot&\text{otherwise.}\end{cases}$

We have,

$\displaystyle q(G_{4}^{c})=q(t\neq\bot)$
$\displaystyle=\sum_{i=0}^{r}\sum_{\begin{subarray}{c}xym,\\\
t(xym)=i\end{subarray}}q(xym)$
$\displaystyle<\frac{2^{-(\mathsf{M}_{I}(p,f)+KI)/I}}{r+1}\cdot\sum_{i=0}^{r}\sum_{\begin{subarray}{c}xym\\\
t(xym)=i\end{subarray}}q(xym_{<i})\cdot p(m_{\geq i}|xym_{<i})$
$\displaystyle\leq 2^{-(\mathsf{M}_{I}(p,f)+KI)/I}.$

A similar argument shows that $q(G_{j}^{c}),q(G_{j}^{\prime
c})<2^{-(\mathsf{M}_{I}(p,f)+KI)/I}$, for all $j\in\\{1,2,3\\}$. Thus, we can
bound

$\displaystyle q(T_{K}^{c}|S_{K})$
$\displaystyle\leq\sum_{j=1}^{3}\frac{q(G_{j}^{c})+q(G_{j}^{\prime
c})}{q(S_{K})}+\frac{q(G_{4}^{c})+q(S_{K}^{c})}{q(S_{K})}$ $\displaystyle\leq
11\cdot\frac{2^{-(\mathsf{M}_{I}(p,f)+KI)/I}}{1-2^{-(\mathsf{M}_{I}(p,f)+KI)/I+2}}\leq
22\cdot 2^{-(\mathsf{M}_{I}(p,f)+KI)/I},$

where we used 33 and the fact that $K\geq 3$. ∎

######  Claim 36.

For any $K\geq 1$, let $S_{K}$ be the set defined in Equation 44 and define

$\displaystyle T_{K}$ $\displaystyle=\\{xym:p(m|xy)\leq
2^{6(\mathsf{M}_{I}(p,f)+KI)}\cdot\min\\{p(m|x),p(m|y)\\}\\}.$ (51)

Then, for all $K\geq 3$, $q(T_{K}^{c}|S_{K})\leq 6\cdot
2^{-(\mathsf{M}_{I}(p,f)+KI)/I}$.

###### Proof.

Define the sets

$\displaystyle G_{1}$
$\displaystyle=\\{xym:q(m|xy)<2^{-(\mathsf{M}_{I}(p,f)+KI)/I}p(m|xy)\\}$
$\displaystyle G_{2}$
$\displaystyle=\\{xym:q(x|ym)<2^{-(\mathsf{M}_{I}(p,f)+KI)/I}p(x|y)\\}$
$\displaystyle G_{3}$
$\displaystyle=\\{xym:q(y|xm)<2^{-(\mathsf{M}_{I}(p,f)+KI)/I}p(y|x)\\}.$

We claim that $q(G_{1}^{c}),q(G_{2}^{c})$ and $q(G_{3}^{c})$ are all smaller
than $2^{-(\mathsf{M}_{I}(p,f)+KI)/I}$. Indeed, to bound $q(G_{1}^{c})$, we
see that

$\displaystyle q(G_{1}^{c})=\sum_{xym\in
G_{1}}q(xym)<2^{-(\mathsf{M}_{I}(p,f)+KI)/I}\cdot\sum_{xym\in G_{1}}q(xy)\cdot
p(m|xy)\leq 2^{-(\mathsf{M}_{I}(p,f)+KI)/I}.$

The proof for the bounds on $q(G_{2}^{c})$ and $q(G_{3}^{c})$ are similar. For
any $xym\in G_{1}\cap G_{2}\cap S_{K}$, we have

$\displaystyle\mathsf{M}_{I}(p,f)$
$\displaystyle\geq\log\Bigg{(}\frac{q(x|ym)}{p(x|y)}\cdot\frac{q(y|xm)}{p(y|x)}\cdot\left(\frac{q(xym)}{p(xym)}\right)^{I}\cdot\bigg{|}\mathop{\mathbb{E}\/}_{q(xy|m)}\left[(-1)^{f}\right]\bigg{|}^{-12I/\delta}\Bigg{)}$
$\displaystyle\geq\log\frac{q(x|ym)}{p(x|y)}-\frac{(\mathsf{M}_{I}(p,f)+KI)}{I}-3(\mathsf{M}_{I}(p,f)+KI)-I$
(by Equation 46 and definition of $G_{2}$)
$\displaystyle\geq\log\frac{q(x|ym)}{p(x|ym)}+\log\frac{p(x|ym)}{p(x|y)}-4(\mathsf{M}_{I}(p,f)+KI)-I$
(since $I\geq 1$)
$\displaystyle\geq-\frac{(\mathsf{M}_{I}(p,f)+KI)}{I}+\log\frac{p(m|xy)}{p(m|y)}-4(\mathsf{M}_{I}(p,f)+KI)-I,$

where in the last step we used the fact $p(m|xy)/p(m|y)=p(x|ym)/p(x|y)$.
Rearranging, we get that for every $xym\in G_{1}\cap G_{2}\cap S_{K}$

$\displaystyle\log\frac{p(m|xy)}{p(m|y)}\leq 6(\mathsf{M}_{I}(p,f)+KI).$

A similar calculation shows that for every $xym\in G_{1}\cap G_{3}\cap S_{K}$
it holds that

$\displaystyle\log\frac{p(m|xy)}{p(m|x)}\leq 6(\mathsf{M}_{I}(p,f)+KI).$

Therefore,

$\displaystyle
q(T_{K}^{c}|S_{K})\leq\frac{q(G_{1}^{c})+q(G_{2}^{c})+q(G_{3}^{c})}{q(S_{K})}\leq
6\cdot 2^{-(\mathsf{M}_{I}(p,f)+KI)/I}.$

∎

Additionally, the bound on the marginal information cost implies the following
lemma which will be useful in our simulation.

######  Lemma 37.

$\displaystyle\mathop{\mathbb{E}\/}_{q(xym)}\bigg{[}\sum_{i\geq
2}^{C}\|p(m_{i}|xm_{<i})-p(m_{i}|ym_{<i})\|_{1}\bigg{]}$ $\displaystyle\leq
8\sqrt{C\cdot\mathsf{M}_{I}(p,f)}$ (52)
$\displaystyle\mathop{\mathbb{E}\/}_{q(xym)}\bigg{[}\bigg{|}\mathop{\mathbb{E}\/}_{q(xy|m)}\left[(-1)^{f}\right]\bigg{|}\bigg{]}$
$\displaystyle\geq 2^{-\delta\mathsf{M}_{I}(p,f)/12I}.$ (53)

###### Proof.

By our bound on the marginal information cost, we get

$\displaystyle\mathsf{M}_{I}(p,f)$
$\displaystyle=\max_{xym\in\mathsf{supp}(q)}\log\Bigg{(}\frac{q(x|ym)}{p(x|y)}\cdot\frac{q(y|xm)}{p(y|x)}\cdot\left(\frac{q(xym)}{p(xym)}\right)^{I}\cdot\bigg{|}\mathop{\mathbb{E}\/}_{q(xy|m)}\left[(-1)^{f}\right]\bigg{|}^{-12I/\delta}\Bigg{)}$
$\displaystyle\geq\mathop{\mathbb{E}\/}_{q(xym)}\bigg{[}\log\frac{q(x|ym)}{p(x|y)}\bigg{]}+\mathop{\mathbb{E}\/}_{q(xym)}\bigg{[}\log\frac{q(y|xm)}{p(y|x)}\bigg{]}$
$\displaystyle\qquad+I\cdot\mathop{\mathbb{E}\/}_{q(xym)}\bigg{[}\log\frac{q(xym)}{p(xym)}\bigg{]}+\mathop{\mathbb{E}\/}_{q(xym)}\bigg{[}\log\bigg{|}\mathop{\mathbb{E}\/}_{q(xy|m)}\left[(-1)^{f}\right]\bigg{|}^{-12I/\delta}\bigg{]}$
(54)

By Equation 6 and the fact that the advantage is always at most $1$, each of
the expectations appearing above is non-negative, and so each term is bounded
by $\mathsf{M}_{I}(p,f)$. This implies

$\log\mathop{\mathbb{E}\/}_{q(xym)}\bigg{[}\bigg{|}\mathop{\mathbb{E}\/}_{q(xy|m)}\left[(-1)^{f}\right]\bigg{|}\bigg{]}\geq\mathop{\mathbb{E}\/}_{q(xym)}\bigg{[}\log\bigg{|}\mathop{\mathbb{E}\/}_{q(xy|m)}\left[(-1)^{f}\right]\bigg{|}\bigg{]}\geq-\frac{\delta\mathsf{M}_{I}(p,f)}{12I},$

thus giving Equation 53. For Equation 52, we have

$\displaystyle\mathop{\mathbb{E}\/}_{q(xym)}\bigg{[}\sum_{i\geq
2}^{C}\|p(m_{i}|xm_{<i})-p(m_{i}|ym_{<i})\|_{1}\bigg{]}$
$\displaystyle\leq\mathop{\mathbb{E}\/}_{q(xym)}\bigg{[}\sum_{i}\|p(m_{i}|xm_{<i})-q(m_{i}|xym_{<i})\|_{1}+\|q(m_{i}|xym_{<i})-p(m_{i}|ym_{<i})\|_{1}\bigg{]}$
$\displaystyle\leq
2\mathop{\mathbb{E}\/}_{q(xym)}\bigg{[}\sum_{i}\sqrt{\mathop{\mathbb{E}\/}_{q(m_{i}|xym_{<i})}\bigg{[}\log\frac{q(m_{i}|xym_{<i})}{p(m_{i}|xm_{<i})}\bigg{]}}+\sqrt{\mathop{\mathbb{E}\/}_{q(m_{i}|xym_{<i})}\bigg{[}\log\frac{q(m_{i}|xym_{<i})}{p(m_{i}|ym_{<i})}\bigg{]}}\bigg{]}$
(by Equation 7) $\displaystyle\leq
2\sqrt{C\cdot\mathop{\mathbb{E}\/}_{q(xym)}\bigg{[}\sum_{i}\log\frac{q(m_{i}|xym_{<i})}{p(m_{i}|xm_{<i})}\bigg{]}}+2\sqrt{C\cdot\mathop{\mathbb{E}\/}_{q(xym)}\bigg{[}\sum_{i}\log\frac{q(m_{i}|xym_{<i})}{p(m_{i}|ym_{<i})}\bigg{]}}$
$\displaystyle=2\sqrt{C\cdot\mathop{\mathbb{E}\/}_{q(xym)}\bigg{[}\log\frac{q(m|xy)}{p(m|x)}\bigg{]}}+2\sqrt{C\cdot\mathop{\mathbb{E}\/}_{q(xym)}\bigg{[}\log\frac{q(m|xy)}{p(m|y)}\bigg{]}}.$

To complete the proof, we claim that

$\mathop{\mathbb{E}\/}_{q(xym)}\bigg{[}\log\frac{q(m|xy)}{p(m|x)}\bigg{]},\mathop{\mathbb{E}\/}_{q(xym)}\bigg{[}\log\frac{q(m|xy)}{p(m|y)}\bigg{]}\leq\mathsf{M}_{I}(p,f)\cdot(1+1/I).$

We show this for the first term; the proof for the second term is identical.
First, we have

$\displaystyle\frac{q(m|xy)}{p(m|x)}$
$\displaystyle=\frac{q(m|xy)}{p(m|xy)}\cdot\frac{p(m|xy)}{p(m|x)}$
$\displaystyle=\frac{q(m|xy)}{p(m|xy)}\cdot\frac{p(x|ym)}{p(x|y)}$
$\displaystyle=\frac{q(m|xy)}{p(m|xy)}\cdot\frac{p(x|ym)}{q(x|ym)}\cdot\frac{q(x|ym)}{p(x|y)}$
$\displaystyle=\frac{q(xym)}{p(xym)}\cdot\frac{p(xy)}{q(xy)}\cdot\frac{p(x|ym)}{q(x|ym)}\cdot\frac{q(x|ym)}{p(x|y)}.$

Therefore,

$\displaystyle\mathop{\mathbb{E}\/}_{q(xym)}\bigg{[}\log\frac{q(m|xy)}{p(m|x)}\bigg{]}$
$\displaystyle=\mathop{\mathbb{E}\/}_{q(xym)}\bigg{[}\log\frac{q(xym)}{p(xym)}\bigg{]}+\mathop{\mathbb{E}\/}_{q(xym)}\bigg{[}\log\frac{p(xy)}{q(xy)}\bigg{]}+\mathop{\mathbb{E}\/}_{q(xym)}\bigg{[}\log\frac{p(x|ym)}{q(x|ym)}\bigg{]}+\mathop{\mathbb{E}\/}_{q(xym)}\bigg{[}\log\frac{q(x|ym)}{p(x|y)}\bigg{]}$
$\displaystyle\leq\mathop{\mathbb{E}\/}_{q(xym)}\bigg{[}\log\frac{q(xym)}{p(xym)}\bigg{]}+\log\mathop{\mathbb{E}\/}_{q(xym)}\bigg{[}\frac{p(xy)}{q(xy)}\bigg{]}+\log\mathop{\mathbb{E}\/}_{q(xym)}\bigg{[}\frac{p(x|ym)}{q(x|ym)}\bigg{]}+\mathop{\mathbb{E}\/}_{q(xym)}\bigg{[}\log\frac{q(x|ym)}{p(x|y)}\bigg{]}$
$\displaystyle\leq\mathop{\mathbb{E}\/}_{q(xym)}\bigg{[}\log\frac{q(xym)}{p(xym)}\bigg{]}+\mathop{\mathbb{E}\/}_{q(xym)}\bigg{[}\log\frac{q(x|ym)}{p(x|y)}\bigg{]}\leq\frac{\mathsf{M}_{I}(p,f)}{I}+\mathsf{M}_{I}(p,f),$

where in the first inequality, we used the concavity of $\log(\cdot)$ and in
the last one, we used Equation 54. ∎

For the simulation of external marginal information, we need a claim analogous
to the previous one.

######  Lemma 38.

Let $q$ be a distribution achieving $\mathsf{M}^{\mathsf{ext}}_{I}(p,f)$.
Then,

$\displaystyle\mathop{\mathbb{E}\/}_{q(xym)}\bigg{[}\log\frac{p(m|xy)}{p(m)}\bigg{]}$
$\displaystyle\leq\mathsf{M}^{\mathsf{ext}}_{I}(p,f),$ (55)
$\displaystyle\mathop{\mathbb{E}\/}_{q(xym)}\bigg{[}\bigg{|}\mathop{\mathbb{E}\/}_{q(xy|m)}\left[(-1)^{f}\right]\bigg{|}\bigg{]}$
$\displaystyle\geq 2^{-\delta\mathsf{M}^{\mathsf{ext}}_{I}(p,f)/(12I)}.$ (56)

###### Proof.

By our bound on the marginal information cost, we get

$\displaystyle\mathsf{M}^{\mathsf{ext}}_{I}(p,f)$
$\displaystyle=\max_{xym\in\mathsf{supp}(q)}\log\Bigg{(}\frac{q(xy|m)}{p(xy)}\cdot\left(\frac{q(xym)}{p(xym)}\right)^{I}\cdot\bigg{|}\mathop{\mathbb{E}\/}_{q(xy|m)}\left[(-1)^{f}\right]\bigg{|}^{-12I/\delta}\Bigg{)}$
$\displaystyle\geq\mathop{\mathbb{E}\/}_{q(xym)}\bigg{[}\log\frac{q(xy|m)}{p(xy)}\bigg{]}+I\cdot\mathop{\mathbb{E}\/}_{q(xym)}\bigg{[}\log\frac{q(xym)}{p(xym)}\bigg{]}-\frac{12I}{\delta}\cdot\mathop{\mathbb{E}\/}_{q(xym)}\bigg{[}\log\bigg{|}\mathop{\mathbb{E}\/}_{q(xy|m)}\left[(-1)^{f}\right]\bigg{|}\bigg{]}.$

By Equation 6 and the fact that the advantage is always at most $1$, each of
the expectations appearing above is non-negative, and so each term is bounded
by $\mathsf{M}_{I}(p,f)$. This implies

$\log\mathop{\mathbb{E}\/}_{q(xym)}\bigg{[}\bigg{|}\mathop{\mathbb{E}\/}_{q(xy|m)}\left[(-1)^{f}\right]\bigg{|}\bigg{]}\geq\mathop{\mathbb{E}\/}_{q(xym)}\bigg{[}\log\bigg{|}\mathop{\mathbb{E}\/}_{q(xy|m)}\left[(-1)^{f}\right]\bigg{|}\bigg{]}\geq-\frac{\delta\mathsf{M}_{I}(p,f)}{12I},$

thus giving Equation 56. Moreover,

$\mathsf{M}^{\mathsf{ext}}_{I}(p,f)\geq\mathop{\mathbb{E}\/}_{q(xym)}\bigg{[}\log\frac{q(xy|m)}{p(xy)}\bigg{]}=\mathop{\mathbb{E}\/}_{q(xym)}\bigg{[}\log\frac{q(xy|m)}{p(xy|m)}\bigg{]}+\mathop{\mathbb{E}\/}_{q(xym)}\bigg{[}\log\frac{p(xy|m)}{p(xy|m)}\bigg{]},$

and this implies Equation 55 since the first term in the sum is non-negative.
∎

##  7 Compressing marginal information

Here we prove Theorem 7. Let $p(xym)$ be a protocol distribution such that
$p(xy)=\mu(xy)$, and $\mathsf{M}_{I}(p,f)=\alpha\cdot I$. Let $q(xym)$ be a
rectangular distribution that realizes $\mathsf{M}_{I}(p,f)$. For a large
constant $K$, let $\mathsf{M}=\mathsf{M}_{I}(p,f)+KI$. Since
$\mathsf{M}(p,f)\geq 0$, we have $\mathsf{M}\geq KI$. Let $g_{1},g_{2}$ be as
in Equation 43.

Let $\varepsilon$ be a parameter such that
$\varepsilon\gg(2^{11\mathsf{M}/I}\sqrt{C\cdot\mathsf{M}})^{-1}$. We define a
protocol $\Gamma$ whose communication complexity is bounded by

$\displaystyle O(\mathsf{M}+\log
1/\varepsilon+2^{7\mathsf{M}/I}\cdot\sqrt{C\mathsf{M}}\cdot\log(C/\varepsilon)).$

Using the assumption that $\mathsf{M}_{I}(p,f)\leq\alpha I$ we see that
$\mathsf{M}\leq\Delta_{1}\cdot I$ and $\log
1/\varepsilon\leq\Delta_{2}\cdot\log(CI)$, where $\Delta_{1},\Delta_{2}$ only
depend on $\alpha$. This implies the bound on the communication in the
theorem.

Here is a description of $\Gamma$:

  1. 1.

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

  2. 2.

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

  3. 3.

Alice and Bob compute $m^{B}$, $m^{A}$ by setting

$\displaystyle m^{A}_{i}$ $\displaystyle=\begin{cases}1&\text{if $\rho_{i}\leq
p(m_{i}=1|xm^{A}_{<i})$,}\\\ 0&\text{otherwise.}\end{cases}$ (57)
$\displaystyle m^{B}_{i}$ $\displaystyle=\begin{cases}1&\text{if $\rho_{i}\leq
p(m_{i}=1|ym^{B}_{<i})$,}\\\ 0&\text{otherwise.}\end{cases},$ (58)

for $i=2,\dotsc,C$.

  4. 4.

Run $\tau$ from Lemma 25 to find the smallest $j$ with $m^{A}_{j}\neq
m^{B}_{j}$. If $j$ is even, Alice flips the value of $m^{A}_{j}$ to
$1-m^{A}_{j}$ and recomputes $m^{A}_{i}$ for $i=j+1,\dotsc,C$ using Equation
57. If $j$ is odd, Bob flips the value of $m^{B}_{j}$ to $1-m^{B}_{j}$ and
recomputes $m^{B}_{i}$ for $i=j+1,\dotsc,C$ using Equation 58. The players
repeat this process at most $2^{7\mathsf{M}/I}\sqrt{C\mathsf{M}}$ times. If by
this point $\tau$ reports that $m^{A}\neq m^{B}$, the players abort.
Otherwise, they continue. Let $\langle m^{A}\rangle$, $\langle m^{B}\rangle$
denote the final values of $m^{A},m^{B}$ after this step. The communication
complexity of this step is at most
$O(2^{7\mathsf{M}/I}\cdot\sqrt{C\mathsf{M}}\cdot\log(C/\varepsilon))$.

  5. 5.

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

  6. 6.

If there is a unique integer $z$ such that

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

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

Let $\Gamma$ denote the joint distribution of the inputs and transcript of the
above protocol. In order to analyze the protocol, define $m$ by setting
$m_{0}=m_{0}^{A}=m_{0}^{B}$, $m_{1}=m^{A}_{1}$, and setting

$\displaystyle m_{i}$ $\displaystyle=\begin{cases}1&\text{if $\rho_{i}\leq
p(m_{i}=1|xm_{<i})$,}\\\ 0&\text{otherwise}\end{cases},$

when $i>1$ is even, and setting

$\displaystyle m_{i}$ $\displaystyle=\begin{cases}1&\text{if $\rho_{i}\leq
p(m_{i}=1|ym_{<i})$,}\\\ 0&\text{otherwise}\end{cases},$

when $i>1$ is odd. This definition ensures that

$\displaystyle\Gamma(xym)=p(xym).$

For $i=2,3,\dotsc,C$ define

$\displaystyle E_{i}$ $\displaystyle=\begin{cases}1&\text{if $\rho_{i}$ is in
between the numbers $p(m_{i}=1|xm_{<i})$ and $p(m_{i}=1|ym_{<i})$,}\\\
0&\text{otherwise.}\end{cases}$

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

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

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

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

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

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

We shall prove:

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

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

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

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

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

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

The event $\mathcal{G}\mathcal{E}^{c}$ implies that $\pi$ or $\tau$ made an
error, leaving Alice and Bob with strings that were not equal in some step.
The probability that this happens is at most

$O(\varepsilon\cdot(1+2^{7\mathsf{M}/I}\sqrt{C\cdot\mathsf{M}}))\leq
2^{-4\mathsf{M}/I},$

by our choice of $\varepsilon$. Finally,
$\Gamma(S^{c}\mathcal{GEZ})\leq\Gamma(S^{c}\mathcal{EZ})\leq
O(\varepsilon\mathsf{M}/I)$, since if $S^{c}\mathcal{GEZ}$ happens then there
must have been a hash collision, which happens with probability at most
$O(\varepsilon\mathsf{M}/I)$. This implies Equation 62.

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

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

For $xym\in S$,

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

where the first equality follows from the fact that

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

by the definition of $S$. Therefore,

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

where in the last line, we used 33.

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

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

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

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

For all $xym\in S$,

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

where the last line follows by Equation 65.

Given Equation 66, to complete the proof of Equation 61, it will be enough to
prove that $\Gamma(\mathcal{E}|QS\mathcal{Z})\geq 1/2$. We shall prove that

$\displaystyle\Gamma(\mathcal{E}^{c}|QS\mathcal{Z})$
$\displaystyle\leq\Gamma(R^{c}|QSZ)+\Gamma\bigg{(}\mathcal{E}^{c}\bigg{|}QS\mathcal{Z}R,\sum_{i=2}^{C}E_{i}\leq
2^{7\mathsf{M}/I}\cdot\sqrt{C\mathsf{M}}\bigg{)}+\Gamma\bigg{(}\sum_{i=2}^{C}E_{i}>2^{7\mathsf{M}/I}\cdot\sqrt{C\mathsf{M}}\Big{|}QS\mathcal{Z}\bigg{)}$
$\displaystyle\leq O(2^{-\mathsf{M}/I}).$ (68)

By Equation 67 and 33,

$\displaystyle\Gamma(R^{c}|QS\mathcal{Z})\leq
q(R^{c}|S)(1+O(\varepsilon\mathsf{M}/I))\leq 2^{-\mathsf{M}/I+3}.$ (69)

Given $QS\mathcal{Z}R$ and the event $\sum_{i=2}^{C}E_{i}\leq
2^{7\mathsf{M}/I}\cdot\sqrt{C\mathsf{M}}$, the event $\mathcal{E}^{c}$ can
happen only if $\tau$ or $\pi$ make an error that leaves Alice and Bob with
inconsistent messages, or if $\pi$ aborts. We claim that the probability that
$\pi$ makes an error or aborts is at most $2\varepsilon$. This is because
every $xym\in R$ satisfies $p(m_{1}|xm_{0})\leq 2^{6\mathsf{M}}\cdot
p(m_{1}|m_{0}y)$, so we can apply Lemma 24. Moreover, the probability that
$\tau$ ever makes an error is at most $O(\varepsilon
2^{7\mathsf{M}/I}\sqrt{C\mathsf{M}})$ by a union bound. So, we conclude that

$\displaystyle\Gamma\bigg{(}\mathcal{E}^{c}\bigg{|}QS\mathcal{Z}R,\sum_{i=2}^{C}E_{i}\leq
2^{7\mathsf{M}/I}\cdot\sqrt{C\mathsf{M}}\bigg{)}$ $\displaystyle\leq
O(\varepsilon 2^{7\mathsf{M}/I}\sqrt{C\mathsf{M}}).$ (70)

We shall prove at the end of this section that

$\displaystyle\Gamma\bigg{(}\sum_{i=2}^{C}E_{i}>2^{7\mathsf{M}/I}\cdot\sqrt{C\mathsf{M}}\Big{|}QS\mathcal{Z}\bigg{)}$
$\displaystyle<O(2^{-\mathsf{M}/I}).$ (71)

Equations 69, 70 and 71 together prove Equation 68, and so conclude the proof
of Equation 61. Next, we prove Equation 60. Since $|\mathcal{A}(xym)|\leq 1$,
we have

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

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

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

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

It only remains to prove Equation 71. Define the function

$\displaystyle t(xym)=\begin{cases}\min\\{j:q(xym_{\leq
j})<2^{-3\mathsf{M}/I}\cdot p(xym_{\leq j})\\}&\text{if such $j$ exists,}\\\
\bot&\text{otherwise.}\end{cases}$

Note that the function $t(xym)$ is determined by $xym_{\leq t(xym)}$.

We have

$\displaystyle\Gamma\bigg{(}\sum_{i=2}^{C}E_{i}>2^{7\mathsf{M}/I}\cdot\sqrt{C\mathsf{M}}\Big{|}QS\mathcal{Z}\bigg{)}$
$\displaystyle\leq\Gamma(t\neq\bot|QSZ)+\Gamma\bigg{(}\sum_{i=2}^{C}E_{i}>2^{7\mathsf{M}/I}\cdot\sqrt{C\mathsf{M}}\Big{|}QS\mathcal{Z},t=\bot\bigg{)},$

so let us bound each of these terms.

$\displaystyle\Gamma(t\neq\bot|QSZ)$ $\displaystyle\leq
q(t\neq\bot|S)\cdot(1+O(\varepsilon\mathsf{M}/I))$ (by Equation 67)
$\displaystyle\leq
q(t\neq\bot)\cdot(1+O(2^{-3\mathsf{M}/I}))\cdot(1+O(\varepsilon\mathsf{M}/I)),$
(by 33)

and

$\displaystyle q(t\neq\bot)=\sum_{j=0}^{C}q(t=j)$
$\displaystyle=\sum_{j=0}^{C}\sum_{\begin{subarray}{c}xym_{\leq j}\\\
t(xym)=j\end{subarray}}q(xym_{\leq j})$
$\displaystyle<2^{-3\mathsf{M}/I}\cdot\sum_{j=0}^{C}\sum_{\begin{subarray}{c}xym_{\leq
j}\\\ t(xym)=j\end{subarray}}p(xym_{\leq j})=2^{-3\mathsf{M}/I}\cdot
p(t\neq\bot)\leq 2^{-3\mathsf{M}/I},$

so we conclude that

$\displaystyle\Gamma(t\neq\bot|QS\mathcal{Z})$ $\displaystyle\leq
O(2^{-3\mathsf{M}/I}).$ (72)

Next, we show that

$\displaystyle\Gamma\bigg{(}\sum_{i=2}^{C}E_{i}>2^{7\mathsf{M}/I}\cdot\sqrt{C\mathsf{M}}\Big{|}QS\mathcal{Z},t=\bot\bigg{)}<O(2^{-\mathsf{M}/I}),$

which would complete the proof of Equation 71. This follows from Markov’s
inequality and the bound

$\displaystyle\mathop{\mathbb{E}\/}_{\Gamma}\bigg{[}\sum_{i=2}^{C}E_{i}\Big{|}QS\mathcal{Z},t=\bot\bigg{]}\leq
O(2^{6\mathsf{M}/I}\sqrt{C\mathsf{M}}),$ (73)

which we prove next. We have:

$\displaystyle\mathop{\mathbb{E}\/}_{\Gamma}\bigg{[}\sum_{i=2}^{C}E_{i}\Big{|}QS\mathcal{Z},t=\bot\bigg{]}$
$\displaystyle=\sum_{i=2}^{C}\frac{\Gamma(E_{i}=1,QS\mathcal{Z},t=\bot)}{\Gamma(QS\mathcal{Z},t=\bot)}$
(74) $\displaystyle\leq
O(2^{3\mathsf{M}/I})\cdot\sum_{i=2}^{C}\Gamma(E_{i}=1,t=\bot).$ (by Equations
66 and 72)

Moreover,

$\displaystyle\Gamma(E_{i}=1,t=\bot)$
$\displaystyle=\sum_{xym_{<i}}\Gamma(xym_{<i})\cdot\Gamma(E_{i}=1|xym_{<i})\cdot\Gamma(t=\bot|E_{i}=1,xym_{<i})$
$\displaystyle=\sum_{xym_{<i}}p(xym_{<i})\cdot\|p(m_{i}|xm_{<i})-p(m_{i}|ym_{<i})\|_{1}\cdot\Gamma(t=\bot|E_{i}=1,xym_{<i})$
$\displaystyle\leq
O(2^{3\mathsf{M}/I})\cdot\sum_{xym_{<i}}q(xym_{<i})\cdot\|p(m_{i}|xm_{<i})-p(m_{i}|ym_{<i})\|_{1}$
(75)

Therefore,

$\displaystyle\mathop{\mathbb{E}\/}_{\Gamma}\bigg{[}\sum_{i=2}^{C}E_{i}\Big{|}QS\mathcal{Z},t=\bot\bigg{]}$
$\displaystyle\leq
O(2^{3\mathsf{M}/I})\cdot\mathop{\mathbb{E}\/}_{q(xym)}\bigg{[}\sum_{i=2}^{C}\|p(m_{i}|xm_{<i})-p(m_{i}|ym_{<i})\|_{1}\bigg{]}$
$\displaystyle\leq O(2^{3\mathsf{M}/I}\cdot\sqrt{C\mathsf{M}}),$

by Equation 52, which completes the proof of Equation 73.

##  8 Smoothing protocols

A smooth protocol is a protocol where each message bit is close to being
uniformly distributed:

######  Definition 39.

Given a protocol distribution $p(xym)$ with $C$ messages satisfying
$m_{2},\dotsc,m_{C}\in\\{0,1\\}$, we say that the distribution is
$\beta$-smooth if for all $i>1$, $|p(m_{i}|xym_{<i})-1/2|\leq\beta$.

Here we prove the following theorem:

######  Theorem 40.

For every Boolean function $f$, every protocol distribution $p(xym)$ with $C$
messages satisfying $m_{2},\dotsc,m_{C}\in\\{0,1\\}$, and every $\beta>0$,
assuming that $\mathsf{M}^{\mathsf{ext}}_{I}(p,f)$ is finite, there is a
$\beta$-smooth protocol $p^{\prime}(xym^{\prime})$ with $C^{\prime}\leq
O(C\cdot\log(IC)/\beta^{2})$ messages such that
$\mathsf{M}^{\mathsf{ext}}_{I}(p^{\prime},f)\leq\mathsf{M}^{\mathsf{ext}}_{I}(p,f)+1$,
and $m^{\prime}_{2},\dotsc,m^{\prime}_{C^{\prime}}\in\\{0,1\\}$.

###### Proof.

Let $q(xym)$ be a rectangular distribution realizing
$\mathsf{M}^{\mathsf{ext}}_{I}(p,f)$. Let $L>1$ be a large odd number to be
determined. Define the pair of distributions
$q^{\prime}(xym^{\prime}),p^{\prime}(xym^{\prime})$ as follows. Let
$m^{\prime}_{0},m^{\prime}_{1}$ have the same support as $m_{0},m_{1}$, and
let $m^{\prime}_{2},\dotsc,m^{\prime}_{C}\in\\{0,1\\}^{L}$. In
$p^{\prime},q^{\prime}$, the $i$’th message will correspond to
$m^{\prime}_{i}$.

For $a\in\\{0,1\\}$, define the following distributions supported on
$\\{0,1\\}^{L}$:

$\displaystyle s_{a}(r)$
$\displaystyle=\prod_{j=1}^{L}\frac{1}{2}+(-1)^{a+r_{j}}\cdot\beta$
$\displaystyle t_{a}(r)$
$\displaystyle=s_{a}\Big{(}r\big{|}(-1)^{a}\cdot\sum_{j=1}^{L}(-1)^{r_{j}}\geq
0\Big{)}$ $\displaystyle t^{\prime}_{a}(r)$
$\displaystyle=s_{a}\Big{(}r\big{|}(-1)^{a}\cdot\sum_{j=1}^{L}(-1)^{r_{j}}<0\Big{)}.$

In words, $s_{a}(r)$ is the distribution of $L$ independent bits that are
biased towards being equal to $a$, $t_{a}(r)$ is this distribution conditioned
on the event that the majority of the bits is equal to $a$ and
$t^{\prime}_{a}(r)$ is the distribution conditioned on the event that the
majority is not $a$.

Now we define a protocol distribution $p^{\prime}(xym^{\prime})$ and a
rectangular distribution $q^{\prime}(xym^{\prime})$. Given $m^{\prime}$, let
$D(m^{\prime}_{i})$ denote the unique string satisfying
$D(m^{\prime}_{0},m^{\prime}_{1})=(m^{\prime}_{0},m^{\prime}_{1})$, and

$(-1)^{D(m^{\prime}_{i})}\cdot\sum_{j=1}^{L}(-1)^{m^{\prime}_{i,j}}\geq 0.$

In other words, $D$ decodes each block of $L$ bits by taking the majority.
Below we abuse notation and write $D(m)=D(m_{0}),D(m_{1}),\dotsc,D(m_{C})$.

Define

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

The definition ensures that $q^{\prime}(xym^{\prime})$ is rectangular, and
that conditioned on $D(m^{\prime})$, $xy$ is independent of $m^{\prime}$.
Define the distribution $p^{\prime}(xymm^{\prime})$ as follows:

$\displaystyle p^{\prime}(xym^{\prime}_{0}m^{\prime}_{1})$
$\displaystyle=p(xym^{\prime}_{0}m^{\prime}_{1}),$

and for $i>1$,

$\displaystyle p^{\prime}(m_{i}m^{\prime}_{i}|xym_{<i}m^{\prime}_{<i})$
$\displaystyle=p(m_{i}|xy,m_{<i}=D(m^{\prime})_{<i})\cdot
s_{m_{i}}(m^{\prime}_{i})$

In words, in the protocol $p^{\prime}(xym^{\prime})$, the parties privately
sample each message bit $m_{i}$ according to the protocol distribution $p$.
However, instead of sending this sampled bit, they send $m^{\prime}_{i}$
sampled according to $s_{m_{i}}(m^{\prime}_{i})$. After this transmission,
they continue the protocol using $D(m^{\prime})_{<i}$. Strictly speaking, in
order to ensure that the new protocol is a protocol distribution, we require
that all the odd bits are transmitted by Alice and all even bits are sent by
Bob. This can be easily achieved by inserting random bits into the transcript,
but we leave out the details here.

There is some small chance that for $i>1$, $D(m^{\prime})_{i}\neq m_{i}$, but
by the Chernoff bound,

$p^{\prime}(D(m^{\prime})_{i}\neq m_{i})\leq\exp(-\Omega(\beta^{2}L)).$

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

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

For any $xyD(m^{\prime})$ such that $q(xyD(m^{\prime}))>0$, we can bound

$\displaystyle\frac{q(xyD(m^{\prime}))}{p^{\prime}(xyD(m^{\prime}))}$
$\displaystyle=\frac{q(xyD(m^{\prime}))}{p(xyD(m^{\prime}))}\cdot\prod_{i=2}^{C}\frac{p(D(m^{\prime})_{i}|xyD(m^{\prime})_{<i})}{p^{\prime}(D(m^{\prime})_{i}|xyD(m^{\prime})_{<i})}$
$\displaystyle\leq\frac{q(xyD(m^{\prime}))}{p(xyD(m^{\prime}))}\cdot\prod_{i=2}^{C}\frac{1}{1-\exp(-\Omega(\beta^{2}L))},$

where we assumed that $p(xyD(m^{\prime}))>0$; if $p(xyD(m^{\prime}))=0$ then
$q(xyD(m^{\prime}))=0$ for otherwise the marginal information cost would be
unbounded. Next,