$V_{\textnormal{\tiny{cover}}}$ and that is the task of the following
algorithm.

######  Algorithm 3.

For implementing Line (2d) of 2 in each batch $i\in[\log\log{n}]$. 1.
Partition the set $U_{i}$ into $b=\log{k_{i}}$ groups based on geometrically
increasing sizes, namely, for every $j\in[b]$, $U_{i,j}$ contains the next
$2^{j}$ elements of $U_{i}$ in the order of permutation $\sigma$:202020The
last group $b$ may contain less than $2^{b}$ elements, as it only has all the
remaining elements of $U_{i}$.
$U_{i,j}=\left\\{u_{2^{j}-1},u_{2^{i}},\ldots,u_{2^{j+1}-2}\right\\}.$ 2. For
every $v\in V$ and $j\in[b]$, define the vector
$\phi(v,j)\in\left\\{0,1\right\\}^{V}$ as the indicator vector of $N(v)\cap
U_{i,j}\cap V_{\textnormal{\tiny{mis}}}$. Note that by the end of Line (2c) of
2, the set $V_{\textnormal{\tiny{mis}}}\cap U_{i,j}$ is known and each update
$(u,v)$ to the dynamic stream for edges of the input graph $G$ can be used to
also update the vectors $\phi(u,j)$ and $\phi(v,j)$ for all $j\in[b]$. 3. Let
$q:=200\ln{n}$ and for every $v\in V$ and $j\in[b]$, run a randomized
$q$-sparse recovery algorithm of Proposition 3.6 on $\phi(v,j)$ and test if
$\phi(v,j)$ is $q$-sparse or not, using $\delta=1/n^{200}$. 4. Let $j\in[b]$
be the smallest index such that Proposition 3.6 declares
$0<\|\phi(v,j)\|_{0}\leqslant q$ and returns $\phi(v,j)$; let $u\in
V_{\textnormal{\tiny{mis}}}$ be the vertex with the minimum $t(u)$ in the
support of $\phi(v,j)$. Return $(u,t(u))$ as the choice for the vertex $v$ in
Line (2d) of 2 (if no such $j$ is found for $v$, return no $u$ exists for
$v$).

######  Lemma 4.10.

With high probability, 3 finds the time-stamps in Line (2d) of 2 and can be
implemented in $O(n\log^{3}{n})$ space.

###### Proof.

We will show that for any vertex $v\in V\setminus
V_{\textnormal{\tiny{mis}}}$, 3 finds the required time-stamp $t(v)$ with high
probability.

Consider the smallest index $j^{\star}\in[b]$ where
$\|\phi(v,j^{\star})\|_{0}>0$; if no such $j^{\star}$ exists then $v$ is not a
neighbor to any vertex in $V_{\textnormal{\tiny{mis}}}$ and thus will not be
added to $V_{\textnormal{\tiny{cover}}}$. Otherwise, the neighbor $u$ of $v$
in $V_{\textnormal{\tiny{mis}}}$ with the smallest value of $t(u)$ belongs to
$U_{i,j^{\star}}$. Thus, returning such $u$ is the correct answer.

Let us see how the algorithm performs for any $j\in[b]$, and enumerate the
sources of error.

  1. $(i)$

For any $j<j^{\star}$, we know that $\|\phi(v,j)\|_{0}=0$, but the randomized
sparse-recovery may return that $\|\phi(v,j)\|_{0}>q$ with probability at most
$\delta$.

  2. $(ii)$

For $j=j^{\star}$, it may be the case that $\|\phi(v,j)\|_{0}>q$ or if
$\|\phi(v,j)\|_{0}\leqslant q$, but randomized sparse-recovery returns
otherwise.

Firstly, let us condition on the fact that randomized sparse-recovery performs
correctly and retrieves $\phi(v,j)$ for all $v\in V\setminus
V_{\textnormal{\tiny{mis}}}$ and $j\in[b]$. Using union bound over all
vertices and $j\in[b]$, we get that this event happens with probability at
least $1-n^{-198}$ for the choice of $\delta=n^{-200}$.

Now, we only need to bound the probability that the case
$\|\phi(v,j^{\star})_{0}\|>q$ happens. We do so using the following
intermediate claim.

######  Claim 4.11.

For any $j>1$ and any vertex $v\in V\setminus V_{\textnormal{\tiny{mis}}}$, if
$\|\phi(v,j-1)\|_{0}=0$, then $\|\phi(v,j)\|_{0}\leqslant q$ with high
probability.

###### Proof.

Let us fix the vertices $U_{i}$ which are picked to be in $\sigma$, but not
the order in which they are processed, i.e., we know the $k_{i}$ vertices that
belong to $U_{i}$ but not the vertex groupings of $U_{i,j}$ for $j\in[b]$. We
define some useful notation to prove this claim.

$\displaystyle G_{i,j}$ $\displaystyle:\text{the graph
$G[U_{i}\setminus(V_{\textnormal{\tiny{cover}}}\cup
V_{\textnormal{\tiny{mis}}})]$ at the beginning of sampling $U_{i,j}$, where,
$V_{\textnormal{\tiny{mis}}}\cup V_{\textnormal{\tiny{cover}}}$ }$
$\displaystyle\text{\hskip 11.38109ptinclude all the vertices in $U_{i}$
settled by all the vertices in $\sigma$ till $U_{i,j-1}$};$ $\displaystyle
d_{j}(v)$ $\displaystyle:\text{the degree of $v$ in $G_{i,j}$};$
$\displaystyle k_{i,j}$
$\displaystyle:k_{i}-(2^{1}+2^{2}+\ldots+2^{j-1}),\text{ the number of
vertices left in $U_{i}$ after}$ $U_{i,1},U_{i,2},\ldots,U_{i,j-1}$ are
sampled

For any $j<b$ with $2^{j}\leqslant k_{i,j}$ (group $j$ is not the last group),
we can think of picking $U_{i,j}$ as sampling $2^{j}$ vertices from the
$k_{i,j}$ vertices of $U_{i}\setminus(U_{i,1}\cup U_{i,2}\cup\ldots\cup
U_{i,j-1})$ without replacement. Each vertex is picked in $U_{i,j}$ with
probability $p_{j}$, where,

$p_{j}:=2^{j}/k_{i,j}.$ (13)

Suppose $d_{j}(v)<100\ln{n}/p_{j}$. Then, in expectation, we know that there
are at most $100\ln n$ neighbors of $v$ in
$G\setminus(V_{\textnormal{\tiny{mis}}}\cup V_{\textnormal{\tiny{cover}}})$.
We use Chernoff bound for negatively correlated random variables in
Proposition 3.2 (because of sampling without replacement) to argue that with
high probability, we cannot have more than $200\ln{n}=q$ neighbors of $v$ in
$G\setminus(V_{\textnormal{\tiny{mis}}}\cup V_{\textnormal{\tiny{cover}}})$
that are sampled in $U_{i,j}$; even if all of those neighbors join
$V_{\textnormal{\tiny{mis}}}$, we will still have that sparsity of $\phi(v,j)$
is at most $q$ as desired.

Now we need to argue the case when $d_{j}(v)\geqslant 100\ln{n}/p_{j}$. This
implies that,

$\displaystyle d_{j}(v)$ $\displaystyle\geqslant 100\ln{n}/p_{j}$ (as the set
$V_{\textnormal{\tiny{mis}}}\cup V_{\textnormal{\tiny{cover}}}$ only grows)
$\displaystyle=100\ln{n}\cdot\frac{k_{i,j}}{2^{j}}$ (by value of $p_{j}$ in Eq
13) $\displaystyle=50\ln{n}\cdot\frac{k_{i,j}}{2^{j-1}}$
$\displaystyle=50\ln{n}\cdot\frac{1}{p_{j-1}}\cdot\frac{k_{i,j}}{k_{i,j-1}}.$
(given that $p_{j-1}=2^{j-1}/k_{i,j-1}$)
$\displaystyle=50\ln{n}\cdot\frac{1}{p_{j-1}}\cdot\frac{k_{i,j-1}-2^{j-1}}{k_{i,j-1}}$
(by definition of $k_{i,j}$)
$\displaystyle=50\ln{n}\cdot\frac{1}{p_{j-1}}\cdot(1-p_{j-1})$
$\displaystyle\geqslant 25\ln{n}\cdot(1/p_{j-1}).$ ($k_{i,j-1}\geqslant
2^{j}+2^{j-1}\geqslant 2\cdot 2^{j-1}$, we get $p_{j-1}\leqslant 1/2$)

When group $j$ is the last group with $2^{j}\geqslant k_{i,j}$ (here
$p_{j}=1$), we have,

$d_{j}(v)\geqslant 100\ln{n}\geqslant 25\ln{n}\cdot(1/p_{j-1}),$

where we have used that $k_{i,j-1}<2^{j-1}+2^{j}<4\cdot 2^{j-1}$, and
$p_{j-1}\geqslant 1/4$.

We have argued that $d_{j}(v)\geqslant 25\ln{n}/p_{j-1}$ in all cases. Among
these $d_{j}(v)$ vertices, none of them are sampled in $U_{i,j-1}$ as $v$ is
not settled in $U_{i,j}$. However, in expectation, $25\ln{n}$ of these
vertices must have been sampled in $U_{i,j-1}$. We use the same argument as in
Lemma 4.8 to say that at least one of these $d_{j}(v)$ vertices will be
sampled in $U_{i,j-1}$ and $v$ will have a neighbor in
$V_{\textnormal{\tiny{mis}}}$ already inside $U_{i,j-1}$, with high
probability. This contradicts our assumption that $\|\phi(v,j-1)\|_{0}=0$.

Thus, in this case $j$ cannot be the first index with non-empty support in
$\phi(v,j)$.  ${}_{\textnormal{~{}~{}\lx@cref{creftypecap~refnum}{clm:finding-
label-min}}}$

To finalize the proof, we have that if $j^{\star}=1$, $U_{i,1}$ has only 2
vertices and $\phi(v,1)$ is $2$-sparse; for any $j^{\star}>1$, we use Claim
4.11 to argue that for any vertex $v$, $\phi(v,j^{\star})$ is $q$-sparse with
high probability. This proves the correctness of the algorithm as argued
earlier.

We can now bound the space of the algorithm. For every $v\in V$, we are
maintaining $O(\log{n})$ randomized sparse-recovery algorithms, each for
recovering an $O(\log{n})$-sparse vector from a domain of size $\leqslant n$
and error probability $\delta=1/\mbox{\rm poly}(n)$; thus, by Proposition 3.6,
this needs $O(\log^{3}{n})$ space per vertex, and $O(n\log^{3}{n})$ space in
total, concluding the proof of Lemma 4.10.

#####  4.2.2 Finding a Large Matching from 2 via the Reduction of 1

2 allows us to recover the time stamps of all vertices in a single run of the
randomized greedy MIS algorithm in $O(\log\log{n})$ passes over a dynamic
stream. We now use this information alongside our reduction of approximate
matching to randomized greedy MIS in 1, to recover a large matching from the
input graph.

Let us first recall some notation about some variables in 1:

$\displaystyle G^{(t)}$ $\displaystyle:\text{the graph $G$ at iteration $t$};$
$\displaystyle\deg^{(t)}(v)$ $\displaystyle:\text{for each $v\in G^{(t)}$,
denotes the degree of $v$ in $G^{(t)}$};$ $\displaystyle x_{e}$
$\displaystyle:\text{the value given to edge $e$ in $x\in\mathbb{R}^{E}$ from
\lx@cref{creftypecap~refnum}{eq:random-order-1}}$ $\displaystyle y_{e}$
$\displaystyle:\text{the value given to edge $e$ in fractional matching
$y\in[0,1]^{E}$ from \lx@cref{creftypecap~refnum}{eq:final-apx-ye}}.$

As we have stated earlier, given the support of the fractional matching $y$
can be too large, we cannot hope to recover it explicitly. Instead, our goal
is to _sample_ the edges of the graph with probabilities proportional to their
$y$-values, and then use the sampled edges to find a large matching.
Specifically, for every $e\in E$, define:

$p_{e}:=\min(1,y_{e}\cdot 200\log n).$ (14)

We would like to sample each edge of the graph with probability $p_{e}$. The
challenge however is that we will not be able to actually recover the values
of $y$ (or even $x$) explicitly and learn $p_{e}$’s, and thus need to use a
“proxy” for them algorithmically.

To start with, we have the time stamps of all the vertices. Let us show that
this also gives us the degrees of all the vertices at the time in which they
are settled.

######  Observation 4.12.

Given the time stamps $t(v)$ for all $v\in V$, using one pass and
$O(n\log{n})$ space, we can find $\deg^{(t(v))}(v)$ for all vertices $v\in V$.

###### Proof.

For any vertex $v$, $\deg^{(t(v))}(v)$ only includes the edges of $v$ to
vertices $w\in V$ which have $t(w)\geqslant t(v)$. We know the labels of all
vertices explicitly, so it is easy to count the total number of edges from $v$
to vertices with labels after $v$ using a counter per vertex.

Equipped with 4.12, we can assume we also have the remaining degree of every
vertex $v\in V$ at the time it is settled. This fixes the value $x$ will
assign to the edges of $v$. The problem however is that we still do not have
sufficient information to perform the check in Line (2c) of 1 to know which
incident edges of $v$ receive a non-zero fractional matching, i.e., which
edges $(v,w)$ satisfy $\deg(w)\leqslant\deg(v)$; this is because for this
check, we need to know the degree of $w$ at the time $v$ is being settled not
$w$ itself.

We side step this issue in the following by defining an intermediate
assignment $z\in\mathbb{R}^{E}$ which we can explicitly find for any pair of
vertices. To formally define the vector $z$, we describe the notion of
assigning a vertex pair to one of the vertices.

######  Definition 4.13 (Assignment of vertex pairs to vertices).

For any pair of vertices $u,v$, we say the pair $u,v$ is assigned to vertex
$u$, denoted by $\textnormal{{vert}}(u,v)$, iff: $(i)$ $u$ is settled before
vertex $v$, i.e., $t(u)<t(v)$, or else, $(ii)$ $u,v$ are removed at the same
time with $t(u)=t(v)$ and $u\in V_{\textnormal{\tiny{cover}}}$ while $v\in
V_{\textnormal{\tiny{mis}}}$, or else, $(iii)$ $t(u)=t(v)$, $u,v\in
V_{\textnormal{\tiny{cover}}}$, and
$\deg^{(t(u))}(u)\geqslant\deg^{(t(v))}(v)$ (breaking the ties between $u$ and
$v$ in case of the equality consistently, say, based on whichever appear in
$\sigma$ first).

Note that by 4.13, every pair $u,v$ of vertices, regardless of whether or not
is an edge, is assigned to one of its endpoints. We then define $z_{uv}$ for a
pair $u,v\in V$ as,

$z_{uv}:=\frac{200\log
n}{\deg^{(t(\textnormal{{vert}}(u,v)))}(\textnormal{{vert}}(u,v))};$ (15)

that is $z_{uv}$ is proportional to the inverse of the degree of its assigned
vertex, at the time this assigned vertex was settled. When vertices $u,v$ do
contain an edge $e=(u,v)$ in the input graph, we use $z_{e}$ and
$\textnormal{{vert}}(e)$ also to denote $z_{uv}$ and
$\textnormal{{vert}}(u,v)$ interchangeably.

We observe that for any vertex pair $u,v$, the value of $z_{uv}$ can be found
easily.

######  Observation 4.14.

For any vertex pair $u,v$, the value of $z_{uv}$ can be determined given the
information collected by the algorithm.

###### Proof.

The only information required to find $\textnormal{{vert}}(e)$ is the time
stamps, the sets $V_{\textnormal{\tiny{cover}}}$ and
$V_{\textnormal{\tiny{mis}}}$, and the degrees at the time of removal, and
lastly the permutation $\sigma$, all of which is stored in the memory
explicitly (using Lemma 4.10 and 4.12). Thus, we can find for each vertex pair
what $\textnormal{{vert}}(u,v)$ is, and then, determining $z_{uv}$ is trivial.

The following claims shows the relevance of $z$-values for us.

######  Claim 4.15.

For every edge $e\in E$, $p_{e}\leqslant z_{e}$ where $p_{e}\in[0,1]$ is from
Eq 14.

###### Proof.

It is sufficient to show that $x_{e}\cdot 200\log n\leqslant z_{e}$ given that
$y_{e}\leqslant x_{e}$ always ($y$ is obtained from $x$ by reducing some of
its values) and by the definition of $p_{e}$ based on $y_{e}$ in Eq 14.

For any edge $e=(u,v)\in E$, the value of $x_{e}$ is updated in at most one
iteration of the loop in Line (2c) of 1, i.e., the iteration where either of
$u$ or $v$ are settled. We will argue that

$x_{e}\leqslant\frac{\beta}{\deg^{(t(\textnormal{{vert}}(e)))}(\textnormal{{vert}}(e))}.$

We have multiple cases to consider:

  * •

When $v$ is settled (strictly) before $u$, that is $t(v)<t(u)$, we have that
$\textnormal{{vert}}(e)=v$ from Line $(i)$ of 4.13. We know that $x_{e}$ is
set as $\beta/\deg^{(t(v))}(v)$ if
$\deg^{(t(v))}(u)\leqslant\deg^{(t(v))}(v)$, otherwise $x_{e}$ is set as zero.
In either case, $x_{e}$ is less than
$\beta/\deg^{(t(\textnormal{{vert}}(e)))}(\textnormal{{vert}}(e))$. This is
similarly true when $u$ is settled (strictly) before $v$.

  * •

When $v$ and $u$ are settled at the same time, with $t(u)=t(v)$, and if $u$
goes to $V_{\textnormal{\tiny{mis}}}$ at this iteration, then $v\in
V_{\textnormal{\tiny{cover}}}$, and $x_{e}$ is again updated as
$\beta/\deg^{(t(v))}(v)$. We have that $\textnormal{{vert}}(e)=v$ by Line
$(ii)$ of 4.13 and can apply the above reasoning.

  * •

When both $u,v$ go to $V_{\textnormal{\tiny{cover}}}$ and have the same
timestamps, the value of $x_{e}$ is set as $\beta/\deg^{(t(v))}(v)$ if $v$ is
the higher degree vertex among $u,v$ at time $t(u)=t(v)$. Again, we have that
$\textnormal{{vert}}(e)=v$ by Line $(iii)$ of 4.13 and can apply the above
reasoning.

The claim follows by observing that,

$x_{e}\cdot 200\cdot\log n\leqslant\frac{\beta\cdot 200\cdot\log
n}{\deg^{(t(\textnormal{{vert}}(e)))}(\textnormal{{vert}}(e))}\leqslant\frac{200\cdot\log
n}{\deg^{(t(\textnormal{{vert}}(e)))}(\textnormal{{vert}}(e))}=z_{e},$

where we have used that $\beta<1$.

Given Claim 4.15, for algorithmic purposes, we can instead sample the edges
with probability proportional to $z$-values, which we _can_ compute. We now
need to check this can be done efficiently in dynamic streams (and that the
size of the sampled edges are not too large, given $z$ is _not_ a fractional
matching). Our sampling is done in two steps: we first sample _all_ pairs
$u,v$ based on their value $z_{u,v}$ to obtain a vector
$\phi_{z}\in\mathbb{R}^{{{V}\choose{2}}}$ and then maintain a sparse-recovery
algorithm over $\phi_{z}$ to recover the actual edges inside this sample.
Furthermore, we need to sample $\phi_{z}$ itself with _limited independence
hash functions_ (defined in Section 3.1) and work with $\phi_{z}$ _implicitly_
given that its size is larger than the allowed space. We now formalize this:

###### Sampling process.

Let $\kappa:=200\log{n}$ and sample a $\kappa$-wise independent hash function
from Definition 3.3 with domain of the set of vertex pairs and the range of
$[0,1]$212121 For the simplicity of exposition, we let the range of the hash
function to be the interval $[0,1]$. For algorithmic purposes, one needs to
further discretize this range to integers. Specifically, use the range as
$\\{1,2,\ldots,\mbox{\rm poly}(n)\\}$ for some large polynomial in $n$ and
consider a mapping of $[0,1]$ to this range in a standard way. The
distribution when sampling from the hash family with this large discrete
domain varies from the range $[0,1]$ by at most $1/\mbox{\rm poly}(n)$ in
total variation distance, and this negligible difference can be added to the
probability of error of the algorithm.:

$h:\binom{n}{2}\rightarrow[0,1].$ (16)

Let $\Phi_{z}\subseteq{{V}\choose{2}}$ be the set of pairs such that
$h(u,v)\leqslant\min(1,z_{u,v})$ and
$\phi_{z}\in\left\\{0,1\right\\}^{\Phi_{z}}$ be the incidence vector of
$E_{z}:=E\cap\Phi_{z}$. This way, the elements in the support of $\phi_{z}$
are obtained from $E$ by sampling each edge $e\in E$, using a $\kappa$-wise
independent hash function, with probability $z_{e}$.

We now analyze this sampling process. The size of $\Phi_{z}$ may still be too
large for us but we show that the total number of _actual edges_ sampled,
i.e., the support of $\phi_{z}$ will not be large and can be found and stored
explicitly by the algorithm.

######  Claim 4.16.

The set $E_{z}$ can be found and stored in $O(n\log^{2}n)$ space explicitly
with high probability.

###### Proof.

We will prove that size of $E_{z}$ is $O(n\log{n})$ with high probability
(over the randomness of $h$ alone). This will be sufficient to prove the claim
since we can implicitly maintain the set $\Phi_{z}$ using the hash function
$h$, which itself can be stored in $O(\kappa\cdot\log{n})=O(\log^{2}{n})$
space using Proposition 3.4 (see also Footnote 21); then, we will store a
randomized sparse-recovery of Proposition 3.6 for the vector $\phi_{z}$ and
each relevant update on the graph $G$ can be passed to this vector given the
implicit access to $\Phi_{z}$. This way, we can recover $E_{z}$, the support
of $\phi_{z}$, in $O(n\log^{2}{n})$ space with high probability.

It thus suffices to prove the bound on the size of $E_{z}$. For any vertex
$v\in V$, let $A(v)$ be the set of edges $e\in E$ that are assigned to $v$,
i.e., $\textnormal{{vert}}(e)=v$. We claim that $A(v)\cap E_{z}$ is of size
$O(\log{n})$ with high probability which implies the bound on $E_{z}$
immediately since the set $\left\\{A(v)\mid v\in V\right\\}$ covers all edges
of the graph.

Let us fix a vertex $v\in V$. Let $d_{v}=\deg^{(t(v))}(v)$ be the degree of
$v$ at the time it is settled. We argue that $\left|{A(v)}\right|\leqslant
d_{v}$. This is because any edge $e=(v,w)$ assigned to $v$ satisfies
$t(w)\geqslant t(v)$ and thus belongs to the graph at the time $v$ is settled.
If $d_{v}\leqslant 200\log{n}$, we are already done, so in the following we
assume $d_{v}>200\log{n}$.

For $e\in A(v)$, define the indicator random variable
$X_{e}\in\left\\{0,1\right\\}$ which is $1$ iff $e$ is sampled in $A_{z}$. By
Eq 15, we have
$\operatorname*{{\mathbb{E}}}\left[X_{e}\right]=200\log{n}/d_{v}$ and thus by
the argument above

$\operatorname*{{\mathbb{E}}}\left|{E_{z}\cap
A(v)}\right|=\left|{A(v)}\right|\cdot\frac{200\log{n}}{d_{v}}\leqslant
d_{v}\cdot\frac{200\log{n}}{d_{v}}=200\log{n}.$

Moreover, $\left\\{Z_{e}\right\\}_{e\in A(v)}$ are chosen via a $\kappa$-wise
independent hash function. Thus, by Proposition 3.5,

$\operatorname*{\textnormal{Pr}}\left(\left|{E_{z}\cap A(v)}\right|\geqslant
400\log{n}\right)\leqslant\exp\left(-\min\left(\frac{\kappa}{2},\frac{2}{3}\cdot
200\log{n}\right)\right)\leqslant n^{-100},$

by the choice of $\kappa=200\log{n}$. A union bound over all the vertices
concludes the proof.

We have proved that our sampling process does not violate the space constraint
and we can obtain the set $E_{z}$ as well. We now finalize the argument by
showing that $E_{z}$ contains a large matching in expectation by relating it
to the fractional matching $y$ of 1. This is a combination of the standard
fact that sampling a fractional matching leads to a large matching as well
(slightly modified to work even with limited-independence sampling), and a
rejection sampling argument in the analysis to relate sampling with
probability $z_{e}$ to the one with $p_{e}$ needed for the fractional matching
sampling.

######  Lemma 4.17.

There exists a matching $M$ in the sampled edges $E_{z}$ with

$\operatorname*{{\mathbb{E}}}\left|{M}\right|\geqslant\left(\frac{1-8\beta}{1-2\beta}\right)\cdot\frac{\beta}{10}\cdot\mu(G).$

###### Proof.

Fix a choice of random ordering $\sigma$ in 1 and its simulation in 2 and let
$y\in\mathbb{R}^{E}$ be the fractional matching defined by this process. Let
$R$ denote the entire randomness of these algorithms, which we condition on in
the following proof. Thus, the only randomness remained at this point is in
the sampling process of $E_{z}$.

Consider any choice of the hash function $h$ in the sampling process from
earlier. Define the following alternative sampling process for obtaining a set
$E_{p}$ as opposed to $E_{z}$: add any edge $e\in E$ to $E_{p}$ iff
$h(e)\leqslant p_{e}$ (recall $p_{e}=\min(1,200\log{n}\cdot y_{e})$ by Eq 14).
Since $p_{e}\leqslant z_{e}$ by Claim 4.15, for any choice of $h$, the set
$E_{p}\subseteq E_{z}$. We can thus think of $E_{p}$ as obtained from $E_{z}$
by rejecting the edges with $p_{e}<h(e)\leqslant z_{e}$. We emphasize that we
are not algorithmically finding $E_{p}$ but rather only define it for the
analysis. Thus, picking the random hash function $h$ defines a sampling
process for picking $E_{p}$ as well.

We now argue that

$\displaystyle\operatorname*{{\mathbb{E}}}\left[\mu(E_{p})\mid
R\right]\geqslant\frac{1}{5}\left|{y}\right|,$ (17)

where $\left|{y}\right|=\sum_{e\in E}y_{e}$. This is sufficient to conclude
the proof since,

$\displaystyle\operatorname*{{\mathbb{E}}}\left[\mu(E_{z})\right]$
$\displaystyle=\operatorname*{{\mathbb{E}}}_{R}\Big{[}\operatorname*{{\mathbb{E}}}\left[\mu(E_{z})\mid
R\right]\Big{]}\geqslant\operatorname*{{\mathbb{E}}}_{R}\Big{[}\operatorname*{{\mathbb{E}}}\left[\mu(E_{p})\mid
R\right]\Big{]}$ (by the law of total expectation and since
$\mu(E_{z})\geqslant\mu(E_{p})$ given $E_{p}\subseteq E_{z}$)
$\displaystyle\geqslant\frac{1}{5}\cdot\operatorname*{{\mathbb{E}}}_{R}\Big{[}\operatorname*{{\mathbb{E}}}\left[\left|{y}\right|\mid
R\right]\Big{]}=\frac{1}{2}\cdot\operatorname*{{\mathbb{E}}}\left|{y}\right|$
(by Eq 17 and the law of total expectation again)
$\displaystyle\geqslant\frac{1}{5}\cdot\left(\frac{1-8\beta}{1-2\beta}\right)\cdot\frac{\beta}{2}\cdot\mu(G)\cdot\left(1-1/\mbox{\rm
poly}{(n)}\right),$

where the final inequality holds by Theorem 2 for the choice of $y$ in 1 with
the additional $1-1/\mbox{\rm poly}{(n)}$ accounting from the correctness
probability of 2 in Lemma 4.10.

It thus remains to prove Eq 17. Define the following assignment $y^{*}_{e}$
for each edge $e\in E$:

$y^{*}_{e}:=\begin{cases}y_{e}\qquad&\textnormal{if $e\in E_{p}$ and
$y_{e}\geqslant 1/(200\log n)$,}\\\ y_{e}/p_{e}\qquad&\textnormal{if $e\in
E_{p}$ and $y_{e}<1/(200\log n)$,}\\\
0\qquad&\textnormal{otherwise.}\end{cases}$

This way, $\operatorname*{{\mathbb{E}}}\left[y^{*}_{e}\mid R\right]=y_{e}$ for
all $e\in E$: if $y_{e}\geqslant 1/(200\log{n})$, we have $p_{e}=1$ and thus
$h(e)\leqslant p_{e}$ always meaning $e\in E_{p}$ and $y^{*}_{e}=y_{e}$
deterministically. Otherwise, $e$ belongs to $E_{p}$ with probability
$p_{e}<1$ and thus
$\operatorname*{{\mathbb{E}}}\left[y^{*}_{e}\right]=p_{e}\cdot
y_{e}/p_{e}=p_{e}$.

We have

$\operatorname*{{\mathbb{E}}}\left[\sum_{e\in E}y^{*}_{e}\mid
R\right]=\sum_{e\in E}y_{e}=\left|{y}\right|,$

and at the same time $y^{*}$ is only supported on the edges in $E_{p}$. We are
going to prove that, with a proper scaling, $y^{*}$ can actually become a
fractional matching. This means $E_{p}$ contains a fractional matching with
expected size $\approx\left|{y}\right|$ which will be sufficient to prove Eq
17.

Fix a vertex $v\in V$ and define,

$\displaystyle y^{\textnormal{fix}}_{v}:=\sum_{e\ni
v}y_{e}\cdot\mathbb{I}(y_{e}\geqslant 1/(200\log n))\quad\text{and}\quad
y^{*}_{v}:=\sum_{e\ni v}y^{*}_{e}\cdot\mathbb{I}(y_{e}<1/(200\log n)).$

It is easy to see that $y^{\textnormal{fix}}_{v}\leqslant 1$ as
$y\in\mathbb{R}^{E}$ is a fractional matching. Define $E_{p}(v)$ as the edges
in $E_{p}$ that are incident on $v$. We can also observe that,

$\displaystyle y^{*}_{v}=\sum_{e\ni
v}y^{*}_{e}\cdot\mathbb{I}(y_{e}<1/(200\log n))$
$\displaystyle\leqslant\frac{1}{200\log n}\cdot\left|{E_{p}(v)}\right|.$ (18)

because, when $y_{e}<1/(200\log n)$, we know that $y_{e}/p_{e}=1/(200\log n)$.
We have,

$\operatorname*{{\mathbb{E}}}\left[\left|{E_{p}(v)}\right|\mid
R\right]=\sum_{e\ni v}p_{e}=\sum_{e\ni v}y_{e}\cdot(200\log{n})\leqslant
200\log{n},$

again using the fact that $y$ is a fractional matching. Moreover,
$\left|{E_{p}(v)}\right|$ is a sum of $\kappa$-wise independent random
variables (by the choice of $h$) and thus, by Proposition 3.5,

$\operatorname*{\textnormal{Pr}}\left(\left|{E_{p}(v)}\right|\geqslant
400\log{n}\mid
R\right)\leqslant\exp\left(-\min\left(\frac{\kappa}{2},\frac{2}{3}\cdot
200\log{n}\right)\right)\leqslant n^{-100},$

by the choice of $\kappa=200\log{n}$. Plugging in this in Eq 18 implies that
with high probability,

$y^{*}_{v}\leqslant\frac{1}{200\log n}\cdot 400\log{n}=2.$

All in all, we have that for every vertex $v\in V$, with high probability

$\sum_{e\ni v}y^{*}_{e}\leqslant 3.$

A union bound over all the vertices, implies that $y^{*}/3$ is with high
probability a fractional matching. We thus have,

$\operatorname*{{\mathbb{E}}}\left[\left|{\frac{y^{*}}{3}}\right|\mid\text{$\frac{y^{*}}{3}$
is a fractional matching,
$R$}\right]\geqslant\frac{\left|{y}\right|}{3}\cdot(1-1/\mbox{\rm
poly}{(n)}).$

To conclude the proof of Eq 17, we have,

$\displaystyle\operatorname*{{\mathbb{E}}}\left[\mu(E_{p})\mid R\right]$
$\displaystyle\geqslant\frac{2}{3}\cdot\operatorname*{\textnormal{Pr}}\left(\text{$\frac{y^{*}}{3}$
is a fractional matching}\mid
R\right)\cdot\operatorname*{{\mathbb{E}}}\left[\left|{\frac{y^{*}}{3}}\right|\mid\text{$\frac{y^{*}}{3}$
is a fractional matching},R\right]$
$\displaystyle\geqslant\frac{2\left|{y}\right|}{9}\cdot(1-1/\mbox{\rm
poly}(n))>\frac{\left|{y}\right|}{5};$

the first inequality holds by the integrality gap of fractional matchings in
3.1 for the first term, and the trivial lower bound of $\mu(E_{p})\geqslant 0$
when $y^{*}/3$ is not a fractional matching; the second inequality holds by
the fact that $y^{*}/3$ is with high probability a fractional matching and the
expectation calculated above.

#####  4.2.3 The Final Dynamic Streaming Algorithm: Concluding the Proof of
Theorem 1

We are almost done with the proof of Theorem 1. Up until now, we have already
established that for any given graph $G=(V,E)$,

  * •

We can run 2 in $O(n\log^{3}{n})$ space and recover the time stamps of all
vertices with high probability (Lemma 4.10);

  * •

We can then extract the vector $z\in\mathbb{R}^{E}$ from the information
collected above in an additional $O(n\log{n})$ space and $O(1)$ passes
deterministically (4.12 and 4.14);

  * •

We can further sample the edges $E_{z}\subseteq E$ in another
$O(n\log^{2}{n})$ space and $O(1)$ passes with high probability (Claim 4.16);

  * •

Finally, we find a maximum matching in $E_{z}$; conditioned on the high
probability events above, this gives us a matching $M$ of _expected_ size
(Lemma 4.17):

$\operatorname*{{\mathbb{E}}}\left|{M}\right|\geqslant\left(\frac{1-8\beta}{1-2\beta}\right)\cdot\frac{\beta}{10}\cdot\mu(G).$

The main missing pieces are to $(i)$ boost the probability of success of this
algorithm to a high probability bound instead of an expectation-guarantee,
and, subsequently, $(ii)$ boost the approximation ratio of the algorithm to a
$(1+\varepsilon)$-approximation (and extend it even to weighted graphs). We
show that both these tasks can be achieved using the existing sketching and
streaming results listed in Section 3.2. The proofs in the following are
pretty standard.

###### Boosting the probability of success.

Let $G=(V,E)$ be the input graph. We can assume without loss of generality
that $\mu(G)\geqslant\log^{2}\\!{(n)}$; the total number of edges in any graph
is at most $2n\cdot\mu(G)$ and thus we can run a randomized sparse-recovery in
Proposition 3.6 for recovering $2n\log^{2}\\!{(n)}$ edges in $O(n\log^{3}{n})$
space with high probability; if $\mu(G)<\log^{2}\\!{(n)}$, this algorithm
succeeds in recovering the entire graph and finding a maximum matching of $G$
exactly. Otherwise, we continue with the main algorithm.

Let $\varepsilon=1/2$ and run the vertex-sampling approach of Proposition 3.7
for $O(\log{n})$ guesses of $\mu(G)$ as powers of $2$ between
$\log^{2}\\!{(n)}$ to $n$ and run our algorithm for each guess separately in
parallel. We specify this more details in the following.

For a given guess $\tilde{\mu}$, at the beginning of the stream, we partition
the vertices randomly into groups $U_{1},\ldots,U_{t}$ for
$t=8\tilde{\mu}/\varepsilon=16\tilde{\mu}$. This allows us to define a graph
$H:=H(\tilde{\mu})$ on new vertices $\left\\{u_{1},\ldots,u_{t}\right\\}$
(representing the groups $U_{1},\ldots,U_{t}$) and edges between $u_{i}$ and
$u_{j}$ iff there exists at least one edge $(x,y)\in E$ with $x\in U_{i}$ and
$y\in U_{j}$ (note that multiple edges in $E$ can be mapped to a single edge
in $H$ but $H$ does _not_ have multi-edges). Moreover, an update to the
dynamic stream defining $E$ can be also directly translated to an update to
the graph $H$ and thus we can run our algorithms over $H$.222222We should
mention a minor point here. There is a slight difference between the dynamic
stream defining $E(H)$ versus for $E$. In particular, we should treat the
dynamic stream on $E(H)$ as a vector $\phi\in\mathbb{N}^{{t}\choose{2}}$ where
$\phi_{u_{i},u_{j}}>0$ (but not necessarily $\phi_{u_{i},u_{j}}=1$) is
interpreted as the the existence of the edge $(u_{i},u_{j})\in E(H)$ (whereas
for the dynamic stream defining $E$, the vector
$\phi\in\left\\{0,1\right\\}^{{V}\choose{2}}$ will be the characteristic
vector of $E$). Nevertheless, our algorithms work the same exact way over $H$.
This is because the only access of these algorithms to the edges of the graph
was via sparse-recovery algorithms and these algorithms return the support of
the vector $\phi$ (or whichever subsets of it they are being run on).
Moreover, since the entries of $\phi$ are still $\mbox{\rm poly}{(n)}$
bounded, the space complexity of the algorithm is exactly as before (as a
function of $n$ itself, i.e., we do not aim for a better dependence based on
$t\leqslant n$).

Now consider, the guess $\tilde{\mu}$ such that
$\mu(G)\leqslant\tilde{\mu}\leqslant 2\cdot\mu(G)$. Firstly, by Proposition
3.7, we have that with high probability $\mu(H)\geqslant\mu(G)/2$. As such,
for this choice and by picking $\beta=1/16$ in our algorithm, for the returned
matching $M$, we have that

$\operatorname*{{\mathbb{E}}}\left|{M}\right|\geqslant\left(\frac{1-8\beta}{1-2\beta}\right)\cdot\frac{\beta}{10}\cdot\mu(H)\geqslant\frac{1}{40}\cdot\mu(G).$

On the other hand, in $H$, we deterministically have that
$\left|{M}\right|\leqslant t/2$ since it is a matching and $H$ has at most $t$
vertices. This means that we also always have

$\left|{M}\right|\leqslant 16\mu(G).$

This implies that

$\operatorname*{\textnormal{Pr}}\left(\left|{M}\right|\geqslant\frac{1}{50}\cdot\mu(G)\right)\geqslant\frac{1}{3200}$

as otherwise

$\operatorname*{{\mathbb{E}}}\left|{M}\right|<\frac{1}{50}\cdot\mu(G)+\frac{1}{3200}\cdot
16\mu(G)<\left(\frac{1}{50}+\frac{1}{200}\right)\cdot\mu(G)=\frac{1}{40}\cdot\mu(G),$

a contradiction. Repeating this algorithm now $O(\log{n})$ times and returning
the largest matching implies that with high probability, we will find a
matching of size at least $\mu(G)/50$. Note that given a matching in $H$, we
can spend $O(1)$ more passes and $O(n\log^{2}{n})$ space to find a matching in
$G$ of the same size: for any edge $(u_{i},u_{j})$ in the matching of $H$, we
need to just find a single edge between the vertices of the group $U_{i}$ and
$U_{j}$ which we know exists. This can be done using a standard sampling trick
and sparse-recovery algorithms: basically, we first count the number $c_{i,j}$
of edges between $U_{i}$ and $U_{j}$ in a single pass and in the second pass,
we sample $\simeq\log{(n)}/c_{i,j}$ fraction of vertex-pairs between $U_{i}$
and $U_{j}$ and run a sparse-recovery algorithm for $\simeq(\log{n})$-sparse
vectors on this subsampled pairs. With high probability, the number of sampled
edges is indeed $\lesssim\log{n}$ and the recovery algorithm finds at least
one of those edges.

In conclusion, by running our main algorithm $O(\log^{2}{(n)})$ times in
parallel for different guesses of $\mu(G)$ and different repetitions for each
guess, we obtain an $O(1)$-approximation algorithm to the maximum matching of
any given graph $G=(V,E)$ in a dynamic stream with high probability232323To
simplify the proof, we have been quite cavalier with the choice of constants
in the analysis of the algorithm and only prove a $50$-approximation
guarantee. Given that we are going to boost the approximation ratio of this
algorithm in a black-box way in the next step, any constant-approximation
works for us and thus we did not optimize the approximation ratio of this base
algorithm. A more careful analysis of the bounds can reduce this ratio
dramatically, but we suspect the limit will be close to $6$-approximation (or
possibly $4$ for bipartite graphs).. Moreover, this algorithm uses
$O(n\log^{5}{n})$ space and $O(\log\log{n})$ passes.

###### Boosting the approximation ratio.

Now that we have an $O(1)$-approximation algorithm that succeeds with high
probability, this step becomes a black-box application of Proposition 3.8.

This concludes the proof of Theorem 1.

###  5 The Lower Bound

We provide our multi-pass lower bound for approximate matchings in the dynamic
streaming model in this section, formalizing 2.

######  Theorem 3.

Any semi-streaming algorithm that given any $n$-vertex graph in a dynamic
streams, outputs an $O(1)$-approximation to the maximum matching problem with
any constant probability of success requires $\Omega(\log\log n)$ passes.

We prove Theorem 3 using the connection between the streaming and
communication models (Proposition 3.10). Our proof consists of two separate
parts proven in the subsequent sections.

Part 1. In Section 5.1, we define a new two-party communication problem for
$r$-round protocols called Augmented Hidden Matrices ($\mathsf{AHM}_{r}$, see
5.3) and prove the following lower bound on its communication complexity in
Section 5.1.1.

######  Lemma 5.1.

For any sufficiently large $n_{r}\in\mathbb{N}$, positive integer
$r=O(\log\log\\!{(n_{r})})$, positive number $\alpha\leqslant 1-n_{r}^{-1/2r}$
and constant $c_{\textsc{adv}}\geqslant 1$, any $r$-round protocol that
successfully solves $\mathsf{AHM}_{r}(n_{r},\alpha)$ with probability of
success at least

$\frac{1}{2}\cdot\left(1+\frac{r}{20\cdot c_{\textsc{adv}}\cdot(r+1)}\right)$

must have a communication cost of at least

$s_{r}=\left(n_{r}\right)\uparrow\left(1+\frac{1}{2^{r}-1}\right)\cdot\left(1-\alpha\right)\uparrow\left(\frac{r\cdot
2^{r}}{2^{r}-1}\right)\cdot\frac{(\alpha/(1-\alpha))^{2}}{(c_{\textsc{jpy}}\cdot
c_{\textsc{adv}}^{2}\cdot 80^{2})^{r}\cdot((r+1)!)^{3}}.$

Part 2. In Section 5.2, we construct graph instances corresponding to the
$\mathsf{AHM}_{r}(n_{r},\alpha)$ problem. We prove the following connection
between any $p$-pass dynamic streaming algorithm for approximate maximum
matching and $\mathsf{AHM}_{r}$ where $r=2p-1$ in Section 5.2.3.

######  Lemma 5.2.

For any sufficiently large $n_{r}\in\mathbb{N}$, integers $p,s\geqslant 1$,
and number $\beta\geqslant 1$, let $\mathcal{A}$ by any $p$-pass $s$-space
dynamic streaming algorithm that computes a $\beta$-approximate maximum
matching on a $(4n_{r})$-vertex bipartite graphs with probability of success
at least $1-1/\mbox{\rm poly}{(n)}$. Then, for $r=2p-1$ and
$\alpha=1/(4\cdot\beta\cdot r)$, there exists an $r$-round protocol $\pi$ for
$\mathsf{AHM}_{r}(n_{r},\alpha)$ with probability of success

$\textnormal{suc}(\pi)\geqslant\frac{1}{2}\cdot\left(1+\frac{1}{3\beta}\right)$

and communication cost

$\textsc{CC}(\pi)\leqslant r\cdot s+O(r\cdot n_{r}\log{(n_{r})}).$

We now prove Theorem 3 using the above two lemmas.

###### Proof of Theorem 3.

Without loss of generality, we can solely focus on proving the lower bound for
semi-streaming algorithms that succeed with high probability instead of
constant probability. This is due to the following standard reduction.

Simply run a constant probability of success streaming algorithm in parallel
$O(\log{n})$ times and consider all the outputs; then, spend one more pass to
filter out all the ones that output an edge that does not belong to the graph
(because they failed), and among the rest, output the largest matching. This
way, we still obtain a semi-streaming algorithm with just one more pass (which
is negligible in this context) and a high probability of success. As such, in
the rest of the proof, we focus on high-probability-of-success algorithms.

For sufficiently large $n\in\mathbb{N}$, integers $p,s\geqslant 1$ and any
constant $\beta\geqslant 1$, let $\mathcal{A}$ be any $p$-pass $s$-space
dynamic streaming algorithm that computes a $\beta$-approximate maximum
matching on any $(4n)$-vertex graph with probability of success at least
$1-1/\mbox{\rm poly}{(n)}$.

By Lemma 5.2 with $r=2p-1$ and $\alpha=1/(4\cdot\beta\cdot r)$, there exists
an $r$-round protocol $\pi$ for $\mathsf{AHM}_{r}(n,\alpha)$ where

$\textnormal{suc}(\pi)\geqslant\frac{1}{2}\cdot\left(1+\frac{1}{3\beta}\right)\qquad\text{and}\qquad\textsc{CC}(\pi)\leqslant
r\cdot s+O(r^{2}\cdot n\log n).$

By Lemma 5.1 with $n_{r}=n$ and $c_{\textsc{adv}}=\beta$, we have that
$\textsc{CC}(\pi)\geqslant s_{r}$ since

$\textnormal{suc}(\pi)\geqslant\frac{1}{2}\cdot\left(1+\frac{1}{3\beta}\right)\geqslant\frac{1}{2}\cdot\left(1+\frac{r}{20\cdot\beta\cdot(r+1)}\right).$

Then, by combining the bounds on $\textsc{CC}(\pi)$ and re-arranging the
inequality, we obtain the following lower bound on the space of $\mathcal{A}$
using the fact that $c_{\textsc{jpy}}$ and $\beta$ are constants (and thus
$\alpha=\Theta(1/r)$):

$\displaystyle s$ $\displaystyle\geqslant\frac{s_{r}}{r}-O(n\log n)$
$\displaystyle={\left(n\right)\uparrow\left(1+\frac{1}{2^{r}-1}\right)\cdot\left(1-\alpha\right)\uparrow\left(\frac{r\cdot
2^{r}}{2^{r}-1}\right)\cdot\frac{(\alpha/(1-\alpha))^{2}}{(c_{\textsc{jpy}}\cdot\beta^{2}\cdot
80^{2})^{r}\cdot((r+1)!)^{3}}}\cdot\frac{1}{r}-O(n\log n)$
$\displaystyle\geqslant{\left(n\right)\uparrow\left(1+\frac{1}{2^{r}-1}\right)}\cdot
r^{-\Theta(r)}-O(n\log n).$ (19)

Overall, by considering $\mathcal{A}$ with $p=o(\log\log n)$ and thus
$r=2p-1=o(\log\log n)$, we have that the space used by the algorithm is $s\gg
n\cdot\mbox{\rm polylog}(n)$ using Eq 19. Therefore, any dynamic streaming
algorithm that uses $n\cdot{\mbox{\rm polylog}}(n)$ space, namely, a semi-
streaming algorithm, to compute an $O(1)$-approximate maximum matching must
use $\Omega(\log\log n)$ passes.

####  5.1 Augmented Hidden Matrices

For any $r\geqslant 1$, the $\mathsf{AHM}_{r}(n_{r},\alpha)$ problem is
defined recursively using $b_{r}^{2}$ many instances of the
$\mathsf{AHM}_{r-1}(n_{r-1},\alpha)$ problem where
$n_{r},b_{r},n_{r-1}\in\mathbb{N}$ and $\alpha\in(0,1)$. The output of any
instance is a single bit, pointed to by a _search sequence_ (to be defined
soon).

######  Definition 5.3 (Augmented Hidden Matrices).

The Augmented Hidden Matrices problem, denoted by
$\mathsf{AHM}_{r}(n_{r},\alpha)$, is defined as follows (see Figure 9 for an
illustration): • For $\mathbf{r=0}$. Alice does not receive any input, i.e.,
$A^{(0)}=\emptyset$, and Bob receives a single bit $B^{(0)}\in\\{0,1\\}$.
There is no communication and Alice has to output $B^{(0)}$. • For
$\mathbf{r\geqslant 1}$. Start with $b_{r}^{2}$ instances of the players’
inputs in $\mathsf{AHM}_{r-1}(n_{r-1},\alpha)$, denoted by
$(A^{(r-1)}_{i,j},B^{(r-1)}_{i,j})$ for $i,j\in[b_{r}]$. Alice receives
$A^{(r)}=X$ where $X$ is a $b_{r}\times b_{r}$ matrix such that
$X[i,j]=B^{(r-1)}_{i,j}$ for $i,j\in[b_{r}]$. Bob receives the input
$B^{(r)}=(\sigma_{\textnormal{{r}}},\sigma_{\textnormal{{c}}},Y)$ where
$\sigma_{\textnormal{{r}}},\sigma_{\textnormal{{c}}}\in S_{b_{r}}$ are
permutations of $[b_{r}]$ and $Y$ is a $b_{r}\times b_{r}$ matrix such that,
for $i,j\in[b_{r}]$, $\displaystyle
Y[i,j]=\begin{cases}\left(A^{(r-1)}_{i,j},B^{(r-1)}_{i,j}\right)&\text{if
}b_{r}\cdot\alpha<\sigma_{\textnormal{{r}}}(i)\neq\sigma_{\textnormal{{c}}}(j)\leqslant
b_{r},\\\ A^{(r-1)}_{i,j}&\text{if
}b_{r}\cdot\alpha<\sigma_{\textnormal{{r}}}(i)=\sigma_{\textnormal{{c}}}(j)\leqslant
b_{r},\\\ \emptyset&\text{otherwise.}\end{cases}$ Alice starts the
communication. After all the messages are sent, the player receiving the last
message is given a search sequence, which is a tuple of $r$ integers,
$(k^{\star}_{r},k^{\star}_{r-1},\ldots,k^{\star}_{1})$ with
$k^{\star}_{i}\in[b_{i}\cdot(1-\alpha)]$. This player must output the solution
to $\mathsf{AHM}_{r-1}$ instance $(A^{(r-1)}_{i,j},B^{(r-1)}_{i,j})$ where
$\sigma_{\textnormal{{r}}}(i)=\sigma_{\textnormal{{c}}}(j)=b_{r}\cdot\alpha+k^{\star}_{r}$
using the search sequence $(k^{\star}_{r-1},k^{\star}_{r-2}\ldots
k^{\star}_{1})$ .

We expound more on the defintion of $\mathsf{AHM}_{r}$ problem, and give some
useful terminology next.

For $r=0$ case, we set $n_{0}=1$, and $\mathsf{AHM}_{0}(1,\alpha)$ is also
denoted by $\mathsf{AHM}_{0}(1)$. This is a base case that is trivially hard
for $0$-round protocols.

For each of the $b_{r}^{2}$ many $\mathsf{AHM}_{r-1}$ instances
$(A^{(r-1)},B^{(r-1)})$ used in an instance of $\mathsf{AHM}_{r}$, the roles
of Alice and Bob are swapped, i.e., Alice holds $B^{(r-1)}$ and Bob holds
$A^{(r-1)}$. Out of these instances, we call the set of the
$\bm{k_{r}}:=b_{r}\cdot(1-\alpha)$ many $\mathsf{AHM}_{r-1}$ instances
$(A^{(r-1)}_{i,j},B^{(r-1)}_{i,j})$ where
$b_{r}\cdot\alpha<\sigma_{\textnormal{{r}}}(i)=\sigma_{\textnormal{{c}}}(j)\leqslant
b_{r}$ as the special sub-instances in an instance of $\mathsf{AHM}_{r}$.
Since each special sub-instance identifies another set of $k_{r-1}$ many
$\mathsf{AHM}_{r-2}$ special (sub-)sub-instances, recursively applying this
for all special sub-instances of $\mathsf{AHM}_{r}$ identifies a set of
$k_{r}\cdot k_{r-1}\cdot\ldots\cdot k_{1}$ many $\mathsf{AHM}_{0}$ special
base instances, where each one corresponds to a single bit $B^{(0)}$.

It is useful to point to the number of special base instances explicitly for
later.

######  Observation 5.4.

In any instance of $\mathsf{AHM}_{r}(n_{r},\alpha)$, there are $k_{r}\cdot
k_{r-1}\cdot\ldots\cdot k_{1}$ many special base instances where
$k_{i}=b_{i}\cdot(1-\alpha)$ for each $i\in[r]$.

Furthermore, we call the set of $k_{r}^{2}-k_{r}$ many $\mathsf{AHM}_{r-1}$
instances $(A^{(r-1)}_{i,j},B^{(r-1)}_{i,j})$ where
$b_{r}\cdot\alpha<\sigma_{\textnormal{{r}}}(i)\neq\sigma_{\textnormal{{c}}}(j)\leqslant
b_{r}$ as the off-diagonal sub-instances in an instance of $\mathsf{AHM}_{r}$.
We define some more notation to point to the sub-instances.

###### Notation.

In any instance of $\mathsf{AHM}_{r}$, denoted by $(A^{(r)},B^{(r)})$, we use
the following notation. We denote each of the $k_{r}$ many special sub-
instances as
$(A^{\textnormal{{spec}}}_{k},B^{\textnormal{{spec}}}_{k})=(A^{(r-1)}_{i,j},B^{(r-1)}_{i,j})$
where
$\sigma_{\textnormal{{r}}}(i)=\sigma_{\textnormal{{c}}}(j)=b_{r}\cdot\alpha+k$
and $i,j\in[b_{r}]$ for $k\in[k_{r}]$. We collectively denote these special
sub-instances as $(A^{\textnormal{{spec}}},B^{\textnormal{{spec}}})$ where

$A^{\textnormal{{spec}}}=(A^{\textnormal{{spec}}}_{1},A^{\textnormal{{spec}}}_{2},\ldots,A^{\textnormal{{spec}}}_{k_{r}})\quad\text{and}\quad
B^{\textnormal{{spec}}}=(B^{\textnormal{{spec}}}_{1},B^{\textnormal{{spec}}}_{2},\ldots,B^{\textnormal{{spec}}}_{k_{r}}).$

We denote the collection of the $k_{r}^{2}-k_{r}$ many off-diagonal sub-
instances as $(A^{\textnormal{{off}}},B^{\textnormal{{off}}})$ where

$A^{\textnormal{{off}}}=(A^{(r-1)}_{i,j}:b_{r}\cdot\alpha<\sigma_{\textnormal{{r}}}(i)\neq\sigma_{\textnormal{{c}}}(j)\leqslant
b_{r})\quad\text{and}\quad
B^{\textnormal{{off}}}=(B^{(r-1)}_{i,j}:b_{r}\cdot\alpha<\sigma_{\textnormal{{r}}}(i)\neq\sigma_{\textnormal{{c}}}(j)\leqslant
b_{r}).$

We let $B^{\textnormal{{rest}}}$ be the remaining $b_{r}^{2}-k_{r}^{2}$ sub-
instances $B^{(r-1)}_{i,j}$ where $\sigma_{\textnormal{{r}}}(i)\leqslant
b_{r}\cdot\alpha$ or $\sigma_{\textnormal{{c}}}(j)\leqslant b_{r}\cdot\alpha$.

###### Search Sequences.

After all the messages are sent, the search sequence given to the player who
receives the last message is always uniformly random and independent of the
players’ inputs. That is, a search sequence
$(k^{\star}_{r},k^{\star}_{r-1},\ldots,k^{\star}_{1})$ is chosen where for
$i\in[r]$, $k^{\star}_{i}$ is chosen uniformly at random and independently
from $[b_{i}\cdot(1-\alpha)]$. The solution to any instance of
$\mathsf{AHM}_{r}$ given $(k^{\star}_{r},k^{\star}_{r-1},\dots,k^{\star}_{1})$
is the same as the solution to the uniformly chosen special sub-instance
$(A^{\textnormal{{spec}}}_{k^{\star}_{r}},B^{\textnormal{{spec}}}_{k^{\star}_{r}})$
on the search sequence $(k^{\star}_{r-1},\dots,k^{\star}_{1})$. Continuing
this until the last index $k^{\star}_{1}$ in the search sequence ultimately
identifies a uniform random special base instance, i.e., an instance of
$\mathsf{AHM}_{0}$, whose solution is the solution to the $\mathsf{AHM}_{r}$
instance.

Our definition of the $\mathsf{AHM}_{r}(n_{r},\alpha)$ communication problem
is non-standard as the uniformly random search sequence, which is a part of
the input, is given to the final player _at the very end of a protocol_. In
particular, the search sequence is crucial to defining the output of the
problem, but does not form part of the input held by the players throughout
the protocol.

Although the search sequence defines the communication problem in a non-
standard way, the easy direction of Yao’s minmax theorem is still applicable.
Thus, we prove Lemma 5.1 by considering deterministic protocols for
$\mathsf{AHM}_{r}(n_{r},\alpha)$ where the players’ inputs $(A^{(r)},B^{(r)})$
are sampled from the hard distribution (which we define shortly).

######  Remark 2.

The definition of $\mathsf{AHM}_{r}(n_{r},\alpha)$ (5.3) always includes the
uniform random search sequence, which is independent of the players’ inputs
and how they are distributed. However, when referring to the
$\mathsf{AHM}_{r}(n_{r},\alpha)$ problem, we do not explicitly mention the
given search sequence if this is clear from context.

$B$$B$$B$$B$$B$$B$$B$$B$$B$$B$$B$$B$$B$$B$$B$$B$$A,B$$A,\underline{\bm{B}}$$A,\underline{\bm{B}}$$A,\underline{\bm{B}}$$A,\underline{\bm{B}}$$B$$B$$A,\underline{\bm{B}}$$A,B$$A,\underline{\bm{B}}$$A,\underline{\bm{B}}$$A,\underline{\bm{B}}$$B$$B$$A,\underline{\bm{B}}$$A,\underline{\bm{B}}$$A,B$$A,\underline{\bm{B}}$$A,\underline{\bm{B}}$$B$$B$$A,\underline{\bm{B}}$$A,\underline{\bm{B}}$$A,\underline{\bm{B}}$$A,B$$A,\underline{\bm{B}}$$B$$B$$A,\underline{\bm{B}}$$A,\underline{\bm{B}}$$A,\underline{\bm{B}}$$A,\underline{\bm{B}}$$A,B$$b_{r}\cdot\alpha$$b_{r}/\alpha$$b_{r}\cdot(1-\alpha)$$b_{r}\cdot\alpha$$b_{r}\cdot(1-\alpha)$$\sigma_{\textnormal{{r}}}(1)$$\sigma_{\textnormal{{c}}}(1)$$\sigma_{\textnormal{{r}}}(2)$$\sigma_{\textnormal{{c}}}(2)$$\sigma_{\textnormal{{r}}}(b_{r})$$\sigma_{\textnormal{{c}}}(b_{r})$$\vdots$$\dots$
Figure 9:  An illustration of $\mathsf{AHM}_{r}(n_{r},\alpha)$ where
$b_{r}=7$, $k^{\star}_{r}=2$, and $\alpha=2/7$, i.e., $b_{r}\cdot\alpha=2$. In
this figure, the $b_{r}\times b_{r}$ matrix is presented after applying the
respective permutations of rows and columns using $\sigma_{\textnormal{{r}}}$
and $\sigma_{\textnormal{{c}}}$, which are held by Bob (alternatively, think
of $\sigma_{\textnormal{{r}}}$ and $\sigma_{\textnormal{{c}}}$ as identity
permutations here). In each position of the matrix, the corresponding input is
either a complete instance of $\mathsf{AHM}_{r-1}(n_{r-1},\alpha)$ denoted by
$(A,B)=(A^{(r-1)},B^{(r-1)})$ or a partial instance of
$\mathsf{AHM}_{r-1}(n_{r-1},\alpha)$ denoted by $B=B^{(r-1)}$ due to the
asymmetry of the construction. All of the $B$’s are held by Alice, all of the
$A$’s are held by Bob, and Bob further holds the $B$’s corresponding to
$B^{\textnormal{{off}}}$, which are bolded and underlined. The shaded
instances are the special sub-instances
$(A^{\textnormal{{spec}}},B^{\textnormal{{spec}}})$, i.e., the ones in the
diagonal of the bolded box. The remaining $B$’s belong to
$B^{\textnormal{{rest}}}$, i.e., the ones not in the bolded box. Given the
search sequence $(k^{\star}_{r},k^{\star}_{r-1},\ldots,k^{\star}_{1})$, the
goal is to solve the the instance identified by ${k^{\star}_{r}}=2$ (shaded in
green, and denoted by
$(A^{\textnormal{{spec}}}_{2},B^{\textnormal{{spec}}}_{2})$), using the search
sequence $(k^{\star}_{r-1},\ldots,k^{\star}_{1})$.

Next, we fix the parameters of the problem, and then define our hard
distribution $\mathcal{D}_{r}(n_{r},\alpha)$.

###### Parameter Choices.

For all $r\geqslant 1$, it is sufficient for us to consider the
$\mathsf{AHM}_{r}$ problem for parameters that satisfy the following
conditions:

$\begin{split}n_{r}&=n_{r-1}\cdot b_{r}\\\
b_{r}&=\left(n_{r}\right)\uparrow\left(\frac{2^{r-1}}{2^{r}-1}\right)\cdot\left(1-\alpha\right)\uparrow\left(\frac{r\cdot
2^{r-1}}{2^{r}-1}-1\right)\\\
n_{r-1}&=\left(n_{r}\right)\uparrow\left(\frac{2^{r-1}-1}{2^{r}-1}\right)/\left(1-\alpha\right)\uparrow\left(\frac{r\cdot
2^{r-1}}{2^{r}-1}-1\right).\end{split}$ (20)

From now on, we only consider $\mathsf{AHM}_{r}(n_{r},\alpha)$ with these
parameter choices.

Hard Distribution $\mathcal{D}_{r}(n_{r},\alpha)$ for
$\mathsf{AHM}_{r}(n_{r},\alpha)$: • For $\mathbf{r=0}$. Sample
$B^{(0)}\in\\{0,1\\}$ uniformly and independently. We also use
$\mathcal{D}_{0}(1)$ to denote this distribution. • For $\mathbf{r\geqslant
1}$. Sample the $b_{r}^{2}$ instances $(A^{(r-1)}_{i,j},B^{(r-1)}_{i,j})$ from
$\mathcal{D}_{r-1}(n_{r-1},\alpha)$ independently for each $i,j\in[b_{r}]$
where $b_{r},n_{r-1}$ are as defined in Eq 20. Sample the permutations
$\sigma_{\textnormal{{r}}},\sigma_{\textnormal{{c}}}\in S_{b_{r}}$ uniformly
and independently.

Recall that the distribution of the search sequence was already defined to be
uniformly random, and independent of all other inputs.

We have the following obvious observation.

######  Observation 5.5.

Any $0$-round protocol (wherein Alice outputs the answer) for solving
$\mathsf{AHM}_{0}(1)$ succeeds with probability at most $1/2$ when the input
is sampled from $\mathcal{D}_{0}(1)$.

The proof of Lemma 5.1 relies on a round-elimination argument that shows that
if there is a good deterministic protocol for $\mathsf{AHM}_{r}(n_{r},\alpha)$
under the input distribution $\mathcal{D}_{r}(n_{r},\alpha)$, then there must
be a good deterministic protocol for $\mathsf{AHM}_{r-1}(n_{r-1},\alpha)$
under the input distribution $\mathcal{D}_{r-1}(n_{r-1},\alpha)$. We prove the
following key lemma in Section 5.1.2.

######  Lemma 5.6.

For any $r\geqslant 1$, sufficiently large $n_{r}\in\mathbb{N}$,
$\alpha,\delta\in(0,1)$, and integer $s\geqslant 1$, suppose there exists a
deterministic $r$-round protocol $\pi_{r}$ for
$\mathsf{AHM}_{r}(n_{r},\alpha)$ with

$\textsc{CC}(\pi_{r})\leqslant s$

and probability of success at least $\delta$ when the input is sampled from
$\mathcal{D}_{r}(n_{r},\alpha)$. Then, for any $\varepsilon\in(0,1)$, there
exists a deterministic $(r-1)$-round protocol $\pi_{r-1}$ for
$\mathsf{AHM}_{r-1}$ with

$\textsc{CC}(\pi_{r-1})\leqslant
c_{\textsc{jpy}}\cdot(r/\varepsilon)\cdot\left(\frac{s}{k_{r}}+r\right),$

and probability of success

$\textnormal{suc}(\pi_{r-1})\geqslant\delta-\varepsilon-\sqrt{\frac{s}{2\cdot
b_{r}^{2}\cdot\alpha^{2}}}$

when the players’ input is sampled from $\mathcal{D}_{r-1}(n_{r-1},\alpha)$.

With that, we have the main tools required to prove of our lower bound for
$\mathsf{AHM}_{r}(n_{r},\alpha)$.

#####  5.1.1 The Lower Bound for Augmented Hidden Matrices: Proof of Lemma 5.1

###### Proof of Lemma 5.1.

We prove this result by first assuming the existence of a deterministic
$r$-round protocol $\pi_{r}$ for $\mathsf{AHM}_{r}$ that is ‘too good to be
true’ (w.r.t. the statement of the lemma) on inputs sampled from
$\mathcal{D}_{r}(n_{r},\alpha)$. Then, by iteratively applying the round-
elimination argument in Lemma 5.6, we ultimately obtain a deterministic
$0$-round protocol $\pi_{0}$ for $\mathsf{AHM}_{0}$ that is trivially ‘too
good to be true’ on inputs sampled from $\mathcal{D}_{0}(1)$ (given 5.5), a
contradiction. Formally, we prove this by induction on $r$.

Base case for $\mathbf{r=1}$. Suppose that there exists a deterministic
$1$-round protocol $\pi_{1}$ for $\mathsf{AHM}_{1}(n_{1},\alpha)$ with
communication cost

$\textsc{CC}(\pi_{1})<s_{1}=\frac{n_{1}^{2}\cdot\alpha^{2}}{c_{\textsc{jpy}}\cdot
c_{\textsc{adv}}^{2}\cdot 80^{2}\cdot 8}$

and probability of success

$\textnormal{suc}(\pi_{1})\geqslant\frac{1}{2}\cdot\left(1+\frac{1}{40\cdot
c_{\textsc{adv}}}\right)$

when the input is sampled from $\mathcal{D}_{1}(n_{1},\alpha)$. Then, using
Lemma 5.6 with $\varepsilon=1/(160\cdot c_{\textsc{adv}})$, we obtain a
deterministic $0$-round protocol $\pi_{0}$ for $\mathsf{AHM}_{0}(1)$ which has
no communication cost (since no messages are communicated) and succeeds with
probability

$\displaystyle\textnormal{suc}(\pi_{0})$
$\displaystyle\geqslant\frac{1}{2}\cdot\left(1+\frac{1}{40\cdot
c_{\textsc{adv}}}\right)-\frac{1}{160\cdot
c_{\textsc{adv}}}-\sqrt{\frac{n_{1}^{2}\cdot\alpha^{2}}{c_{\textsc{jpy}}\cdot
c_{\textsc{adv}}^{2}\cdot 80^{2}\cdot 16\cdot b_{1}^{2}\cdot\alpha^{2}}}$
$\displaystyle\geqslant\frac{1}{2}\cdot\left(1+\frac{1}{80\cdot
c_{\textsc{adv}}}-\sqrt{\frac{n_{1}^{2}}{c_{\textsc{adv}}^{2}\cdot
160^{2}\cdot b_{1}^{2}}}\right)$ (since $c_{\textsc{jpy}}\geqslant 1$)
$\displaystyle=\frac{1}{2}\cdot\left(1+\frac{1}{160\cdot
c_{\textsc{adv}}}\right)$ (since $b_{1}=n_{1}$ by Eq 20)

when the input is sampled from $\mathcal{D}_{0}(1)$. This, however,
contradicts 5.5 and thus proves the result for the base case when $r=1$.

Inductive step for $\mathbf{r\geqslant 2}$. Having proven the base case, we
now prove the result for any $r\geqslant 2$ given the result holds for $r-1$,
i.e., the inductive hypothesis. Suppose that there exists a deterministic
protocol $\pi_{r}$ for $\mathsf{AHM}_{r}(n_{r},\alpha)$ with communication
cost

$\textsc{CC}(\pi_{r})<s_{r}=\left(n_{r}\right)\uparrow\left(1+\frac{1}{2^{r}-1}\right)\cdot\left(1-\alpha\right)\uparrow\left(\frac{r\cdot
2^{r}}{2^{r}-1}\right)\cdot\frac{(\alpha/(1-\alpha))^{2}}{(c_{\textsc{jpy}}\cdot
c_{\textsc{adv}}^{2}\cdot 80^{2})^{r}\cdot((r+1)!)^{3}}$

and probability of success

$\textnormal{suc}(\pi_{r})\geqslant\frac{1}{2}\cdot\left(1+\frac{r}{20\cdot
c_{\textsc{adv}}\cdot(r+1)}\right)$

when the input is sampled from $\mathcal{D}_{r}(n_{r},\alpha)$. Then, using
Lemma 5.6 with $\varepsilon=1/{(40\cdot c_{\textsc{adv}}\cdot(r+1)^{2})}$, we
obtain a deterministic $(r-1)$-round protocol $\pi_{r-1}$ for
$\mathsf{AHM}_{r-1}(n_{r-1},\alpha)$ with cost

$\displaystyle\textsc{CC}(\pi_{r-1})<c_{\textsc{jpy}}\cdot(40\cdot
c_{\textsc{adv}}\cdot(r+1)^{2}\cdot r)\cdot\left(s_{r}/k_{r}+r\right)$ (21)

and probability of success

$\displaystyle\textnormal{suc}(\pi_{r-1})\geqslant\frac{1}{2}\cdot\left(1+\frac{r}{20\cdot
c_{\textsc{adv}}\cdot(r+1)}\right)-\frac{1}{40\cdot
c_{\textsc{adv}}\cdot(r+1)^{2}}-\sqrt{\frac{s_{r}}{2\cdot
b_{r}^{2}\cdot\alpha^{2}}}$ (22)

when the input is sampled from $\mathcal{D}_{r-1}(n_{r-1},\alpha)$.

We now argue that protocol $\pi_{r-1}$ contradicts the result for $r-1$,
namely, the inductive hypothesis. In particular, we show that
$\textsc{CC}(\pi_{r-1})<s_{r-1}$ and

$\textnormal{suc}(\pi_{r-1})\geqslant\frac{1}{2}\cdot\left(1+\frac{(r-1)}{20\cdot
c_{\textsc{adv}}\cdot r}\right).$

The rest of the proof is a careful but rather tedious calculation of the
values we obtain using the above reduction for the communication cost and
probability of success of the protocol.

To bound the communication cost, we first reiterate the relation between
$n_{r}$ and $n_{r-1}$ from Eq 20 as follows:

$\displaystyle\left(n_{r}\right)\uparrow\left(\frac{1}{2^{r}-1}\right)$
$\displaystyle=\left(n_{r-1}\right)\uparrow\left(\frac{1}{2^{r-1}-1}\right)\cdot\left(1-\alpha\right)\uparrow\left(\left(\frac{r\cdot
2^{r-1}}{2^{r}-1}-1\right)\cdot\frac{1}{2^{r-1}-1}\right)$
$\displaystyle=\left(n_{r-1}\right)\uparrow\left(\frac{1}{2^{r-1}-1}\right)\cdot\left(1-\alpha\right)\uparrow\left(\frac{(r-2)\cdot
2^{r-1}+1}{(2^{r}-1)\cdot(2^{r-1}-1)}\right).$ (23)

Next, we use this to simplify the expression for the term $s_{r}/k_{r}$ in Eq
21.

$\displaystyle\frac{s_{r}}{k_{r}}$
$\displaystyle=\underbrace{\left(n_{r}\right)\uparrow\left(1+\frac{1}{2^{r}-1}\right)\cdot\left(1-\alpha\right)\uparrow\left(\frac{r\cdot
2^{r}}{2^{r}-1}\right)\cdot\frac{(\alpha/(1-\alpha))^{2}}{(c_{\textsc{jpy}}\cdot
c_{\textsc{adv}}^{2}\cdot
80^{2})^{r}\cdot((r+1)!)^{3}}}_{s_{r}}\cdot\frac{1}{\underbrace{b_{r}\cdot(1-\alpha)}_{1/k_{r}}}$
$\displaystyle=\frac{n_{r}}{b_{r}}\cdot\left(n_{r}\right)\uparrow\left(\frac{1}{2^{r}-1}\right)\cdot\left(1-\alpha\right)\uparrow\left(\frac{r\cdot
2^{r}}{2^{r}-1}-1\right)\cdot\frac{(\alpha/(1-\alpha))^{2}}{(c_{\textsc{jpy}}\cdot
c_{\textsc{adv}}^{2}\cdot 80^{2})^{r}\cdot((r+1)!)^{3}}$
$\displaystyle=n_{r-1}\cdot\left(n_{r}\right)\uparrow\left(\frac{1}{2^{r}-1}\right)\cdot\left(1-\alpha\right)\uparrow\left(\frac{r\cdot
2^{r}}{2^{r}-1}-1\right)\cdot\frac{(\alpha/(1-\alpha))^{2}}{(c_{\textsc{jpy}}\cdot
c_{\textsc{adv}}^{2}\cdot 80^{2})^{r}\cdot((r+1)!)^{3}}$ (as
$n_{r}=n_{r-1}\cdot b_{r}$ by Eq 20)
$\displaystyle=\left(n_{r-1}\right)\uparrow\left(1+\frac{1}{2^{r-1}-1}\right)\cdot\left(1-\alpha\right)\uparrow\left(x\right)\cdot\frac{(\alpha/(1-\alpha))^{2}}{(c_{\textsc{jpy}}\cdot
c_{\textsc{adv}}^{2}\cdot 80^{2})^{r}\cdot((r+1)!)^{3}}.$ (by Eq 23)

where the exponent of $(1-\alpha)$ in the above equation is

$\displaystyle x$ $\displaystyle=\frac{(r-2)\cdot
2^{r-1}+1}{(2^{r}-1)\cdot(2^{r-1}-1)}+\frac{r\cdot 2^{r}}{2^{r}-1}-1$
$\displaystyle=\frac{(r-2)\cdot(2^{r-1}-1)+1+r-2}{(2^{r}-1)\cdot(2^{r-1}-1)}+\frac{(r-1)\cdot
2^{r}+1}{2^{r}-1}$
$\displaystyle=\frac{1}{2^{r}-1}\cdot\left((r-1)2^{r}+1+(r-2)+\frac{r-1}{2^{r-1}-1}\right)$
$\displaystyle=\frac{(r-1)}{2^{r}-1}\cdot(2^{r}+1+\frac{1}{2^{r-1}-1})$
$\displaystyle=\frac{(r-1)}{2^{r}-1}\cdot(\frac{2^{2r-1}-2^{r}+2^{r-1}-1+1}{2^{r-1}-1})$
$\displaystyle=\frac{(r-1)}{2^{r}-1}\cdot(\frac{2^{2r-1}-2^{r-1}}{2^{r-1}-1})$
$\displaystyle=\frac{(r-1)\cdot 2^{r-1}}{2^{r-1}-1}\ .$

Therefore, we have that

$\displaystyle\frac{s_{r}}{k_{r}}$
$\displaystyle=\left(n_{r-1}\right)\uparrow\left(1+\frac{1}{2^{r-1}-1}\right)\cdot\left(1-\alpha\right)\uparrow\left(\frac{(r-1)\cdot
2^{r-1}}{2^{r-1}-1}\right)\cdot\frac{(\alpha/(1-\alpha))^{2}}{(c_{\textsc{jpy}}\cdot
c_{\textsc{adv}}^{2}\cdot 80^{2})^{r}\cdot((r+1)!)^{3}}$
$\displaystyle=s_{r-1}\cdot\frac{1}{c_{\textsc{jpy}}\cdot
c_{\textsc{adv}}^{2}\cdot 80^{2}\cdot(r+1)^{3}}.$

By plugging this back into Eq 21, we obtain

$\displaystyle\textsc{CC}(\pi_{r-1})$
$\displaystyle<c_{\textsc{jpy}}\cdot(40\cdot
c_{\textsc{adv}}\cdot(r+1)^{2}\cdot
r)\cdot\left(s_{r-1}\cdot\frac{1}{c_{\textsc{jpy}}\cdot
c_{\textsc{adv}}^{2}\cdot 80^{2}\cdot(r+1)^{3}}+r\right)$
$\displaystyle\leqslant\frac{1}{c_{\textsc{adv}}^{2}\cdot 160}\cdot
s_{r-1}+40\cdot c_{\textsc{jpy}}\cdot c_{\textsc{adv}}\cdot(r+1)^{4}$ (using
$r\leqslant r+1$) $\displaystyle\leqslant s_{r-1}\ ,$ (as $r^{4}\ll s_{r-1}$
for $r=O(\log\log n)$ and $\alpha\leqslant 1-n_{r}^{-1/2r}$)

which is our desired bound on the communication cost of $\pi_{r-1}$.

To bound the probability of success, we first reiterate the following useful
relation from Eq 20:

$\displaystyle b_{r}^{2}$
$\displaystyle=\left(n_{r}\right)\uparrow\left(\frac{2\cdot
2^{r-1}}{2^{r}-1}\right)\cdot\left(1-\alpha\right)\uparrow\left(\frac{r\cdot
2\cdot 2^{r-1}}{2^{r}-1}-2\right)$
$\displaystyle=\left(n_{r}\right)\uparrow\left(1+\frac{1}{2^{r}-1}\right)\cdot\left(1-\alpha\right)\uparrow\left(\frac{r\cdot
2^{r}}{2^{r}-1}\right)/(1-\alpha)^{2}\ .$ (24)

Using this, we now simplify the term $s_{r}/(2\cdot b_{r}^{2}\cdot\alpha^{2})$
in Eq 22.

$\displaystyle\frac{s_{r}}{2\cdot b_{r}^{2}\cdot\alpha^{2}}$
$\displaystyle=\underbrace{\left(n_{r}\right)\uparrow\left(1+\frac{1}{2^{r}-1}\right)\cdot\left(1-\alpha\right)\uparrow\left(\frac{r\cdot
2^{r}}{2^{r}-1}\right)\cdot\frac{(\alpha/(1-\alpha))^{2}}{(c_{\textsc{jpy}}\cdot
c_{\textsc{adv}}^{2}\cdot
80^{2})^{r}\cdot((r+1)!)^{3}}}_{s_{r}}\cdot\frac{1}{2\cdot
b_{r}^{2}\cdot\alpha^{2}}$
$\displaystyle=\frac{b_{r}^{2}\cdot\alpha^{2}}{(c_{\textsc{jpy}}\cdot
c_{\textsc{adv}}^{2}\cdot 80^{2})^{r}\cdot((r+1)!)^{3}}\cdot\frac{1}{2\cdot
b_{r}^{2}\cdot\alpha^{2}}$ (by Eq 24)
$\displaystyle=\frac{1}{2\cdot(c_{\textsc{jpy}}\cdot c_{\textsc{adv}}^{2}\cdot
80^{2})^{r}\cdot((r+1)!)^{3}}\ .$

By plugging this back into Eq 22, we have that

$\displaystyle\textnormal{suc}(\pi_{r-1})$
$\displaystyle\geqslant\frac{1}{2}\cdot\left(1+\frac{r}{20\cdot
c_{\textsc{adv}}\cdot(r+1)}\right)-\frac{1}{40\cdot
c_{\textsc{adv}}\cdot(r+1)^{2}}-\sqrt{\frac{1}{2\cdot(c_{\textsc{jpy}}\cdot
c_{\textsc{adv}}^{2}\cdot 80^{2})^{r}\cdot((r+1)!)^{3}}}$
$\displaystyle\geqslant\frac{1}{2}\cdot\left(1+\frac{r}{20\cdot
c_{\textsc{adv}}\cdot(r+1)}\right)-\frac{1}{40\cdot
c_{\textsc{adv}}\cdot(r+1)^{2}}-\sqrt{\frac{1}{c_{\textsc{adv}}^{2}\cdot
80^{2}\cdot(r+1)^{4}}}$ (since $c_{\textsc{jpy}}\geqslant 1$ and
$2\cdot((r+1)!)^{3}\geqslant(r+1)^{4}$ for $r\geqslant 1$)
$\displaystyle=\frac{1}{2}\cdot\left(1+\frac{r}{20\cdot
c_{\textsc{adv}}\cdot(r+1)}\right)-\frac{1}{c_{\textsc{adv}}\cdot
80\cdot(r+1)^{2}}$ $\displaystyle=\frac{1}{2}\cdot\left(1+\frac{r}{20\cdot
c_{\textsc{adv}}\cdot(r+1)}-\frac{1}{40\cdot
c_{\textsc{adv}}\cdot(r+1)^{2}}\right)$
$\displaystyle\geqslant\frac{1}{2}\cdot\left(1+\frac{r-1}{20\cdot
c_{\textsc{adv}}\cdot r}\right),$

which is our desired bound.

Overall, we have that the deterministic protocol $\pi_{r-1}$ constructed from
$\pi_{r}$ using Lemma 5.6 contradicts the lemma for $r-1$ (inductive
hypothesis) and thus the lemma must hold for deterministic $r$-round protocols
when the input is sampled from the distribution $\mathcal{D}_{r}$ for every
$r\geqslant 1$. Finally, by the easy direction of Yao’s minmax principle, the
same result holds for any (even randomized) $r$-round protocol for any
instance of $\mathsf{AHM}_{r}$ (given a uniform random search sequence).

#####  5.1.2 The Round Elimination Argument: Proof of Lemma 5.6

We now get to the main part of the argument, which is the proof of Lemma 5.6,
restated below.

######  Lemma 5.6 (restated).

For any $r\geqslant 1$, sufficiently large $n_{r}\in\mathbb{N}$,
$\alpha,\delta\in(0,1)$, and integer $s\geqslant 1$, suppose there exists a
deterministic $r$-round protocol $\pi_{r}$ for
$\mathsf{AHM}_{r}(n_{r},\alpha)$ with

$\textsc{CC}(\pi_{r})\leqslant s$

and probability of success at least $\delta$ when the input is sampled from
$\mathcal{D}_{r}(n_{r},\alpha)$. Then, for any $\varepsilon\in(0,1)$, there
exists a deterministic $(r-1)$-round protocol $\pi_{r-1}$ for
$\mathsf{AHM}_{r-1}$ with

$\textsc{CC}(\pi_{r-1})\leqslant
c_{\textsc{jpy}}\cdot(r/\varepsilon)\cdot\left(\frac{s}{k_{r}}+r\right),$

and probability of success

$\textnormal{suc}(\pi_{r-1})\geqslant\delta-\varepsilon-\sqrt{\frac{s}{2\cdot
b_{r}^{2}\cdot\alpha^{2}}}$

when the players’ input is sampled from $\mathcal{D}_{r-1}(n_{r-1},\alpha)$.

Starting with a deterministic $r$-round protocol $\pi_{r}$ for
$\mathsf{AHM}_{r}(n_{r},\alpha)$ where $\textsc{CC}(\pi_{r})\leqslant s$ and
$\textnormal{suc}(\pi_{r})\geqslant\delta$ under $\mathcal{D}_{r}$ as in the
statement of Lemma 5.6, we construct a deterministic $(r-1)$-round protocol
$\pi_{r-1}$ for $\mathsf{AHM}_{r-1}(n_{r-1},\alpha)$ that proves the lemma in
three steps:

  1. $(i)$

(Input Embedding) Construct a randomized $r$-round protocol $\pi^{(1)}_{r}$
under $\mathcal{D}_{r-1}$ with success probability the same as $\pi_{r}$ under
$\mathcal{D}_{r}$, i.e., $\textnormal{suc}(\pi^{(1)}_{r})\geqslant\delta$, and
internal information cost less than the communication cost of $\pi_{r}$ by a
$k_{r}$ multiplicative factor, i.e.,

$\textsc{IC}(\pi^{(1)}_{r},\mathcal{D}_{r-1})\leqslant\frac{s}{k_{r}}.$

  2. $(ii)$

(Message Compression) Construct a randomized $r$-round protocol
$\pi^{(2)}_{r}$ under $\mathcal{D}_{r-1}$ with success probability less than
that of $\pi^{(1)}_{r}$ under $\mathcal{D}_{r-1}$ by at most an additive
$\varepsilon$ factor, i.e.,
$\textnormal{suc}(\pi^{(2)}_{r})\geqslant\delta-\varepsilon$, and with
communication cost similar to the internal information cost of $\pi^{(1)}_{r}$
under $\mathcal{D}_{r-1}$, i.e.,

$\textsc{CC}(\pi^{(2)}_{r})\leqslant
c_{\textsc{jpy}}\cdot\frac{r}{\varepsilon}\cdot\left(\textsc{IC}(\pi^{(1)}_{r},\mathcal{D}_{r-1})+r\right)\leqslant
c_{\textsc{jpy}}\cdot\frac{r}{\varepsilon}\cdot\left(\frac{s}{k_{r}}+r\right).$

  3. $(iii)$

(Guessing the First Message) Construct a deterministic $(r-1)$-round protocol
$\pi_{r-1}$ under $\mathcal{D}_{r-1}$ with success probability less than that
of $\pi^{(2)}_{r}$ under $\mathcal{D}_{r-1}$ by at most an additive
$\simeq\sqrt{s/(b_{r}^{2}\cdot\alpha^{2})}$ factor, i.e,
$\textnormal{suc}(\pi_{r-1})\geqslant\delta-\varepsilon-\sqrt{s/(2\cdot
b_{r}^{2}\cdot\alpha^{2})}$, and with communication cost no more than that of
$\pi^{(2)}_{r}$, i.e.,

$\textsc{CC}(\pi_{r-1})\leqslant\textsc{CC}(\pi^{(2)}_{r})\leqslant
c_{\textsc{jpy}}\cdot\frac{r}{\varepsilon}\cdot\left(\frac{s}{k_{r}}+r\right).$

##### Step $(i)$: A Low Information Cost Protocol via Input Embedding

We construct a low information cost $r$-round protocol $\pi^{(1)}_{r}$ for
$\mathsf{AHM}_{r-1}$ by considering an input
$(A^{(r-1)},B^{(r-1)})\sim\mathcal{D}_{r-1}(n_{r-1},\alpha)$ and embedding it
in a simulated input instance
$(A^{(r)},B^{(r)})\sim\mathcal{D}_{r}(n_{r},\alpha)$ for $\mathsf{AHM}_{r}$
such that its output can be used to solve $(A^{(r-1)},B^{(r-1)})$. Then, the
players simulate a run of the protocol $\pi_{r}$ in $r$ rounds using the
simulated input.

To simplify the exposition, we disambiguate the players in the construction of
$\pi^{(1)}_{r}$ (and $\pi_{r-1}$ later in step $(iii)$). We use Alice and Bob
to denote the players in the input instance of $\mathsf{AHM}_{r-1}$ where
Alice holds $A^{\star}=A^{(r-1)}$ and Bob holds $B^{\star}=B^{(r-1)}$. On the
other hand, we use ${P}_{X}$ and ${P}_{Y}$ to refer to the players in the
simulated input instance of $\mathsf{AHM}_{r}$ where player ${P}_{X}$ holds
$A^{(r)}=X$ and player ${P}_{Y}$ holds
$B^{(r)}=(\sigma_{\textnormal{{r}}},\sigma_{\textnormal{{c}}},Y)$.

An $r$-round protocol $\pi^{(1)}_{r}$ for $\mathsf{AHM}_{r-1}(n_{r-1},\alpha)$
on input $(A^{\star},B^{\star})\sim\mathcal{D}_{r-1}(n_{r-1},\alpha)$ where
$(k^{\star}_{r-1},k^{\star}_{r-2},\dots,k^{\star}_{1})$ is the given uniform
random search sequence: $(a)$ Using public randomness, independently sample a
uniform random search index $k^{\star}\in[k_{r}]$. Then, jointly sample the
following from $\mathcal{D}_{r}(n_{r},\alpha)$: • The uniform random
permutations $\sigma_{\textnormal{{r}}},\sigma_{\textnormal{{c}}}$ of
$[b_{r}]$; • Bob’s part of all the $k_{r}^{2}-k_{r}$ many off-diagonal sub-
instances
$B^{\textnormal{{off}}}=(B^{(r-1)}_{i,j}:b_{r}\cdot\alpha<\sigma_{\textnormal{{r}}}(i)\neq\sigma_{\textnormal{{c}}}(j)\leqslant
b_{r});$ • Alice’s part of $k^{\star}-1$ many special sub-instances
$A^{\textnormal{{spec}}}_{<k^{\star}}=(A^{\textnormal{{spec}}}_{k}:1\leqslant
k<k^{\star})$; • Bob’s part of $k_{r}-k^{\star}$ many special sub-instances
$B^{\textnormal{{spec}}}_{>k^{\star}}=(B^{\textnormal{{spec}}}_{k}:k^{\star}<k\leqslant
k_{r})$. Let $i^{\star},j^{\star}\in[b_{r}]$ be such that
$\sigma_{\textnormal{{r}}}(i)=\sigma_{\textnormal{{c}}}(j)=b_{r}\cdot\alpha+k^{\star}$,
which both players can compute since
$\sigma_{\textnormal{{r}}},\sigma_{\textnormal{{c}}},k^{\star}$ are sampled
using public randomness. $(b)$ Bob takes on the role of player ${P}_{X}$ and
sets $X[i^{\star},j^{\star}]=B^{\star}$. Bob privately samples $X$ from
$\mathcal{D}_{r}(n_{r},\alpha)$ conditioned on all the random variables from
step $(a)$ and $X[i^{\star},j^{\star}]$, i.e., the remainder of ${P}_{X}$’s
input $A^{(r)}$. $(c)$ Alice takes on the role of player ${P}_{Y}$ and sets
$Y[i^{\star},j^{\star}]=A^{\star}$. Alice privately samples $Y$ from
$\mathcal{D}_{r}(n_{r},\alpha)$ conditioned on all the variables from step
$(a)$ and $Y[i^{\star},j^{\star}]$, i.e., the remainder of player ${P}_{Y}$’s
input $B^{(r)}$. $(d)$ The players ${P}_{X}$ ($=\text{Bob}$) and ${P}_{Y}$
($=\text{Alice}$) simulate a run of protocol $\pi_{r}$ in $r$ rounds using
their respective inputs $A^{(r)}=X$ and
$B^{(r)}=(\sigma_{\textnormal{{r}}},\sigma_{\textnormal{{c}}},Y)$ and starting
with player ${P}_{X}$. $(e)$ At the end of the protocol, the player that
receives the final message gets the uniform random search sequence
$(k^{\star}_{r-1},k^{\star}_{r-2},\ldots,k^{\star}_{0})$ and then returns the
answer of $\pi_{r}$ on the search sequence
$(k^{\star},k^{\star}_{r-1},k^{\star}_{r-2},\ldots,k^{\star}_{0})$.

######  Observation 5.7.

In protocol $\pi^{(1)}_{r}$, $(A^{(r)},B^{(r)})$ in the simulation of
$\pi_{r}$ is sampled from $\mathcal{D}_{r}(n_{r},\alpha)$ and
$(k^{\star},k^{\star}_{r-1},k^{\star}_{r-2},\ldots,k^{\star}_{0})$ is a
uniform random search sequence.

###### Proof.

The input to the simulation of $\pi_{r}$ is $(A^{(r)},B^{(r)})$ where
$A^{(r)}=X$ and
$B^{(r)}=(\sigma_{\textnormal{{r}}},\sigma_{\textnormal{{c}}},Y)$. All
variables of the input are jointly sampled from
$\mathcal{D}_{r}(n_{r},\alpha)$ except for Alice and Bob’s embedded instance
$(A^{\star},B^{\star})\sim\mathcal{D}_{r-1}(n_{r-1},\alpha)$ where
$X[i^{\star},j^{\star}]=B^{\star}$ and $Y[i^{\star},j^{\star}]=A^{\star}$.
Since the instance of $\mathsf{AHM}_{r-1}$ corresponding to
$(X[i^{\star},j^{\star}],Y[i^{\star},j^{\star}])$ is independent of all other
variables in the distribution $\mathcal{D}_{r}(n_{r},\alpha)$, all other
variables are jointly distributed according to
$\mathcal{D}_{r}(n_{r},\alpha)$. It remains to show that
$(X[i^{\star},j^{\star}],Y[i^{\star},j^{\star}])$ distributed according to
$\mathcal{D}_{r-1}(n_{r-1},\alpha)$, which is required in
$\mathcal{D}_{r}(n_{r},\alpha)$. This is immediate from the embedding as
$(X[i^{\star},j^{\star}],Y[i^{\star},j^{\star}])=(A^{\star},B^{\star})\sim\mathcal{D}_{r-1}(n_{r-1},\alpha)$

Each search index in $(k^{\star}_{r-1},k^{\star}_{r-2},\ldots,k^{\star}_{0})$
is uniformly sampled. Then, since $k^{\star}\in[k_{r}]$ is also uniformly
sampled, we have
$(k^{\star},k^{\star}_{r-1},k^{\star}_{r-2},\ldots,k^{\star}_{0})$ is a random
search sequence as required.

With this observation, we have that Alice and Bob have successfully simulated
$\pi_{r}$ for $\mathsf{AHM}_{r}(n_{r},\alpha)$ on the correct distribution, as
the search sequence
$(k^{\star},k^{\star}_{r-1},k^{\star}_{r-2},\ldots,k^{\star}_{0})$ is
uniformly random and the players’ inputs are distributed according to
$\mathcal{D}_{r}(n_{r},\alpha)$. Since the messages communicated by the
players are exactly the messages of the simulated protocol $\pi_{r}$, the
communication cost of $\pi^{(1)}_{r}$ is the same as $\pi_{r}$. Although the
communication cost is large, we now show that its internal information cost
(about input $(A^{\star},B^{\star})$) is smaller by a multiplicative $k_{r}$
factor.

###### Notation.

We use ${\mathsf{A}}^{\star},{\mathsf{B}}^{\star}$ to denote the random
variables corresponding to the input instance of $\mathsf{AHM}_{r-1}$ given to
Alice and Bob, which are distributed according to $\mathcal{D}_{r-1}$. We use
${\mathsf{\Pi}}$ to denote the random variable corresponding to the set of
messages sent by both Alice and Bob. For $i\in[r]$, $\Pi_{i}$ denotes the
message sent in round $i$ and ${\mathsf{\Pi}}_{i}$ denotes the random variable
corresponding to $\Pi_{i}$. We use
${\mathsf{A}}^{\textnormal{{off}}},{\mathsf{B}}^{\textnormal{{off}}},{\mathsf{k}}^{\star},{\mathsf{A}}^{\textnormal{{spec}}},{\mathsf{B}}^{\textnormal{{spec}}}$
to denote the random variables corresponding to
$A^{\textnormal{{off}}},B^{\textnormal{{off}}}$,
$k^{\star},A^{\textnormal{{spec}}}=(A^{\textnormal{{spec}}}_{1},A^{\textnormal{{spec}}}_{2},\ldots,A^{\textnormal{{spec}}}_{k_{r}})$,
$B^{\textnormal{{spec}}}=(B^{\textnormal{{spec}}}_{1},\ldots,B^{\textnormal{{spec}}}_{k_{r}})$,
respectively.

The following claim proves that information cost of $\pi^{(1)}_{r}$ about its
input sampled from $\mathcal{D}_{r-1}$ is $1/k_{r}$ times smaller than the
information cost of $\pi_{r}$ about its own input sampled from
$\mathcal{D}_{r}$.

######  Claim 5.8.

In protocol $\pi^{(1)}_{r}$, we have that

$\textsc{IC}(\pi^{(1)}_{r},\mathcal{D}_{r-1}(n_{r-1},\alpha))\leqslant\frac{1}{k_{r}}\cdot\textsc{IC}(\pi_{r},\mathcal{D}_{r}(n,\alpha)).$

###### Proof.

By the definition of internal information cost (3.11),

$\displaystyle\begin{split}\textsc{IC}(\pi^{(1)}_{r},\mathcal{D}_{r-1}(n_{r-1},\alpha))&=\mathbb{I}({\mathsf{A}}^{\star}\,;{\mathsf{\Pi}}\mid\underbrace{\bm{\sigma}_{\textnormal{{r}}},\bm{\sigma}_{\textnormal{{c}}},{\mathsf{B}}^{\textnormal{{off}}},{\mathsf{k}}^{\star},{\mathsf{B}}^{\textnormal{{spec}}}_{>{\mathsf{k}}^{\star}},{\mathsf{A}}^{\textnormal{{spec}}}_{<{\mathsf{k}}^{\star}}}_{\text{public
randomness of $\pi^{(1)}_{r}$}},{\mathsf{B}}^{\star})\\\ &\hskip
14.22636pt+\mathbb{I}({\mathsf{B}}^{\star}\,;{\mathsf{\Pi}}\mid\underbrace{\bm{\sigma}_{\textnormal{{r}}},\bm{\sigma}_{\textnormal{{c}}},{\mathsf{B}}^{\textnormal{{off}}},{\mathsf{k}}^{\star},{\mathsf{B}}^{\textnormal{{spec}}}_{>{\mathsf{k}}^{\star}},{\mathsf{A}}^{\textnormal{{spec}}}_{<{\mathsf{k}}^{\star}}}_{\text{public
randomness $\pi^{(1)}_{r}$}},{\mathsf{A}}^{\star}).\end{split}$ (25)

Each mutual information term corresponds to the amount of information
communicated by each player about their input, and we bound them separately.

For Alice’s mutual information term in Eq 25, we have that

$\displaystyle\mathbb{I}({\mathsf{A}}^{\star}\,;{\mathsf{\Pi}}\mid\bm{\sigma}_{\textnormal{{r}}},\bm{\sigma}_{\textnormal{{c}}},{\mathsf{B}}^{\textnormal{{off}}},{\mathsf{k}}^{\star},{\mathsf{B}}^{\textnormal{{spec}}}_{>{\mathsf{k}}^{\star}},{\mathsf{A}}^{\textnormal{{spec}}}_{<{\mathsf{k}}^{\star}},{\mathsf{B}}^{\star})$
$\displaystyle=\frac{1}{k_{r}}\cdot\sum_{k\in[k_{r}]}\mathbb{I}({\mathsf{A}}^{\star}\,;{\mathsf{\Pi}}\mid\bm{\sigma}_{\textnormal{{r}}},\bm{\sigma}_{\textnormal{{c}}},{\mathsf{B}}^{\textnormal{{off}}},{\mathsf{k}}^{\star}=k,{\mathsf{B}}^{\textnormal{{spec}}}_{>k},{\mathsf{A}}^{\textnormal{{spec}}}_{<k},{\mathsf{B}}^{\star})$
(by the definition of conditional mutual information and the uniform
distribution of ${\mathsf{k}}^{\star}$)
$\displaystyle=\frac{1}{k_{r}}\cdot\sum_{k\in[k_{r}]}\mathbb{I}({\mathsf{A}}^{\textnormal{{spec}}}_{k}\,;{\mathsf{\Pi}}\mid\bm{\sigma}_{\textnormal{{r}}},\bm{\sigma}_{\textnormal{{c}}},{\mathsf{B}}^{\textnormal{{off}}},{\mathsf{k}}^{\star}=k,{\mathsf{B}}^{\textnormal{{spec}}}_{\geqslant
k},{\mathsf{A}}^{\textnormal{{spec}}}_{<k})$ (as
${\mathsf{A}}^{\star}={\mathsf{A}}^{\textnormal{{spec}}}_{k},{\mathsf{B}}^{\star}={\mathsf{B}}^{\textnormal{{spec}}}_{k}$
in protocol $\pi^{(1)}_{r}$ when ${\mathsf{k}}^{\star}=k$)
$\displaystyle=\frac{1}{k_{r}}\cdot\sum_{k\in[k_{r}]}\mathbb{I}({\mathsf{A}}^{\textnormal{{spec}}}_{k}\,;{\mathsf{\Pi}}\mid\bm{\sigma}_{\textnormal{{r}}},\bm{\sigma}_{\textnormal{{c}}},{\mathsf{B}}^{\textnormal{{off}}},{\mathsf{B}}^{\textnormal{{spec}}}_{\geqslant
k},{\mathsf{A}}^{\textnormal{{spec}}}_{<k});$

the last part holds because the joint distribution of
$({\mathsf{A}}^{\textnormal{{spec}}}_{\leqslant
k},{\mathsf{B}}^{\textnormal{{spec}}}_{\geqslant
k},\bm{\sigma}_{\textnormal{{r}}},\bm{\sigma}_{\textnormal{{c}}},{\mathsf{B}}^{\textnormal{{off}}},\Pi)$
is independent of the value of ${\mathsf{k}}^{\star}$. In particular, if we
sample any input $(A^{(r)},B^{(r)})$ from $\mathcal{D}_{r}(n,\alpha)$ (which
does not include $k^{\star}=k^{\star}_{r}$), the values of
$\bm{\sigma}_{\textnormal{{r}}},\bm{\sigma}_{\textnormal{{c}}},{\mathsf{B}}^{\textnormal{{off}}},{\mathsf{A}}^{\textnormal{{spec}}}_{\leqslant
k},{\mathsf{B}}^{\textnormal{{spec}}}_{\geqslant k}$ are fixed and the value
of ${\mathsf{\Pi}}$ is also fixed as $\pi_{r}$ is deterministic. Hence, the
distribution of ${\mathsf{k}}^{\star}$ remains uniform over $[k_{r}]$
irrespective of the instance $(A^{(r)},B^{(r)})$. Continuing the bounding of
Alice’s mutual information term, we have that

$\displaystyle\frac{1}{k_{r}}\cdot\sum_{k\in[k_{r}]}\mathbb{I}({\mathsf{A}}^{\textnormal{{spec}}}_{k}\,;{\mathsf{\Pi}}\mid\bm{\sigma}_{\textnormal{{r}}},\bm{\sigma}_{\textnormal{{c}}},{\mathsf{B}}^{\textnormal{{off}}},{\mathsf{B}}^{\textnormal{{spec}}}_{\geqslant
k},{\mathsf{A}}^{\textnormal{{spec}}}_{<k})$ $\displaystyle\hskip
20.0pt\leqslant\frac{1}{k_{r}}\cdot\sum_{k\in[k_{r}]}\mathbb{I}({\mathsf{A}}^{\textnormal{{spec}}}_{k}\,;{\mathsf{\Pi}}\mid\bm{\sigma}_{\textnormal{{r}}},\bm{\sigma}_{\textnormal{{c}}},{\mathsf{B}}^{\textnormal{{off}}},{\mathsf{B}}^{\textnormal{{spec}}},{\mathsf{A}}^{\textnormal{{spec}}}_{<k})$
(by Proposition A.2 as
${\mathsf{B}}^{\textnormal{{spec}}}_{<k}\perp{\mathsf{A}}^{\textnormal{{spec}}}_{k}\mid\bm{\sigma}_{\textnormal{{r}}},\bm{\sigma}_{\textnormal{{c}}},{\mathsf{B}}^{\textnormal{{off}}},{\mathsf{A}}^{\textnormal{{spec}}}_{<k}$
by the definition of distribution $\mathcal{D}_{r}$) $\displaystyle\hskip
20.0pt=\frac{1}{k_{r}}\cdot\mathbb{I}({\mathsf{A}}^{\textnormal{{spec}}}\,;{\mathsf{\Pi}}\mid\bm{\sigma}_{\textnormal{{r}}},\bm{\sigma}_{\textnormal{{c}}},{\mathsf{B}}^{\textnormal{{off}}},{\mathsf{B}}^{\textnormal{{spec}}})$
(by the chain rule of mutual information, A.1-(4)) $\displaystyle\hskip
20.0pt\leqslant\frac{1}{k_{r}}\cdot\mathbb{I}({\mathsf{A}}^{\textnormal{{spec}}}\,;{\mathsf{\Pi}}\mid\bm{\sigma}_{\textnormal{{r}}},\bm{\sigma}_{\textnormal{{c}}},{\mathsf{B}}^{\textnormal{{off}}},{\mathsf{B}}^{\textnormal{{spec}}},{\mathsf{B}}^{\textnormal{{rest}}})$
(by Proposition A.2, as
${\mathsf{A}}^{\textnormal{{spec}}}\perp{\mathsf{B}}^{\textnormal{{rest}}}\mid{\mathsf{B}}^{\textnormal{{spec}}},\bm{\sigma}_{\textnormal{{r}}},\bm{\sigma}_{\textnormal{{c}}},{\mathsf{B}}^{\textnormal{{off}}}$
by the definition of distribution $\mathcal{D}_{r}$) $\displaystyle\hskip
20.0pt=\frac{1}{k_{r}}\cdot\mathbb{I}({\mathsf{A}}^{\textnormal{{spec}}},{\mathsf{B}}^{\textnormal{{off}}}\,;{\mathsf{\Pi}}\mid\bm{\sigma}_{\textnormal{{r}}},\bm{\sigma}_{\textnormal{{c}}},{\mathsf{B}}^{\textnormal{{off}}},{\mathsf{B}}^{\textnormal{{spec}}},{\mathsf{B}}^{\textnormal{{rest}}})$
(as ${\mathsf{B}}^{\textnormal{{off}}}$ is fixed) $\displaystyle\hskip
20.0pt\leqslant\frac{1}{k_{r}}\cdot\mathbb{I}({\mathsf{A}}^{\textnormal{{spec}}},{\mathsf{A}}^{\textnormal{{off}}},{\mathsf{B}}^{\textnormal{{off}}},\bm{\sigma}_{\textnormal{{r}}},\bm{\sigma}_{\textnormal{{c}}}\,;{\mathsf{\Pi}}\mid{\mathsf{B}}^{\textnormal{{off}}},{\mathsf{B}}^{\textnormal{{spec}}},{\mathsf{B}}^{\textnormal{{rest}}})$
(by the chain rule (A.1-(4)) and non-negativity of mutual information
(A.1-(2))) $\displaystyle\hskip
20.0pt=\frac{1}{k_{r}}\cdot\mathbb{I}({\mathsf{B}}^{(r)}\,;{\mathsf{\Pi}}\mid{\mathsf{A}}^{(r)}).$
(recall that input of ${P}_{Y}$ (resp. ${P}_{X}$) simulated by Alice (resp.
Bob) in $\pi^{(1)}_{r}$ is $B^{(r)}$ (resp. $A^{(r)}$))

For Bob’s mutual information term in Eq 25, following a similar argument, we
have

$\displaystyle\mathbb{I}({\mathsf{B}}^{\star}\,;{\mathsf{\Pi}}\mid\bm{\sigma}_{\textnormal{{r}}},\bm{\sigma}_{\textnormal{{c}}},{\mathsf{B}}^{\textnormal{{off}}},{\mathsf{k}}^{\star},{\mathsf{B}}^{\textnormal{{spec}}}_{>{\mathsf{k}}^{\star}},{\mathsf{A}}^{\textnormal{{spec}}}_{<{\mathsf{k}}^{\star}},{\mathsf{A}}^{\star})$
$\displaystyle=\frac{1}{k_{r}}\cdot\sum_{k\in[k_{r}]}\mathbb{I}({\mathsf{B}}^{\textnormal{{spec}}}_{k}\,;{\mathsf{\Pi}}\mid\bm{\sigma}_{\textnormal{{r}}},\bm{\sigma}_{\textnormal{{c}}},{\mathsf{B}}^{\textnormal{{off}}},{\mathsf{k}}^{\star}=k,{\mathsf{B}}^{\textnormal{{spec}}}_{>k},{\mathsf{A}}^{\textnormal{{spec}}}_{\leqslant
k})$ (by definition of conditional mutual information and
${\mathsf{A}}^{\star},{\mathsf{B}}^{\star}$ and the uniform distribution of
${\mathsf{k}}^{\star}$)
$\displaystyle=\frac{1}{k_{r}}\cdot\sum_{k\in[k_{r}]}\mathbb{I}({\mathsf{B}}^{\textnormal{{spec}}}_{k}\,;{\mathsf{\Pi}}\mid\bm{\sigma}_{\textnormal{{r}}},\bm{\sigma}_{\textnormal{{c}}},{\mathsf{B}}^{\textnormal{{off}}},{\mathsf{B}}^{\textnormal{{spec}}}_{>k},{\mathsf{A}}^{\textnormal{{spec}}}_{\leqslant
k})$ (as in the previous case for Alice, for any $k\in[k_{r}]$,
$({\mathsf{k}}^{\star}=k)\perp({\mathsf{B}}^{\textnormal{{spec}}}_{\geqslant
k},{\mathsf{A}}^{\textnormal{{spec}}}_{\leqslant
k},\bm{\sigma}_{\textnormal{{r}}},\bm{\sigma}_{\textnormal{{c}}},{\mathsf{B}}^{\textnormal{{off}}})$)
$\displaystyle\leqslant\frac{1}{k_{r}}\cdot\sum_{k\in[k_{r}]}\mathbb{I}({\mathsf{B}}^{\textnormal{{spec}}}_{k}\,;{\mathsf{\Pi}}\mid\bm{\sigma}_{\textnormal{{r}}},\bm{\sigma}_{\textnormal{{c}}},{\mathsf{B}}^{\textnormal{{off}}},{\mathsf{B}}^{\textnormal{{spec}}}_{>k},{\mathsf{A}}^{\textnormal{{spec}}})$
(by Proposition A.2, as
${\mathsf{A}}^{\textnormal{{spec}}}_{>k}\perp{\mathsf{B}}^{\textnormal{{spec}}}_{k}\mid\bm{\sigma}_{\textnormal{{r}}},\bm{\sigma}_{\textnormal{{c}}},{\mathsf{B}}^{\textnormal{{off}}},{\mathsf{B}}^{\textnormal{{spec}}}_{>k}$
by the definition of distribution $\mathcal{D}_{r}$)
$\displaystyle=\frac{1}{k_{r}}\cdot\mathbb{I}({\mathsf{B}}^{\textnormal{{spec}}}\,;{\mathsf{\Pi}}\mid\bm{\sigma}_{\textnormal{{r}}},\bm{\sigma}_{\textnormal{{c}}},{\mathsf{B}}^{\textnormal{{off}}},{\mathsf{A}}^{\textnormal{{spec}}})$
(by chain rule of mutual information, A.1-(4))
$\displaystyle\leqslant\frac{1}{k_{r}}\cdot\mathbb{I}({\mathsf{B}}^{\textnormal{{spec}}}\,;{\mathsf{\Pi}}\mid\bm{\sigma}_{\textnormal{{r}}},\bm{\sigma}_{\textnormal{{c}}},{\mathsf{A}}^{\textnormal{{off}}},{\mathsf{B}}^{\textnormal{{off}}},{\mathsf{A}}^{\textnormal{{spec}}})$
(by Proposition A.2, as
${\mathsf{A}}^{\textnormal{{off}}}\perp{\mathsf{B}}^{\textnormal{{spec}}}\mid\bm{\sigma}_{\textnormal{{r}}},\bm{\sigma}_{\textnormal{{c}}},{\mathsf{B}}^{\textnormal{{off}}},{\mathsf{A}}^{\textnormal{{spec}}}$
by the definition of distribution $\mathcal{D}_{r}$)
$\displaystyle\leqslant\frac{1}{k_{r}}\cdot\mathbb{I}({\mathsf{B}}^{\textnormal{{spec}}},{\mathsf{B}}^{\textnormal{{off}}},{\mathsf{B}}^{\textnormal{{rest}}}\,;{\mathsf{\Pi}}\mid\bm{\sigma}_{\textnormal{{r}}},\bm{\sigma}_{\textnormal{{c}}},{\mathsf{A}}^{\textnormal{{off}}},{\mathsf{B}}^{\textnormal{{off}}},{\mathsf{A}}^{\textnormal{{spec}}})$
(by the chain rule (A.1-(4)) and non-negativity of mutual information
(A.1-(2)))
$\displaystyle=\frac{1}{k_{r}}\cdot\mathbb{I}({\mathsf{A}}^{(r)}\,;{\mathsf{\Pi}}\mid{\mathsf{B}}^{(r)}).$
(recall that input of ${P}_{X}$ (resp. ${P}_{Y}$) simulated by Bob (resp.
Alice) in $\pi^{(1)}_{r}$ is $A^{(r)}$ (resp. $B^{(r)}$))

With both these bounds, we can upper bound the LHS of Eq 25 and obtain

$\displaystyle\textsc{IC}(\pi^{(1)}_{r},\mathcal{D}_{r-1})$
$\displaystyle\leqslant\frac{1}{k_{r}}\cdot\left(\mathbb{I}({\mathsf{B}}^{(r)}\,;{\mathsf{\Pi}}\mid{\mathsf{A}}^{(r)})+\mathbb{I}({\mathsf{A}}^{(r)}\,;{\mathsf{\Pi}}\mid{\mathsf{B}}^{(r)})\right)$
$\displaystyle=\frac{1}{k_{r}}\cdot\textsc{IC}(\pi_{r},\mathcal{D}_{r}),$

where the last step follows since the messages communicated in $\pi^{(1)}_{r}$
are exactly the messages communicated in the simulation of $\pi_{r}$ and since
$({\mathsf{A}}^{(r)},{\mathsf{B}}^{(r)})\sim\mathcal{D}_{r}$ in
$\pi^{(1)}_{r}$ by 5.7.

We now obtain the following main lemma of this step of the argument:

######  Lemma 5.9.

Protocol $\pi^{(1)}_{r}$ is an $r$-round protocol for
$\mathsf{AHM}_{r-1}(n_{r-1},\alpha)$ where Bob speaks first with communication
cost at most $s$, probability of success at least $\delta$, and internal
information cost at most $s/k_{r}$ when the input is sampled from
$\mathcal{D}_{r-1}(n_{r-1},\alpha)$.

###### Proof.

In protocol $\pi^{(1)}_{r}$, the instance $(A^{(r)},B^{(r)})$ used to simulate
$\pi_{r}$ is constructed without any communication, so the total number of
bits communicated in $\pi^{(1)}_{r}$ is at most the total number of bits
communicated in $\pi_{r}$, which is $\textsc{CC}(\pi_{r})\leqslant s$ as in
the statement of Lemma 5.6. Bob takes on the role of ${P}_{X}$ in the
simulation and thus Bob speaks first.

By construction, protocol $\pi^{(1)}_{r}$ outputs the same answer as $\pi_{r}$
since the solution to $(A^{(r)},B^{(r)})\sim\mathcal{D}_{r}$ on search
sequence $(k^{\star},k^{\star}_{r-1},k^{\star}_{r-2},\ldots,k^{\star}_{0})$ is
the same as the solution to the input
$(A^{\textnormal{{spec}}}_{k^{\star}},B^{\textnormal{{spec}}}_{k^{\star}})=(A^{\star},B^{\star})\sim\mathcal{D}_{r-1}$
on the search sequence
$(k^{\star}_{r-1},k^{\star}_{r-2},\ldots,k^{\star}_{0})$. Therefore,
$\pi^{(1)}_{r}$ succeeds with probability at least $\delta$. Finally, the
bound on the internal information cost of $\pi^{(1)}_{r}$ follows from Claim
5.8 and the fact that the communication cost of $\pi_{r}$, namely, $s$, is an
upper bound of its internal information cost.

##### Step $(ii)$: A Low Communication Cost Protocol via Message Compression

In this step, we compress the communication cost of $\pi^{(1)}_{r}$ using
standard message compression techniques. As a direct corollary of Proposition
3.13, we get the following:

######  Corollary 5.10.

For any $0<\varepsilon<1$, there exists an $r$-round protocol $\pi^{(2)}_{r}$
for $\mathsf{AHM}_{r-1}(n_{r-1},\alpha)$ where Bob speaks first with

$\textsc{CC}(\pi^{(2)}_{r})\leqslant
c_{\textsc{jpy}}\cdot(r/\varepsilon)\cdot\left(\frac{s}{k_{r}}+r\right).$

and probability of success at least $\delta-\varepsilon$ when the input is
sampled from $\mathcal{D}_{r-1}(n_{r-1},\alpha)$.

###### Proof.

We use Proposition 3.13 on protocol $\pi^{(1)}_{r}$ to get protocol
$\pi^{(2)}_{r}$ such that the simulation fails with probability at most
$\varepsilon$. Then, we have that

$\displaystyle\textsc{CC}(\pi^{(2)}_{r})$ $\displaystyle\leqslant
c_{\textsc{jpy}}\cdot\left(r/\varepsilon\cdot\textsc{IC}(\pi^{(1)}_{r},\mathcal{D}_{r-1})+r^{2}/\varepsilon\right)\leqslant
c_{\textsc{jpy}}\cdot(r/\varepsilon)\cdot\left(\frac{s}{k_{r}}+r\right).$ (by
Lemma 5.9)

The simulation of $\pi^{(1)}_{r}$ using compressed messages fails with
probability at most $\varepsilon$, so $\pi^{(2)}_{r}$ succeeds with
probability at least $\delta-\varepsilon$, as desired.

Since this step only compresses the messages sent in $\pi^{(1)}_{r}$, protocol
$\pi^{(2)}_{r}$ is constructed in the same way as $\pi^{(1)}_{r}$ with an
additional message compression step that uses an independent source of public
randomness. In particular, $\pi^{(2)}_{r}$ is a simulation of $\pi_{r}$ on an
instance of $\mathsf{AHM}_{r}$ sampled from $\mathcal{D}_{r}$, but with
communication cost smaller by a $\simeq k_{r}$ multiplicative factor and with
a slightly smaller probability of success.

##### Step $(iii)$: An $(r-1)$-Round Protocol via Guessing the First Message

In this final and the most important step, we take the $r$-round protocol
$\pi^{(2)}_{r}$ for $\mathsf{AHM}_{r-1}$ where Bob communicates first and we
eliminate the first message by making the players _guess_ it using public
randomness, thus beginning the protocol from the second round. Therefore, we
obtain an $(r-1)$-round protocol $\pi_{r-1}$ for $\mathsf{AHM}_{r-1}$ where
Alice communicates first as required. This alters the joint distribution of
the input and thus affects the guarantees of the protocol (as in Corollary
5.10), but we will show that the effect is small.

An $(r-1)$-round protocol $\pi_{r-1}$ for $\mathsf{AHM}_{r-1}$ on inputs
$(A^{(r-1)},B^{(r-1)})\sim\mathcal{D}_{r-1}(n_{r-1},\alpha)$ where
$(k^{\star}_{r-1},k^{\star}_{r-2},\dots,k^{\star}_{1})$ is the given uniform
random search sequence: $(a)$ Using public randomness, jointly sample the
first message $\Pi_{1}$ and the search index $k^{\star}$ from the protocol
$\pi^{(2)}_{r}$. Then, jointly sample the following from
$\mathcal{D}_{r}(n_{r},\alpha)$ conditioned on $\Pi_{1},k^{\star}$: • The
uniform random permutations
$\sigma_{\textnormal{{r}}},\sigma_{\textnormal{{c}}}$ of $[b_{r}]$; • Bob’s
part of all the $k_{r}^{2}-k_{r}$ many off-diagonal sub-instances
$B^{\textnormal{{off}}}=(B^{(r-1)}_{i,j}:b_{r}\cdot\alpha<\sigma_{\textnormal{{r}}}(i)\neq\sigma_{\textnormal{{c}}}(j)\leqslant
b_{r});$ • Alice’s part of the $k^{\star}-1$ many special sub-instances
$A^{\textnormal{{spec}}}_{<k^{\star}}=(A^{\textnormal{{spec}}}_{k}:1\leqslant
k<k^{\star})$; • Bob’s part of the $k_{r}-k^{\star}$ many special sub-
instances
$B^{\textnormal{{spec}}}_{>k^{\star}}=(B^{\textnormal{{spec}}}_{k}:k^{\star}<k\leqslant
k_{r})$. Let $i^{\star},j^{\star}\in[b_{r}]$ be such that
$\sigma_{\textnormal{{r}}}(i)=\sigma_{\textnormal{{c}}}(j)=b_{r}\cdot\alpha+k^{\star}$,
which both players can compute since
$\sigma_{\textnormal{{r}}},\sigma_{\textnormal{{c}}},k^{\star}$ are sampled
using public randomness. $(b)$ Bob takes on the role of player ${P}_{X}$ and
sets $X[i^{\star},j^{\star}]=B^{\star}$. Bob privately samples $X$ from
$\mathcal{D}_{r}(n_{r},\alpha)$ conditioned on all the random variables from
step $(a)$ and $X[i^{\star},j^{\star}]$, i.e., the remainder of ${P}_{X}$’s
input $A^{(r)}$. $(c)$ Alice takes on the role of player ${P}_{Y}$ and sets
$Y[i^{\star},j^{\star}]=A^{\star}$. Alice privately samples $Y$ from
$\mathcal{D}_{r}(n_{r},\alpha)$ conditioned on all the variables from step
$(a)$ and $Y[i^{\star},j^{\star}]$, i.e., the remainder of player ${P}_{Y}$’s
input $B^{(r)}$. $(d)$ The players ${P}_{X}$ ($=\text{Bob}$) and ${P}_{Y}$
($=\text{Alice}$) simulate protocol $\pi^{(2)}_{r}$ using their respective
inputs
$A^{(r)}=X,B^{(r)}=(\sigma_{\textnormal{{r}}},\sigma_{\textnormal{{c}}},Y)$
and the search sequence
$(k^{\star},k^{\star}_{r-1},k^{\star}_{r-2},\dots,k^{\star}_{1})$. They use
$\Pi_{1}$ as a guess of the first message sent from ${P}_{X}$ to ${P}_{Y}$ and
thus only simulate $r-1$ rounds of $\pi^{(2)}_{r}$ starting with the second
round, i.e., player ${P}_{Y}$ communicates first.

Observe that, similar to the construction of $\pi^{(2)}_{r}$ (which is
identical to $\pi^{(1)}_{r}$, except for the message compression), protocol
$\pi_{r-1}$ embeds the input for $\mathsf{AHM}_{r-1}$ sampled from
$\mathcal{D}_{r-1}$ into a simulated instance $(A^{(r)},B^{(r)})$ of
$\mathsf{AHM}_{r}$. Then, the players simulate a run of $\pi^{(2)}_{r}$ using
$(A^{(r)},B^{(r)})$ where, to remove the first round of communication, the
first message is guessed using public randomness. However, due to the random
guessing of the first message, the simulated instance is no longer distributed
according to $\mathcal{D}_{r}(n_{r},\alpha)$ (recall 5.7), i.e., the
guarantees of $\pi^{(2)}_{r}$ do not hold for $\pi_{r-1}$. Despite this, we
show that the simulated instance and first message are statistically close to
being distributed as they are in $\pi^{(2)}_{r}$ and thus similar guarantees
hold.

Let $\mathcal{D}^{\textnormal{{fake}}}$ denote the joint distribution of
$({\mathsf{A}}^{(r)},{\mathsf{B}}^{(r)},{\mathsf{\Pi}}_{1},{\mathsf{k}}^{\star})$
as it is in $\pi_{r-1}$ and let $\mathcal{D}^{\textnormal{{real}}}$ denote the
joint distribution of
$({\mathsf{A}}^{(r)},{\mathsf{B}}^{(r)},{\mathsf{\Pi}}_{1},{\mathsf{k}}^{\star})$
as it is in $\pi^{(2)}_{r}$. Let

${\mathsf{R}}_{a}:=({\mathsf{\Pi}}_{1},\bm{\sigma}_{\textnormal{{r}}},\bm{\sigma}_{\textnormal{{c}}},{\mathsf{B}}^{\textnormal{{off}}},{\mathsf{k}}^{\star},{\mathsf{B}}^{\textnormal{{spec}}}_{>{\mathsf{k}}^{\star}},{\mathsf{A}}^{\textnormal{{spec}}}_{<{\mathsf{k}}^{\star}})$

denote the public randomness used in step $(a)$ of $\pi_{r-1}$. We show in
Claim 5.11 that the distributions $\mathcal{D}^{\textnormal{{fake}}}$ and
$\mathcal{D}^{\textnormal{{real}}}$ only differ in the way that the input
$({\mathsf{A}}^{\star},{\mathsf{B}}^{\star})=({\mathsf{A}}^{\textnormal{{spec}}}_{{\mathsf{k}}^{\star}},{\mathsf{B}}^{\textnormal{{spec}}}_{{\mathsf{k}}^{\star}})$
is sampled.

######  Claim 5.11.

We have that

$\displaystyle\mathcal{D}^{\textnormal{{fake}}}$
$\displaystyle=\textnormal{dist}({\mathsf{R}}_{a})\times~{}~{}~{}\textnormal{dist}({\mathsf{A}}^{\textnormal{{spec}}}_{{\mathsf{k}}^{\star}},{\mathsf{B}}^{\textnormal{{spec}}}_{{\mathsf{k}}^{\star}})~{}~{}~{}\\!\times\textnormal{dist}({\mathsf{A}}^{\textnormal{{off}}},{\mathsf{A}}^{\textnormal{{spec}}}_{>{\mathsf{k}}^{\star}}\mid{\mathsf{R}}_{a},{\mathsf{A}}^{\textnormal{{spec}}}_{{\mathsf{k}}^{\star}})\times\textnormal{dist}({\mathsf{B}}^{\textnormal{{rest}}},{\mathsf{B}}^{\textnormal{{spec}}}_{<{\mathsf{k}}^{\star}}\mid{\mathsf{R}}_{a},{\mathsf{B}}^{\textnormal{{spec}}}_{{\mathsf{k}}^{\star}}),$
$\displaystyle\mathcal{D}^{\textnormal{{real}}}$
$\displaystyle=\textnormal{dist}({\mathsf{R}}_{a})\times\textnormal{dist}({\mathsf{A}}^{\textnormal{{spec}}}_{{\mathsf{k}}^{\star}},{\mathsf{B}}^{\textnormal{{spec}}}_{{\mathsf{k}}^{\star}}\mid{\mathsf{R}}_{a})\times\textnormal{dist}({\mathsf{A}}^{\textnormal{{off}}},{\mathsf{A}}^{\textnormal{{spec}}}_{>{\mathsf{k}}^{\star}}\mid{\mathsf{R}}_{a},{\mathsf{A}}^{\textnormal{{spec}}}_{{\mathsf{k}}^{\star}})\times\textnormal{dist}({\mathsf{B}}^{\textnormal{{rest}}},{\mathsf{B}}^{\textnormal{{spec}}}_{<{\mathsf{k}}^{\star}}\mid{\mathsf{R}}_{a},{\mathsf{B}}^{\textnormal{{spec}}}_{{\mathsf{k}}^{\star}}).$

###### Proof.

We first consider
$({\mathsf{A}}^{(r)},{\mathsf{B}}^{(r)},{\mathsf{\Pi}}_{1},{\mathsf{k}}^{\star})$
directly as it is sampled in $\pi_{r-1}$. The random variable
${\mathsf{R}}_{a}$ in $\pi_{r-1}$ is jointly sampled in step $(a)$. Then,
Alice and Bob embed
$({\mathsf{A}}^{\star},{\mathsf{B}}^{\star})\sim\mathcal{D}_{r-1}$ as
${\mathsf{A}}^{\textnormal{{spec}}}_{{\mathsf{k}}^{\star}}={\mathsf{A}}^{\star}$
and
${\mathsf{B}}^{\textnormal{{spec}}}_{{\mathsf{k}}^{\star}}={\mathsf{B}}^{\star}$,
i.e.,
$({\mathsf{A}}^{\textnormal{{spec}}}_{{\mathsf{k}}^{\star}},{\mathsf{B}}^{\textnormal{{spec}}}_{{\mathsf{k}}^{\star}})\sim\mathcal{D}_{r-1}$,
which is _not_ conditioned on ${\mathsf{R}}_{a}$. Finally, Bob and Alice
privately sample the remainder of $X$ and $Y$ (and thus the remainder of
$A^{(r)}$ and $B^{(r)}$), respectively, which is only conditioned on
${\mathsf{R}}_{a}$ and their respective embedded inputs. This defines
$\mathcal{D}^{\textnormal{{fake}}}$.

We then obtain $\mathcal{D}^{\textnormal{{real}}}$ from
$\mathcal{D}^{\textnormal{{fake}}}$ by including all previously sampled random
variables in the conditioning of the subsequently sampled random variables.
That is, we obtain

$\displaystyle\mathcal{D}^{\textnormal{{real}}}$
$\displaystyle=\textnormal{dist}({\mathsf{R}}_{a})$
$\displaystyle\times\textnormal{dist}({\mathsf{A}}^{\textnormal{{spec}}}_{{\mathsf{k}}^{\star}},{\mathsf{B}}^{\textnormal{{spec}}}_{{\mathsf{k}}^{\star}}\mid{\mathsf{R}}_{a})$
$\displaystyle\times\textnormal{dist}({\mathsf{A}}^{\textnormal{{off}}},{\mathsf{A}}^{\textnormal{{spec}}}_{>{\mathsf{k}}^{\star}}\mid{\mathsf{R}}_{a},{\mathsf{A}}^{\textnormal{{spec}}}_{{\mathsf{k}}^{\star}},{\mathsf{B}}^{\textnormal{{spec}}}_{{\mathsf{k}}^{\star}})$
$\displaystyle\times\textnormal{dist}({\mathsf{B}}^{\textnormal{{rest}}},{\mathsf{B}}^{\textnormal{{spec}}}_{<{\mathsf{k}}^{\star}}\mid{\mathsf{R}}_{a},{\mathsf{B}}^{\textnormal{{spec}}}_{{\mathsf{k}}^{\star}},{\mathsf{A}}^{\textnormal{{off}}},{\mathsf{A}}^{\textnormal{{spec}}}_{\geqslant{\mathsf{k}}^{\star}}).$

It is easy to verify that this is exactly the distribution of
$({\mathsf{A}}^{(r)},{\mathsf{B}}^{(r)},{\mathsf{\Pi}}_{1},{\mathsf{k}}^{\star})$
as it is in $\pi^{(2)}_{r}$.

Finally, we simplify the third and fourth terms in
$\mathcal{D}^{\textnormal{{real}}}$ to show that they are identical to the
corresponding terms in $\mathcal{D}^{\textnormal{{fake}}}$, which follows
directly from the claims that

$({\mathsf{A}}^{\textnormal{{off}}},{\mathsf{A}}^{\textnormal{{spec}}}_{>{\mathsf{k}}^{\star}})\perp{\mathsf{B}}^{\textnormal{{spec}}}_{{\mathsf{k}}^{\star}}\mid{\mathsf{R}}_{a},{\mathsf{A}}^{\textnormal{{spec}}}_{{\mathsf{k}}^{\star}}\quad\text{and}\quad{\mathsf{B}}^{\textnormal{{spec}}}_{<{\mathsf{k}}^{\star}},{\mathsf{B}}^{\textnormal{{rest}}}\perp{\mathsf{A}}^{\textnormal{{off}}},{\mathsf{A}}^{\textnormal{{spec}}}_{\geqslant{\mathsf{k}}^{\star}}\mid{\mathsf{R}}_{a},{\mathsf{B}}^{\textnormal{{spec}}}_{{\mathsf{k}}^{\star}},$

respectively. To prove these claims, it is sufficient to bound the
corresponding mutual information terms as follows:

$\displaystyle\mathbb{I}({\mathsf{A}}^{\textnormal{{off}}},{\mathsf{A}}^{\textnormal{{spec}}}_{>{\mathsf{k}}^{\star}}\,;{\mathsf{B}}^{\textnormal{{spec}}}_{{\mathsf{k}}^{\star}}\mid{\mathsf{R}}_{a},{\mathsf{A}}^{\textnormal{{spec}}}_{{\mathsf{k}}^{\star}})$
$\displaystyle\leqslant\mathbb{I}({\mathsf{A}}^{\textnormal{{off}}},{\mathsf{A}}^{\textnormal{{spec}}}_{>{\mathsf{k}}^{\star}}\,;{\mathsf{B}}^{\textnormal{{spec}}}_{\leqslant{\mathsf{k}}^{\star}},{\mathsf{B}}^{\textnormal{{rest}}}\mid{\mathsf{R}}_{a},{\mathsf{A}}^{\textnormal{{spec}}}_{{\mathsf{k}}^{\star}})$
(by the chain rule (A.1-(4)) and non-negativity of mutual information
(A.1-(2)))
$\displaystyle=\mathbb{I}({\mathsf{A}}^{\textnormal{{off}}},{\mathsf{A}}^{\textnormal{{spec}}}_{>{\mathsf{k}}^{\star}}\,;{\mathsf{B}}^{\textnormal{{spec}}}_{\leqslant{\mathsf{k}}^{\star}},{\mathsf{B}}^{\textnormal{{rest}}}\mid{\mathsf{\Pi}}_{1},\bm{\sigma}_{\textnormal{{r}}},\bm{\sigma}_{\textnormal{{c}}},{\mathsf{B}}^{\textnormal{{off}}},{\mathsf{k}}^{\star},{\mathsf{B}}^{\textnormal{{spec}}}_{>{\mathsf{k}}^{\star}},{\mathsf{A}}^{\textnormal{{spec}}}_{\leqslant{\mathsf{k}}^{\star}})$
(by the definition of ${\mathsf{R}}_{a}$)
$\displaystyle\leqslant\mathbb{I}({\mathsf{A}}^{\textnormal{{off}}},{\mathsf{A}}^{\textnormal{{spec}}}_{>{\mathsf{k}}^{\star}}\,;{\mathsf{B}}^{\textnormal{{spec}}}_{\leqslant{\mathsf{k}}^{\star}},{\mathsf{B}}^{\textnormal{{rest}}},{\mathsf{\Pi}}_{1}\mid\bm{\sigma}_{\textnormal{{r}}},\bm{\sigma}_{\textnormal{{c}}},{\mathsf{B}}^{\textnormal{{off}}},{\mathsf{k}}^{\star},{\mathsf{B}}^{\textnormal{{spec}}}_{>{\mathsf{k}}^{\star}},{\mathsf{A}}^{\textnormal{{spec}}}_{\leqslant{\mathsf{k}}^{\star}})$
(by the chain rule (A.1-(4)) and non-negativity of mutual information
(A.1-(2)))
$\displaystyle=\mathbb{I}({\mathsf{A}}^{\textnormal{{off}}},{\mathsf{A}}^{\textnormal{{spec}}}_{>{\mathsf{k}}^{\star}}\,;{\mathsf{B}}^{\textnormal{{spec}}}_{\leqslant{\mathsf{k}}^{\star}},{\mathsf{B}}^{\textnormal{{rest}}}\mid\bm{\sigma}_{\textnormal{{r}}},\bm{\sigma}_{\textnormal{{c}}},{\mathsf{B}}^{\textnormal{{off}}},{\mathsf{k}}^{\star},{\mathsf{B}}^{\textnormal{{spec}}}_{>{\mathsf{k}}^{\star}},{\mathsf{A}}^{\textnormal{{spec}}}_{\leqslant{\mathsf{k}}^{\star}})$
(as ${\mathsf{\Pi}}_{1}$ is fixed by
${\mathsf{B}}^{\textnormal{{off}}},{\mathsf{B}}^{\textnormal{{rest}}},{\mathsf{B}}^{\textnormal{{spec}}}$)
$\displaystyle=0,$ (by A.1-(2) and construction of distribution
$\mathcal{D}_{r}$)

and

$\displaystyle\mathbb{I}({\mathsf{B}}^{\textnormal{{spec}}}_{<{\mathsf{k}}^{\star}},{\mathsf{B}}^{\textnormal{{rest}}}\,;{\mathsf{A}}^{\textnormal{{off}}},{\mathsf{A}}^{\textnormal{{spec}}}_{\geqslant{\mathsf{k}}^{\star}}\mid{\mathsf{R}}_{a},{\mathsf{B}}^{\textnormal{{spec}}}_{{\mathsf{k}}^{\star}})$
$\displaystyle\leqslant\mathbb{I}({\mathsf{B}}^{\textnormal{{spec}}}_{<{\mathsf{k}}^{\star}},{\mathsf{B}}^{\textnormal{{rest}}},{\mathsf{\Pi}}_{1}\,;{\mathsf{A}}^{\textnormal{{off}}},{\mathsf{A}}^{\textnormal{{spec}}}_{\geqslant{\mathsf{k}}^{\star}}\mid\bm{\sigma}_{\textnormal{{r}}},\bm{\sigma}_{\textnormal{{c}}},{\mathsf{B}}^{\textnormal{{off}}},{\mathsf{k}}^{\star},{\mathsf{B}}^{\textnormal{{spec}}}_{\geqslant{\mathsf{k}}^{\star}},{\mathsf{A}}^{\textnormal{{spec}}}_{\leqslant{\mathsf{k}}^{\star}})$
(by the chain rule (A.1-(4)) and non-negativity of mutual information
(A.1-(2)))
$\displaystyle=\mathbb{I}({\mathsf{B}}^{\textnormal{{spec}}}_{<{\mathsf{k}}^{\star}},{\mathsf{B}}^{\textnormal{{rest}}}\,;{\mathsf{A}}^{\textnormal{{off}}},{\mathsf{A}}^{\textnormal{{spec}}}_{\geqslant{\mathsf{k}}^{\star}}\mid\bm{\sigma}_{\textnormal{{r}}},\bm{\sigma}_{\textnormal{{c}}},{\mathsf{B}}^{\textnormal{{off}}},{\mathsf{k}}^{\star},{\mathsf{B}}^{\textnormal{{spec}}}_{\geqslant{\mathsf{k}}^{\star}},{\mathsf{A}}^{\textnormal{{spec}}}_{\leqslant{\mathsf{k}}^{\star}})$
(as ${\mathsf{\Pi}}_{1}$ is fixed by
${\mathsf{B}}^{\textnormal{{rest}}},{\mathsf{B}}^{\textnormal{{off}}},{\mathsf{B}}^{\textnormal{{spec}}}$)
$\displaystyle=0.$ (by A.1-(2) and construction of distribution
$\mathcal{D}_{r}$)

This completes the proof.

We note here that the simulated instance $(A^{(r)},B^{(r)})$ in
$\mathcal{D}^{\textnormal{{real}}}$ is sampled according to
$\mathcal{D}_{r}(n_{r},\alpha)$ (recall 5.7). However, this is not true in
$\mathcal{D}^{\textnormal{{fake}}}$ since
$({\mathsf{A}}^{\star},{\mathsf{B}}^{\star})=({\mathsf{A}}^{\textnormal{{spec}}}_{{\mathsf{k}}^{\star}},{\mathsf{B}}^{\textnormal{{spec}}}_{{\mathsf{k}}^{\star}})$
is sampled according to $=\mathcal{D}_{r-1}$ instead of
$\mathcal{D}_{r}\mid{\mathsf{R}}_{a}$. Thus, to bound the total variation
distance between $\mathcal{D}^{\textnormal{{real}}}$ and
$\mathcal{D}^{\textnormal{{fake}}}$, we show that the information revealed by
the random variable ${\mathsf{R}}_{a}$ about the input
$({\mathsf{A}}^{\star},{\mathsf{B}}^{\star})$ in $\pi^{(2)}_{r}$, i.e., under
distribution $\mathcal{D}^{\textnormal{{real}}}$, is not too large. We need an
independence claim (Claim 5.12) and then a crucial bound on the information
carried by the first message (Claim 5.13).

######  Claim 5.12.

${\mathsf{A}}^{\textnormal{{spec}}}_{<{\mathsf{k}}^{\star}}\perp{\mathsf{B}}^{\textnormal{{spec}}}_{{\mathsf{k}}^{\star}}\mid{\mathsf{\Pi}}_{1},\bm{\sigma}_{\textnormal{{r}}},\bm{\sigma}_{\textnormal{{c}}},{\mathsf{B}}^{\textnormal{{off}}},{\mathsf{k}}^{\star},{\mathsf{B}}^{\textnormal{{spec}}}_{>{\mathsf{k}}^{\star}},{\mathsf{B}}^{\textnormal{{spec}}}_{<{\mathsf{k}}^{\star}}.$

###### Proof.

Again, we bound the mutual information between the terms. Let
${\mathsf{R}}_{\text{comp}}$ represent the independent source of public
randomness used in the message compression in step $(ii)$. Then,

$\displaystyle\mathbb{I}({\mathsf{A}}^{\textnormal{{spec}}}_{<{\mathsf{k}}^{\star}}\,;{\mathsf{B}}^{\textnormal{{spec}}}_{{\mathsf{k}}^{\star}}\mid{\mathsf{\Pi}}_{1},\bm{\sigma}_{\textnormal{{r}}},\bm{\sigma}_{\textnormal{{c}}},{\mathsf{B}}^{\textnormal{{off}}},{\mathsf{k}}^{\star},{\mathsf{B}}^{\textnormal{{spec}}}_{>{\mathsf{k}}^{\star}},{\mathsf{B}}^{\textnormal{{spec}}}_{<{\mathsf{k}}^{\star}})$
$\displaystyle\leqslant\mathbb{I}({\mathsf{A}}^{\textnormal{{spec}}}_{<{\mathsf{k}}^{\star}}\,;{\mathsf{B}}^{\textnormal{{spec}}}_{{\mathsf{k}}^{\star}},{\mathsf{\Pi}}_{1}\mid\bm{\sigma}_{\textnormal{{r}}},\bm{\sigma}_{\textnormal{{c}}},{\mathsf{B}}^{\textnormal{{off}}},{\mathsf{k}}^{\star},{\mathsf{B}}^{\textnormal{{spec}}}_{>{\mathsf{k}}^{\star}},{\mathsf{B}}^{\textnormal{{spec}}}_{<{\mathsf{k}}^{\star}})$
(moving ${\mathsf{\Pi}}_{1}$ by chain rule in A.1-(4), and non-negativity of
mutual information A.1-(2))
$\displaystyle\leqslant\mathbb{I}({\mathsf{A}}^{\textnormal{{spec}}}_{<{\mathsf{k}}^{\star}}\,;{\mathsf{B}}^{\textnormal{{spec}}}_{{\mathsf{k}}^{\star}},{\mathsf{B}}^{\textnormal{{rest}}},{\mathsf{R}}_{\text{comp}}\mid\bm{\sigma}_{\textnormal{{r}}},\bm{\sigma}_{\textnormal{{c}}},{\mathsf{B}}^{\textnormal{{off}}},{\mathsf{k}}^{\star},{\mathsf{B}}^{\textnormal{{spec}}}_{>{\mathsf{k}}^{\star}},{\mathsf{B}}^{\textnormal{{spec}}}_{<{\mathsf{k}}^{\star}})$
(by data processing inequality in A.1-(5), ${\mathsf{\Pi}}_{1}$ is fixed by
${\mathsf{B}}^{\textnormal{{rest}}},{\mathsf{B}}^{\textnormal{{spec}}},{\mathsf{B}}^{\textnormal{{off}}},{\mathsf{R}}_{\text{comp}}$)
$\displaystyle=\mathbb{I}({\mathsf{A}}^{\textnormal{{spec}}}_{<{\mathsf{k}}^{\star}}\,;{\mathsf{B}}^{\textnormal{{spec}}}_{{\mathsf{k}}^{\star}},{\mathsf{B}}^{\textnormal{{rest}}}\mid\bm{\sigma}_{\textnormal{{r}}},\bm{\sigma}_{\textnormal{{c}}},{\mathsf{B}}^{\textnormal{{off}}},{\mathsf{k}}^{\star},{\mathsf{B}}^{\textnormal{{spec}}}_{>{\mathsf{k}}^{\star}},{\mathsf{B}}^{\textnormal{{spec}}}_{<{\mathsf{k}}^{\star}})$
(since ${\mathsf{R}}_{\text{comp}}$ is an entirely independent source of
randomness) $\displaystyle\leqslant 0.\nobreak\hskip 0.0pt\hskip 15.00002pt
minus 5.0pt\nobreak\vrule height=7.5pt,width=5.0pt,depth=2.5pt$ (by A.1-(2)
and construction of $\mathcal{D}_{r}$)

The following claim is the heart of the entire proof.

######  Claim 5.13.

For any $k\in[k_{r}]$,

$\mathbb{I}({\mathsf{B}}^{\textnormal{{spec}}}_{k}\,;{\mathsf{\Pi}}_{1}\mid\bm{\sigma}_{\textnormal{{r}}},\bm{\sigma}_{\textnormal{{c}}},{\mathsf{B}}^{\textnormal{{off}}},{\mathsf{B}}^{\textnormal{{spec}}}_{<k},{\mathsf{B}}^{\textnormal{{spec}}}_{>k})\leqslant\frac{s}{b_{r}^{2}\cdot\alpha^{2}}.$

###### Proof.

Let $\rho_{\textnormal{{r}}},\rho_{\textnormal{{c}}}$ be the inverse of
$\sigma_{\textnormal{{r}}},\sigma_{\textnormal{{c}}}$, and let
$\bm{\rho}_{\textnormal{{r}}},\bm{\rho}_{\textnormal{{c}}}$ denote the random
variables corresponding to $\rho_{\textnormal{{r}}},\rho_{\textnormal{{c}}}$
respectively. For ease of exposition, we represent any permutation $\rho$ on
$[b_{r}]$ as an ordered set $S:=\\{\rho(\ell):\ell\in[b_{r}]\\}$ with the
ordering that $\rho(\ell)<\rho(\ell^{\prime})$ for $\ell<\ell^{\prime}$. Using
this representation, we allow for partial definitions of permutations, i.e.,
ordered subsets $T\subset S$. In particular, we require the following partial
definitions of $\rho_{\textnormal{{r}}}$ and $\rho_{\textnormal{{c}}}$:

  * •

Let $T_{\textnormal{{row}}}$ be an ordered set

$T_{\textnormal{{row}}}=\left\\{\rho_{\textnormal{{r}}}(\ell)\mid
b_{r}\cdot\alpha<\ell\leqslant b_{r},\ell\neq b_{r}\cdot\alpha+k\right\\}$

of size $b_{r}\cdot(1-\alpha)-1$, which is the set of rows that corresponds to
$B^{\textnormal{{off}}}$ except for the row corresponding to
${\mathsf{B}}^{\textnormal{{spec}}}_{k}$. Let
${\mathsf{T}}_{\textnormal{{row}}}$ denote its random variable.

  * •

Let $T_{\textnormal{{col}}}$ be an ordered set

$T_{\textnormal{{col}}}=\left\\{\rho_{\textnormal{{c}}}(\ell)\mid
b_{r}\cdot\alpha<\ell\leqslant b_{r},\ell\neq b_{r}\cdot\alpha+k\right\\}$

of size $b_{r}\cdot(1-\alpha)-1$, which is the set of columns that corresponds
to $B^{\textnormal{{off}}}$ except for the column corresponding to
${\mathsf{B}}^{\textnormal{{spec}}}_{k}$. Let
${\mathsf{T}}_{\textnormal{{col}}}$ denote its random variable.

We give an illustration of these definitions in Figure 10.

$B$$B$$B$$B$$B$$B$$B$$B$$B$$B$$B$$B$$B$$B$$B$$B$$B$$B$$B$$B$$B$$B$$B$$B$$B$$B$$B$$B$$B$$B$$B$$B$$B$$B$$B$$B$$B$$B$$B$$B$$B$$B$$B$$B$$B$$B$$B$$B$$B$$b_{r}\cdot\alpha$$b_{r}/\alpha$$b_{r}\cdot(1-\alpha)$$b_{r}\cdot\alpha$$b_{r}\cdot(1-\alpha)$$\sigma_{\textnormal{{r}}}(1)$$\sigma_{\textnormal{{c}}}(1)$$\sigma_{\textnormal{{r}}}(b_{r})$$\sigma_{\textnormal{{c}}}(b_{r})$$\vdots$$\dots$
Figure 10: An illustration of the partial definitions $T_{\textnormal{{row}}}$
and $T_{\textnormal{{col}}}$ for an instance of
$\mathsf{AHM}_{r}(n_{r},\alpha)$ where $b_{r}=7$, $\alpha=2/7$, and $k=2$. In
this figure, the $b_{r}\times b_{r}$ matrix is after applying the respective
permutations of rows and columns using $\sigma_{\textnormal{{r}}}$ and
$\sigma_{\textnormal{{c}}}$ held by Bob. In each position of the matrix, the
corresponding input is the $B^{\prime}s$ from each instance of
$\mathsf{AHM}_{r-1}(n_{r-1},\alpha)$ that is held by Alice.
$T_{\textnormal{{row}}}$ and $T_{\textnormal{{col}}}$ are partial definitions
of the permutations $\rho_{\textnormal{{r}}}$ and $\rho_{\textnormal{{c}}}$,
i.e., the inverses of $\sigma_{\textnormal{{r}}}$ and
$\sigma_{\textnormal{{c}}}$, respectively. $T_{\textnormal{{row}}}$
corresponds to fixing the rows filled red and $T_{\textnormal{{col}}}$
corresponds to fixing the columns filled blue, which implies fixing positions
filled purple. The unfilled (white) positions remain unrestricted by
$T_{\textnormal{{row}}},T_{\textnormal{{col}}}$, i.e., the green outlined
special position $B^{\textnormal{{spec}}}_{k}$ could still (uniformly) be in
any of the unfilled positions when conditioned on
$T_{\textnormal{{row}}},T_{\textnormal{{col}}}$ (instead of
$\sigma_{\textnormal{{r}}},\sigma_{\textnormal{{c}}}$).

This now allows us to write the indices $i,j\in[b_{r}]$ of the instances
corresponding to ${\mathsf{B}}^{\textnormal{{spec}}}$ and
${\mathsf{B}}^{\textnormal{{off}}}$ using
$\rho_{\textnormal{{r}}},\rho_{\textnormal{{c}}},T_{\textnormal{{row}}},T_{\textnormal{{col}}}$:

  1. $(i)$

For any $\ell\in[k_{r}]$, ${\mathsf{B}}^{\textnormal{{spec}}}_{\ell}$ is the
same as the random variable
${\mathsf{B}}_{\rho_{\textnormal{{r}}}(b_{r}\cdot\alpha+\ell),\rho_{\textnormal{{c}}}(b_{r}\cdot\alpha+\ell)}$
where we omit the superscript $r-1$ as it is clear from context;

  2. $(ii)$

${\mathsf{B}}^{\textnormal{{off}}},{\mathsf{B}}^{\textnormal{{spec}}}_{<k},{\mathsf{B}}^{\textnormal{{spec}}}_{>k}$
is the union of combinatorial rectangles formed by

$({\mathsf{T}}_{\textnormal{{row}}}\times{\mathsf{T}}_{\textnormal{{col}}}),\quad({\mathsf{T}}_{\textnormal{{row}}}\times\left\\{\bm{\rho}_{\textnormal{{c}}}(b_{r}\cdot\alpha+k)\right\\}),\quad(\left\\{\rho_{\textnormal{{r}}}(b_{r}\cdot\alpha+k)\right\\}\times{\mathsf{T}}_{\textnormal{{col}}}).$

Finally, let ${\mathsf{Z}}$ be defined as,

${\mathsf{Z}}:=({\mathsf{B}}^{\textnormal{{off}}},{\mathsf{B}}^{\textnormal{{spec}}}_{<k},{\mathsf{B}}^{\textnormal{{spec}}}_{>k}).$

With these at hand, we can start bounding the mutual information term in the
claim. Firstly, it is easy to see that,

$\displaystyle\mathbb{I}({\mathsf{B}}^{\textnormal{{spec}}}_{k}\,;{\mathsf{\Pi}}_{1}\mid\bm{\sigma}_{\textnormal{{r}}},\bm{\sigma}_{\textnormal{{c}}},{\mathsf{B}}^{\textnormal{{off}}},{\mathsf{B}}^{\textnormal{{spec}}}_{<k},{\mathsf{B}}^{\textnormal{{spec}}}_{>k})=\mathbb{I}({\mathsf{B}}^{\textnormal{{spec}}}_{k}\,;{\mathsf{\Pi}}_{1}\mid\bm{\sigma}_{\textnormal{{r}}},\bm{\sigma}_{\textnormal{{c}}},{\mathsf{Z}}),$

by definition of ${\mathsf{Z}}$.

We need the following intermediate claim for our proof.

######  Claim 5.14.

$\textnormal{dist}({\mathsf{B}}^{\textnormal{{spec}}}_{k},{\mathsf{\Pi}}_{1},{\mathsf{Z}}\mid\bm{\sigma}_{\textnormal{{r}}},\bm{\sigma}_{\textnormal{{c}}})=\textnormal{dist}({\mathsf{B}}^{\textnormal{{spec}}}_{k},{\mathsf{\Pi}}_{1},{\mathsf{Z}}\mid{\mathsf{T}}_{\textnormal{{row}}},{\mathsf{T}}_{\textnormal{{col}}},\bm{\rho}_{\textnormal{{r}}}(b_{r}\cdot\alpha+k),\bm{\rho}_{\textnormal{{c}}}(b_{r}\cdot\alpha+k)).$

###### Proof.

Let $\bm{\rho}_{\textnormal{{r}}}([b_{r}\cdot\alpha])$ and
$\bm{\rho}_{\textnormal{{c}}}([b_{r}\cdot\alpha])$ denote the random variables
$\bm{\rho}_{\textnormal{{r}}}(i)$ and $\bm{\rho}_{\textnormal{{c}}}(i)$ for
all $i\in[b_{r}\cdot\alpha]$ respectively. We know that random variable
$\bm{\sigma}_{\textnormal{{r}}}$ is fixed by $\bm{\rho}_{\textnormal{{r}}}$,
as they are inverses of each other. Random variable
$\bm{\rho}_{\textnormal{{r}}}$ is in turn fixed by all the values each element
of $[b_{r}]$ is mapped to, i.e., $\bm{\rho}_{\textnormal{{r}}}(i)$ for
$i\in[b_{r}]$.

Hence, it is sufficient to argue that,

$({\mathsf{B}}^{\textnormal{{spec}}}_{k},{\mathsf{\Pi}}_{1},{\mathsf{Z}})\perp\bm{\rho}_{\textnormal{{r}}}([b_{r}\cdot\alpha]),\bm{\rho}_{\textnormal{{c}}}([b_{r}\cdot\alpha])\mid{\mathsf{T}}_{\textnormal{{row}}},{\mathsf{T}}_{\textnormal{{col}}},\bm{\rho}_{\textnormal{{r}}}(b_{r}\cdot\alpha+k),\bm{\rho}_{\textnormal{{c}}}(b_{r}\cdot\alpha+k),$

to prove the claim. We know that
${\mathsf{B}}^{\textnormal{{spec}}}_{k},{\mathsf{Z}}$ is the random variable
corresponding to the instances in $A^{(r)}$ inside the combinatorial rectangle

$({\mathsf{T}}_{\textnormal{{row}}}\cup\\{\bm{\rho}_{\textnormal{{r}}}(b_{r}\cdot\alpha+k)\\})\times({\mathsf{T}}_{\textnormal{{col}}}\cup\\{\bm{\rho}_{\textnormal{{c}}}(b_{r}\cdot\alpha+k)\\}).$

The entirety of this rectangle is fixed by the conditioning.

Proving the claim amounts to proving that the joint distribution of
$B^{(r-1)}_{i,j}$ for a fixed set of positions of $A^{(r)}$ (the ones inside
the rectangle fixed by conditioning), and the transcript ${\mathsf{\Pi}}_{1}$
is independent of the _permutation_ of the rest of the positions of $A^{(r)}$.
This is true because ${P}_{X}$, who sends ${\mathsf{\Pi}}_{1}$, does not have
access to either of the permutations $\bm{\rho}_{\textnormal{{r}}}$ or
$\bm{\rho}_{\textnormal{{c}}}$ (held by ${P}_{Y}$).
${}_{\textnormal{~{}~{}\lx@cref{creftypecap~refnum}{clm:ind-rest-of-sigma}}}$

We can continue to bound the mutual information now.

$\displaystyle\mathbb{I}({\mathsf{B}}^{\textnormal{{spec}}}_{k}\,;{\mathsf{\Pi}}_{1}\mid\bm{\sigma}_{\textnormal{{r}}},\bm{\sigma}_{\textnormal{{c}}},{\mathsf{Z}})$
$\displaystyle=\mathbb{I}({\mathsf{B}}^{\textnormal{{spec}}}_{k}\,;{\mathsf{\Pi}}_{1}\mid{\mathsf{Z}},{\mathsf{T}}_{\textnormal{{row}}},{\mathsf{T}}_{\textnormal{{col}}},\bm{\rho}_{\textnormal{{r}}}(b_{r}\cdot\alpha+k),\bm{\rho}_{\textnormal{{c}}}(b_{r}\cdot\alpha+k))$
(by Claim 5.14)
$\displaystyle=\operatorname*{{\mathbb{E}}}_{\begin{subarray}{c}(T_{\textnormal{{row}}},T_{\textnormal{{col}}})\\\
\sim({\mathsf{T}}_{\textnormal{{row}}},{\mathsf{T}}_{\textnormal{{col}}})\end{subarray}}\mathbb{I}({\mathsf{B}}^{\textnormal{{spec}}}_{k}\,;{\mathsf{\Pi}}_{1}\mid{\mathsf{Z}},{\mathsf{T}}_{\textnormal{{row}}}=T_{\textnormal{{row}}},{\mathsf{T}}_{\textnormal{{col}}}=T_{\textnormal{{col}}},\bm{\rho}_{\textnormal{{r}}}(b_{r}\cdot\alpha+k),\bm{\rho}_{\textnormal{{c}}}(b_{r}\cdot\alpha+k))$
(by definition of conditional mutual information)
$\displaystyle\underset{\textnormal{(1)}}{\leqslant}\frac{1}{b_{r}^{2}\cdot\alpha^{2}}\operatorname*{{\mathbb{E}}}_{\begin{subarray}{c}(T_{\textnormal{{row}}},T_{\textnormal{{col}}})\\\
\sim({\mathsf{T}}_{\textnormal{{row}}},{\mathsf{T}}_{\textnormal{{col}}})\end{subarray}}\sum_{\begin{subarray}{c}i\in[b_{r}]\setminus{\mathsf{T}}_{\textnormal{{row}}},\\\
j\in[b_{r}]\setminus{\mathsf{T}}_{\textnormal{{col}}}\end{subarray}}\mathbb{I}({\mathsf{B}}_{i,j}\,;{\mathsf{\Pi}}_{1}\mid{\mathsf{Z}},T_{\textnormal{{row}}},T_{\textnormal{{col}}},\bm{\rho}_{\textnormal{{r}}}(b_{r}\cdot\alpha+k)=i,\bm{\rho}_{\textnormal{{c}}}(b_{r}\cdot\alpha+k)=j)$
$\displaystyle\underset{\textnormal{(2)}}{=}\frac{1}{b_{r}^{2}\cdot\alpha^{2}}\operatorname*{{\mathbb{E}}}_{\begin{subarray}{c}(T_{\textnormal{{row}}},T_{\textnormal{{col}}})\\\
\sim({\mathsf{T}}_{\textnormal{{row}}},{\mathsf{T}}_{\textnormal{{col}}})\end{subarray}}\sum_{i\in[b_{r}]\setminus{\mathsf{T}}_{\textnormal{{row}}},j\in[b_{r}]\setminus{\mathsf{T}}_{\textnormal{{col}}}}\mathbb{I}({\mathsf{B}}_{i,j}\,;{\mathsf{\Pi}}_{1}\mid{\mathsf{Z}},{\mathsf{T}}_{\textnormal{{row}}}=T_{\textnormal{{row}}},{\mathsf{T}}_{\textnormal{{col}}}=T_{\textnormal{{col}}})$
$\displaystyle\underset{\textnormal{(3)}}{=}\frac{1}{b_{r}^{2}\cdot\alpha^{2}}\sum_{i\in[b_{r}]\setminus{\mathsf{T}}_{\textnormal{{row}}},j\in[b_{r}]\setminus{\mathsf{T}}_{\textnormal{{col}}}}\mathbb{I}({\mathsf{B}}_{i,j}\,;{\mathsf{\Pi}}_{1}\mid{\mathsf{Z}},{\mathsf{T}}_{\textnormal{{row}}},{\mathsf{T}}_{\textnormal{{col}}})$

where $(1)$ holds by the definition of conditional mutual information since,
conditioned on any ${\mathsf{T}}_{\textnormal{{row}}}=T_{\textnormal{{row}}}$
and ${\mathsf{T}}_{\textnormal{{col}}}=T_{\textnormal{{col}}}$, the values of
$\bm{\rho}_{\textnormal{{r}}}(b_{r}\cdot\alpha+k)$ and
$\bm{\rho}_{\textnormal{{c}}}(b_{r}\cdot\alpha+k)$ are uniformly chosen from
$[b_{r}]\backslash T_{\textnormal{{row}}}$ and $[b_{r}]\backslash
T_{\textnormal{{col}}}$ (each of size $b_{r}\cdot\alpha+1$), respectively;
$(2)$ holds because, conditioned on any choice of
${\mathsf{T}}_{\textnormal{{row}}}=T_{\textnormal{{row}}}$ and
${\mathsf{T}}_{\textnormal{{col}}}=T_{\textnormal{{col}}}$, the event
$\bm{\rho}_{\textnormal{{c}}}(b_{r}\cdot\alpha+k)=j,\bm{\rho}_{\textnormal{{r}}}(b_{r}\cdot\alpha+k)=i$
is independent of $({\mathsf{B}}_{i,j},{\mathsf{\Pi}}_{1},{\mathsf{Z}})$; and
$(3)$ holds by the linearity of expectation and the definition of conditional
mutual information.

We re-index both the sets $[b_{r}]\setminus{\mathsf{T}}_{\textnormal{{row}}}$
and $[b_{r}]\setminus{\mathsf{T}}_{\textnormal{{col}}}$ as
$[b_{r}\cdot\alpha+1]$ for ease of exposition just for this final part of the
proof. We know that ${\mathsf{B}}_{i,j}$ for any $i,j\in[b_{r}]$ are sampled
independently of each other in distribution $\mathcal{D}_{r}$. Hence, using
Proposition A.2, we have that

$\displaystyle\frac{1}{b_{r}^{2}\cdot\alpha^{2}}\sum_{i\in[b_{r}]\setminus{\mathsf{T}}_{\textnormal{{row}}},j\in[b_{r}]\setminus{\mathsf{T}}_{\textnormal{{col}}}}\mathbb{I}({\mathsf{B}}_{i,j}\,;{\mathsf{\Pi}}_{1}\mid{\mathsf{Z}},{\mathsf{T}}_{\textnormal{{row}}},{\mathsf{T}}_{\textnormal{{col}}})$
$\displaystyle\leqslant\frac{1}{b_{r}^{2}\cdot\alpha^{2}}\sum_{i\in[b_{r}\cdot\alpha+1],j\in[b_{r}\cdot\alpha+1]}\mathbb{I}({\mathsf{B}}_{i,j}\,;{\mathsf{\Pi}}_{1}\mid{\mathsf{B}}_{i,>j},{\mathsf{B}}_{>i},{\mathsf{Z}},{\mathsf{T}}_{\textnormal{{row}}},{\mathsf{T}}_{\textnormal{{col}}})$
$\displaystyle=\frac{1}{b_{r}^{2}\cdot\alpha^{2}}\cdot\mathbb{I}({\mathsf{B}}_{1,1},\ldots,{\mathsf{B}}_{1,b_{r}\cdot\alpha+1},{\mathsf{B}}_{2,1},\ldots,{\mathsf{B}}_{b_{r}\cdot\alpha+1,b_{r}\cdot\alpha+1}\,;{\mathsf{\Pi}}_{1}\mid{\mathsf{Z}},{\mathsf{T}}_{\textnormal{{row}}},{\mathsf{T}}_{\textnormal{{col}}})$
(by chain rule of mutual information, A.1-(4))
$\displaystyle\leqslant\frac{1}{b_{r}^{2}\cdot\alpha^{2}}\cdot\mathbb{I}({\mathsf{B}}^{(r)}\,;{\mathsf{\Pi}}_{1}\mid{\mathsf{Z}},{\mathsf{T}}_{\textnormal{{row}}},{\mathsf{T}}_{\textnormal{{col}}})$
(by the chain rule (A.1-(4)) and non-negativity of mutual information
(A.1-(2))) $\displaystyle\leqslant\frac{s}{b_{r}^{2}\cdot\alpha^{2}}.$ (as
$\mathbb{I}({\mathsf{B}}^{(r)}\,;{\mathsf{\Pi}}_{1}\mid{\mathsf{Z}},{\mathsf{T}}_{\textnormal{{row}}},{\mathsf{T}}_{\textnormal{{col}}})\leqslant\mathbb{H}({\mathsf{\Pi}}_{1})\leqslant
s$ by A.1-(1))

This proves the claim.

We now use these claims to show that the information revealed by random
variable ${\mathsf{R}}_{a}$ about the input
$({\mathsf{A}}^{\star},{\mathsf{B}}^{\star})$ is not too large in
$\mathcal{D}^{\textnormal{{real}}}$.

######  Claim 5.15.

$\mathbb{I}({\mathsf{A}}^{\textnormal{{spec}}}_{{\mathsf{k}}^{\star}},{\mathsf{B}}^{\textnormal{{spec}}}_{{\mathsf{k}}^{\star}}\,;{\mathsf{R}}_{a})\leqslant\frac{s}{b_{r}^{2}\cdot\alpha^{2}}.$

###### Proof.

First, by chain rule of mutual information (A.1-(4)), we have that

$\displaystyle\mathbb{I}({\mathsf{A}}^{\textnormal{{spec}}}_{{\mathsf{k}}^{\star}},{\mathsf{B}}^{\textnormal{{spec}}}_{{\mathsf{k}}^{\star}}\,;{\mathsf{R}}_{a})$
$\displaystyle=\mathbb{I}({\mathsf{B}}^{\textnormal{{spec}}}_{{\mathsf{k}}^{\star}}\,;{\mathsf{R}}_{a})+\mathbb{I}({\mathsf{A}}^{\textnormal{{spec}}}_{{\mathsf{k}}^{\star}}\,;{\mathsf{R}}_{a}\mid{\mathsf{B}}^{\textnormal{{spec}}}_{{\mathsf{k}}^{\star}}).$

We can prove that the second term is zero as follows: Let
${\mathsf{R}}_{\text{comp}}$ represent the independent source of public
randomness used in the message compression in step $(ii)$. Then,

$\displaystyle\mathbb{I}({\mathsf{A}}^{\textnormal{{spec}}}_{{\mathsf{k}}^{\star}}\,;{\mathsf{R}}_{a}\mid{\mathsf{B}}^{\textnormal{{spec}}}_{{\mathsf{k}}^{\star}})$
$\displaystyle=\mathbb{I}({\mathsf{A}}^{\textnormal{{spec}}}_{{\mathsf{k}}^{\star}}\,;{\mathsf{\Pi}}_{1},\bm{\sigma}_{\textnormal{{r}}},\bm{\sigma}_{\textnormal{{c}}},{\mathsf{B}}^{\textnormal{{off}}},{\mathsf{k}}^{\star},{\mathsf{B}}^{\textnormal{{spec}}}_{>{\mathsf{k}}^{\star}},{\mathsf{A}}^{\textnormal{{spec}}}_{<{\mathsf{k}}^{\star}}\mid{\mathsf{B}}^{\textnormal{{spec}}}_{{\mathsf{k}}^{\star}})$
(by expanding ${\mathsf{R}}_{a}$)
$\displaystyle=\mathbb{I}({\mathsf{A}}^{\textnormal{{spec}}}_{{\mathsf{k}}^{\star}}\,;\bm{\sigma}_{\textnormal{{r}}},\bm{\sigma}_{\textnormal{{c}}},{\mathsf{B}}^{\textnormal{{off}}},{\mathsf{k}}^{\star},{\mathsf{B}}^{\textnormal{{spec}}}_{>{\mathsf{k}}^{\star}},{\mathsf{A}}^{\textnormal{{spec}}}_{<{\mathsf{k}}^{\star}}\mid{\mathsf{B}}^{\textnormal{{spec}}}_{{\mathsf{k}}^{\star}})+\mathbb{I}({\mathsf{A}}^{\textnormal{{spec}}}_{{\mathsf{k}}^{\star}}\,;{\mathsf{\Pi}}_{1}\mid{\mathsf{B}}^{\textnormal{{spec}}}_{{\mathsf{k}}^{\star}},\bm{\sigma}_{\textnormal{{r}}},\bm{\sigma}_{\textnormal{{c}}},{\mathsf{B}}^{\textnormal{{off}}},{\mathsf{k}}^{\star},{\mathsf{B}}^{\textnormal{{spec}}}_{>{\mathsf{k}}^{\star}},{\mathsf{A}}^{\textnormal{{spec}}}_{<{\mathsf{k}}^{\star}})$
(by chain rule in A.1-(4))
$\displaystyle=0+\mathbb{I}({\mathsf{A}}^{\textnormal{{spec}}}_{{\mathsf{k}}^{\star}}\,;{\mathsf{\Pi}}_{1}\mid{\mathsf{B}}^{\textnormal{{spec}}}_{{\mathsf{k}}^{\star}},\bm{\sigma}_{\textnormal{{r}}},\bm{\sigma}_{\textnormal{{c}}},{\mathsf{B}}^{\textnormal{{off}}},{\mathsf{k}}^{\star},{\mathsf{B}}^{\textnormal{{spec}}}_{>{\mathsf{k}}^{\star}},{\mathsf{A}}^{\textnormal{{spec}}}_{<{\mathsf{k}}^{\star}}).$
(by A.1-(2) and construction of $\mathcal{D}_{r}$)
$\displaystyle\leqslant\mathbb{I}({\mathsf{A}}^{\textnormal{{spec}}}_{{\mathsf{k}}^{\star}}\,;{\mathsf{B}}^{\textnormal{{rest}}},{\mathsf{B}}^{\textnormal{{spec}}}_{<{\mathsf{k}}^{\star}},{\mathsf{R}}_{\text{comp}}\mid{\mathsf{B}}^{\textnormal{{spec}}}_{{\mathsf{k}}^{\star}},\bm{\sigma}_{\textnormal{{r}}},\bm{\sigma}_{\textnormal{{c}}},{\mathsf{B}}^{\textnormal{{off}}},{\mathsf{k}}^{\star},{\mathsf{B}}^{\textnormal{{spec}}}_{>{\mathsf{k}}^{\star}},{\mathsf{A}}^{\textnormal{{spec}}}_{<{\mathsf{k}}^{\star}}).$
(by data processing inequality A.1-(5) as ${\mathsf{\Pi}}_{1}$ is fixed by
${\mathsf{B}}^{\textnormal{{spec}}},{\mathsf{B}}^{\textnormal{{off}}},{\mathsf{B}}^{\textnormal{{rest}}},{\mathsf{R}}_{\text{comp}}$)
$\displaystyle=\mathbb{I}({\mathsf{A}}^{\textnormal{{spec}}}_{{\mathsf{k}}^{\star}}\,;{\mathsf{B}}^{\textnormal{{rest}}},{\mathsf{B}}^{\textnormal{{spec}}}_{<{\mathsf{k}}^{\star}}\mid{\mathsf{B}}^{\textnormal{{spec}}}_{{\mathsf{k}}^{\star}},\bm{\sigma}_{\textnormal{{r}}},\bm{\sigma}_{\textnormal{{c}}},{\mathsf{B}}^{\textnormal{{off}}},{\mathsf{k}}^{\star},{\mathsf{B}}^{\textnormal{{spec}}}_{>{\mathsf{k}}^{\star}},{\mathsf{A}}^{\textnormal{{spec}}}_{<{\mathsf{k}}^{\star}}).$
(since ${\mathsf{R}}_{\text{comp}}$ is an entirely independent source of
randomness) $\displaystyle=0.$ (by A.1-(2) and construction of
$\mathcal{D}_{r}$)

Therefore, an upper bound on
$\mathbb{I}({\mathsf{B}}^{\textnormal{{spec}}}_{{\mathsf{k}}^{\star}}\,;{\mathsf{R}}_{a})$
is an upper bound on
$\mathbb{I}({\mathsf{A}}^{\textnormal{{spec}}}_{{\mathsf{k}}^{\star}},{\mathsf{B}}^{\textnormal{{spec}}}_{{\mathsf{k}}^{\star}}\,;{\mathsf{R}}_{a})$.
We have,

$\displaystyle\mathbb{I}({\mathsf{B}}^{\textnormal{{spec}}}_{{\mathsf{k}}^{\star}}\,;{\mathsf{R}}_{a})$
$\displaystyle\hskip
20.0pt\leqslant\mathbb{I}({\mathsf{B}}^{\textnormal{{spec}}}_{{\mathsf{k}}^{\star}}\,;{\mathsf{R}}_{a},{\mathsf{B}}^{\textnormal{{spec}}}_{<{\mathsf{k}}^{\star}})$
(by the chain rule (A.1-(4)) and non-negativity of mutual information
(A.1-(2))) $\displaystyle\hskip
20.0pt=\mathbb{I}({\mathsf{B}}^{\textnormal{{spec}}}_{{\mathsf{k}}^{\star}}\,;{\mathsf{\Pi}}_{1},\bm{\sigma}_{\textnormal{{r}}},\bm{\sigma}_{\textnormal{{c}}},{\mathsf{B}}^{\textnormal{{off}}},{\mathsf{k}}^{\star},{\mathsf{B}}^{\textnormal{{spec}}}_{>{\mathsf{k}}^{\star}},{\mathsf{A}}^{\textnormal{{spec}}}_{<{\mathsf{k}}^{\star}},{\mathsf{B}}^{\textnormal{{spec}}}_{<{\mathsf{k}}^{\star}})$
(by expanding ${\mathsf{R}}_{a}$) $\displaystyle\hskip
20.0pt=\mathbb{I}({\mathsf{B}}^{\textnormal{{spec}}}_{{\mathsf{k}}^{\star}}\,;\bm{\sigma}_{\textnormal{{r}}},\bm{\sigma}_{\textnormal{{c}}},{\mathsf{B}}^{\textnormal{{off}}},{\mathsf{k}}^{\star},{\mathsf{B}}^{\textnormal{{spec}}}_{>{\mathsf{k}}^{\star}},{\mathsf{A}}^{\textnormal{{spec}}}_{<{\mathsf{k}}^{\star}},{\mathsf{B}}^{\textnormal{{spec}}}_{<{\mathsf{k}}^{\star}})$
$\displaystyle\hskip
100.0pt+\mathbb{I}({\mathsf{B}}^{\textnormal{{spec}}}_{{\mathsf{k}}^{\star}}\,;{\mathsf{\Pi}}_{1}\mid\bm{\sigma}_{\textnormal{{r}}},\bm{\sigma}_{\textnormal{{c}}},{\mathsf{B}}^{\textnormal{{off}}},{\mathsf{k}}^{\star},{\mathsf{B}}^{\textnormal{{spec}}}_{>{\mathsf{k}}^{\star}},{\mathsf{A}}^{\textnormal{{spec}}}_{<{\mathsf{k}}^{\star}},{\mathsf{B}}^{\textnormal{{spec}}}_{<{\mathsf{k}}^{\star}})$
(by chain rule in A.1-(4)) $\displaystyle\hskip
20.0pt=0+\mathbb{I}({\mathsf{B}}^{\textnormal{{spec}}}_{{\mathsf{k}}^{\star}}\,;{\mathsf{\Pi}}_{1}\mid\bm{\sigma}_{\textnormal{{r}}},\bm{\sigma}_{\textnormal{{c}}},{\mathsf{B}}^{\textnormal{{off}}},{\mathsf{k}}^{\star},{\mathsf{B}}^{\textnormal{{spec}}}_{>{\mathsf{k}}^{\star}},{\mathsf{A}}^{\textnormal{{spec}}}_{<{\mathsf{k}}^{\star}},{\mathsf{B}}^{\textnormal{{spec}}}_{<{\mathsf{k}}^{\star}})$
(by A.1-(2) and construction of $\mathcal{D}_{r}$) $\displaystyle\hskip
20.0pt\leqslant\mathbb{I}({\mathsf{B}}^{\textnormal{{spec}}}_{{\mathsf{k}}^{\star}}\,;{\mathsf{\Pi}}_{1}\mid\bm{\sigma}_{\textnormal{{r}}},\bm{\sigma}_{\textnormal{{c}}},{\mathsf{B}}^{\textnormal{{off}}},{\mathsf{k}}^{\star},{\mathsf{B}}^{\textnormal{{spec}}}_{>{\mathsf{k}}^{\star}},{\mathsf{B}}^{\textnormal{{spec}}}_{<{\mathsf{k}}^{\star}})$
(removing ${\mathsf{A}}^{\textnormal{{spec}}}_{<{\mathsf{k}}^{\star}}$ in the
conditioning by Proposition A.3 and Claim 5.12) $\displaystyle\hskip
20.0pt=\frac{1}{k_{r}}\cdot\sum_{k\in[k_{r}]}\mathbb{I}({\mathsf{B}}^{\textnormal{{spec}}}_{k}\,;{\mathsf{\Pi}}_{1}\mid\bm{\sigma}_{\textnormal{{r}}},\bm{\sigma}_{\textnormal{{c}}},{\mathsf{B}}^{\textnormal{{off}}},{\mathsf{k}}^{\star}=k,{\mathsf{B}}^{\textnormal{{spec}}}_{>k},{\mathsf{B}}^{\textnormal{{spec}}}_{<k})$
(by the definition of conditional mutual information) $\displaystyle\hskip
20.0pt=\frac{1}{k_{r}}\cdot\sum_{k\in[k_{r}]}\mathbb{I}({\mathsf{B}}^{\textnormal{{spec}}}_{k}\,;{\mathsf{\Pi}}_{1}\mid\bm{\sigma}_{\textnormal{{r}}},\bm{\sigma}_{\textnormal{{c}}},{\mathsf{B}}^{\textnormal{{off}}},{\mathsf{B}}^{\textnormal{{spec}}}_{>k},{\mathsf{B}}^{\textnormal{{spec}}}_{<k})$
(as event ${\mathsf{k}}^{\star}=k$ is independent of
$({\mathsf{B}}^{\textnormal{{spec}}},{\mathsf{B}}^{\textnormal{{off}}},{\mathsf{\Pi}}_{1},\bm{\sigma}_{\textnormal{{r}}},\bm{\sigma}_{\textnormal{{c}}})$
(see proof of Claim 5.8)) $\displaystyle\hskip
20.0pt\leqslant\frac{s}{b_{r}^{2}\cdot\alpha^{2}},$

by applying Claim 5.13 to bound each term, completing the proof.

We are now ready to show that $\mathcal{D}^{\textnormal{{fake}}}$ and
$\mathcal{D}^{\textnormal{{real}}}$ are statistically close.

######  Lemma 5.16.

$\|\mathcal{D}^{\textnormal{{real}}}-\mathcal{D}^{\textnormal{{fake}}}\|_{\mathrm{tvd}}\leqslant\sqrt{\frac{s}{2\cdot
b_{r}^{2}\cdot\alpha^{2}}}.$

###### Proof.

Firstly, we use weak chain rule over total variation distance (A.6) using the