invoke procedure main-reconstruct for each $\textbf{main-sk}_{i}(x)$ and
$\textbf{main-sk}_{i}(y)$, $i=1,\dots,10s+50$. Each call to main-reconstruct
produces a collection of costly edges that should be part of the canonical
alignment of $x$ and $y$. Some of the edges might be misidentified by a given
call to main-reconstruct so as the final output of ED-recover we output only
edges that main-reconstruct outputs more than half of the time.

Algorithm 10 $\textsc{ED-recover}(\textbf{sk}(x),\textbf{sk}(y);k,n)$

Input: Sketch of $x$: $\textbf{sk}(x)=(\textbf{OR-print}(x)$, $\textbf{main-
sk}_{1}(x),\ldots,$ $\textbf{main-sk}_{10s+50}(x))$ and sketch of $y$:
$\textbf{sk}(y)=(\textbf{OR-print}(y),$ $\textbf{main-
sk}_{1}(y),\ldots,\textbf{main-sk}_{10s+50}(y))$.

Output: Edit distance of $x$ and $y$ if it is smaller than $k$, and large
otherwise.

if  _$\textbf{OR-print}(x)\neq\textbf{OR-print}(y)$_ then return large;

66 for  _$i\in\\{1,\ldots,10s+50\\}$_ do

67 $\textbf{candids}_{i}=\textsc{main-reconstruct}(\textbf{main-
sk}_{i}(x),\textbf{main-sk}_{i}(y))$

68 end for

69Let found-edges be the set of edges that appear in more than half of the
sets $\textbf{candids}_{i}$. if  _$|\textbf{found-edges}| >k$_ then return
large;

Return found-edges.

##  7 Analysis of the sketch-and-recover scheme

###  7.1 Main result

An execution of ED-sketch and ED-recover on a pair of strings $x,y$ consists
of evaluation of $\textsc{ED-sketch}(x)$ and $\textsc{ED-sketch}(y)$ and of
$\textsc{ED-recover}(\textsc{ED-sketch}(x),\textsc{ED-sketch}(y))$ where all
three evaluations use the same randomizing parameter $\rho$. The execution of
$\textsc{ED-sketch}(x)$, $\textsc{ED-sketch}(y)$ and $\textsc{ED-
recover}(\textsc{ED-sketch}(x),\textsc{ED-sketch}(y))$ _succeeds_ provided
that

  * •

If $\textbf{ED}(x,y)>k$ then ED-recover outputs large, and

  * •

If $\textbf{ED}(x,y)\leq k$ then ED-recover outputs
$\textbf{costly}({\textbf{canon}}^{+}(x,y))$,

and fails otherwise.

In this section we prove the main result of the paper:

######  Theorem 7.1.

The pair of algorithms ED-sketch and ED-recover provide a sketch-and-recover
scheme for the canonical difference summary for edit distance. Given
sufficiently large size parameter $n$, $s=\log n$, distance parameter $k\leq
n/40s_{{\mathrm{OR}}}$ and alphabet $\Sigma_{n}$:

  1. 1.

ED-sketch runs on strings $x$ of length at most $n$ and outputs a sketch
$\textbf{str-sk}(x)$ of length at most $O(ks_{{\mathrm{OR}}}^{2}s^{O(1)})$.

  2. 2.

The running time of ED-sketch is ${\widetilde{O}}(|x|\cdot T(n))$ and the
running time of ED-recover is
${\widetilde{O}}(\min(n^{2},k^{3}s_{{\mathrm{OR}}}^{2}))$, where $T(n)\geq n$
is the time to compute OR-fingerprint on inputs of length $n$. (Recall, $T(n)$
is polynomial in $n$.)

  3. 3.

For all $x$,$y$ of length at most $n$, the execution of $\textsc{ED-
sketch}(x)$, $\textsc{ED-sketch}(y)$, and $\textsc{ED-recover}($ $\textsc{ED-
sketch}(x),$ $\textsc{ED-sketch}(y))$ fails with probability at most 1/3.

As usual, the value 1/3 for failure probability is arbitrary, and can be
replaced by any function $\delta>0$ by repetition: construct a sketch
consisting of $r=O(\log(1/\delta))$ independent sketches of $x$ and of $y$,
apply the recovery algorithm to each pair of corresponding sketches, and take
majority vote.

The bounds on the sketch size and running time are straightforward and given
in Section 7.2.

The most significant part of the analysis is the upper bound on the failure
probability. This proof is contained in Sections 7.4 to 8.2.

###  7.2 Time and space analysis

In this section we prove parts 1 and 2 of Theorem 7.1. For part 1 we bound the
size of the output of ED-sketch. The output consists of $10s+50$ independent
instances of the output of grammar-condense and location-condense. Each call
to grammar-condense produces $d$ sketches using hmr-sketch, each of bit-size
${\widetilde{O}}(s_{{\mathrm{OR}}}^{2}k)$. Each call to location-condense
produces $ds-1$ sketches using hmr-sketch, each of bit-size
${\widetilde{O}}(s_{{\mathrm{OR}}}^{2}k)$. Hence, the total size of the sketch
is ${\widetilde{O}}(k2^{O(\sqrt{\log(n)\log\log(n)})})$.

For part 2 we bound the time of ED-sketch and ED-recover. Let $m=|x|$ and
$T(n)$ be the time to compute OR-fingerprint on strings of length at most $n$.
ED-sketch makes one call to OR-fingerprint which takes time $T(n)$ and then
makes $10s+50={\widetilde{O}}(1)$ independent calls to main-sketch. main-
sketch calls main-decomp, grammar-condense, and location-condense.

main-decomp constructs substrs, grams, OR-prints, $\textbf{substrs}^{*}$,
$\textbf{left-size}^{*}$, and ${\textbf{fingerprints}}^{*}$. Even though each
of these is defined on trees which have (roughly) $n^{d}$ nodes, which is
superpolynomial in $n$, the time to compute them will be polynomial in $m$ as
we use sparse representation for each labeling of the tree. Sets vis-nodes and
$\textbf{vis-nodes}^{*}$ determine the nodes with non-empty labels in those
trees.

Since substrs is a decomposition tree for $x$, each layer is a decomposition
of $x$ and has at most $m$ nonempty strings, so $|\textbf{vis-nodes}|\leq dm$.
Thus, the total cost of calls to basic-decomp for strings on a single layer of
substrs is ${\widetilde{O}}(m)$. Hence, each layer of grams contains in total
${\widetilde{O}}(m)$ ones in the grammar bit-vectors. To construct OR-prints,
we apply OR-fingerprint to each nonempty $\textbf{substrs}_{v}$. This take
total time ${\widetilde{O}}(m\cdot T(n))$.

The decomposition tree $\textbf{substrs}^{*}$ also uses a sparse
representation and is explicitly defined on the set $\textbf{vis-nodes}^{*}$
which consists of all nodes in the binary tree that are ancestors of a node in
vis-nodes. Since each node in vis-nodes has at most $ds$ ancestors
$|\textbf{vis-nodes}^{*}|={\widetilde{O}}(m)$. Hence, $\textbf{left-
size}^{*}_{v}$ can be computed in time ${\widetilde{O}}(m)$. We apply
fingerprint to each node of $\textbf{substrs}^{*}$ in $\textbf{vis-
nodes}^{*}$. We need ${\widetilde{O}}(m)$ time to compute the fingerprints for
nodes on a single layers of $\textbf{substrs}^{*}$. Thus the total time to
compute $\textbf{substrs}^{*}$, $\textbf{left-size}^{*}$, and
${\textbf{fingerprints}}^{*}$ is ${\widetilde{O}}(m)$.

grammar-condense involves the computation of $d$ instances of hmr-sketch. The
$j$-th instance is for $\textbf{grams}^{j}$ which is the $j$-th layer of
grams. Thus the sparse representation of $\textbf{grams}^{j}$ contains at most
${\widetilde{O}}(m)$ entries so the time to compute a single hmr-sketch is
${\widetilde{O}}(m+2^{O(\sqrt{\log(n)\log\log(n)})}k)$.

Similarly location-condense involves the computation of $ds-1$ instances of
hmr-sketch. The $j$-th instance is for the function $\textbf{left-size}^{j}$
which has at most $m$ non-zero entries so again the time of hmr-sketch is
${\widetilde{O}}(m+2^{O(\sqrt{\log(n)\log\log(n)})}k)$.

Thus the overall time of ED-sketch is ${\widetilde{O}}(m\cdot
T(n)+m+2^{O(\sqrt{\log(n)\log\log(n)})}k)$.

Next we consider the time of ED-recover. We will argue first that its running
time is at most ${\widetilde{O}}(n^{2})$. The we point out how to make it
faster. find-strings is applied to each pair $\textbf{str-
sk}^{j}(x),\textbf{str-sk}^{j}(y)$ for $j\in\\{1,\ldots,d\\}$ and find-
locations is applied to each pair $\textbf{loc-sk}^{j}(x),$ $\textbf{loc-
sk}^{j}(y)$ for $j\in\\{1,\ldots,ds-1\\}$.

Each call to find-strings runs hmr-recover whose running time is
${\widetilde{O}}(2^{O(\sqrt{\log(n)\log\log(n)})}k)$. This produces a set of
at most ${\widetilde{O}}(2^{O(\sqrt{\log(n)\log\log(n)})}k)$ mismatch pairs.
This determines the set str-nodes of nodes, also of size at most the number of
mismatch pairs. For each node $v\in\textbf{str-nodes}$ we use the mismatch
pairs to construct $\textbf{found-gram}^{j}_{v}$, which is a proposed
reconstruction of $\textbf{grams}_{v}$. We apply basic-decode to each of these
to get $\textbf{found-str}_{v}$. The total time is within
${\widetilde{O}}(n)$.

Similarly, each call to find-locations runs hmr-recover. This produces a set
of at most ${\widetilde{O}}(2^{O(\sqrt{\log(n)\log\log(n)})}k)$ mismatch
pairs. For each node in str-nodes we calculate a sum of at most $sd$ elements.
Hence, the total time is ${\widetilde{O}}(n)$.

Last, for each node $v$ in str-nodes we have to compute the edit distance of
$\textbf{found-str}_{v}(x)$ and $\textbf{found-str}_{v}(y)$ which takes time
$O(|\textbf{found-str}_{v}(x)|\cdot|\textbf{found-str}_{v}(y)|)$. By Corollary
7.8 (which is stated later) under normal execution, both $\textbf{found-
str}_{v}(x)$ and $\textbf{found-str}_{v}(y)$ are real substrings of $x$ and
$y$, respectively. Thus the sum of lengths of $\textbf{found-str}_{v}(x)$ at
the same layer of the decomposition tree is at most $n$. Thus the total time
needed for the reconstruction is ${\widetilde{O}}(n^{2})$ under normal
execution. If the recovery algorithm runs for more time than
${\widetilde{O}}(n^{2})$ we can terminate it as the execution is abnormal and
the result might be incorrect. That happens with only small probability as
shown later.

To obtain a faster running time for the recovery, observe that one does not
have to expand the grammars to compute their canonical alignment. Using the
result of [GKLS22] one can compute the set of costly edges of the canonical
alignment for two strings represented by grammars of size at most $g$ in time
${\widetilde{O}}(g+k^{\prime 2})$ where $k^{\prime}$ is the edit distance of
the two strings. The total size of grammars we will recover is
${\widetilde{O}}(ks_{{\mathrm{OR}}}^{2})$, their number is also at most
${\widetilde{O}}(ks_{{\mathrm{OR}}}^{2})$, and the edit distance we care for
is $k$. Hence running the edit distance algorithm on all recovered pairs of
grammars costs at most ${\widetilde{O}}(k^{3}s_{{\mathrm{OR}}}^{2})$.

###  7.3 Upper bound on the failure probability

Having proved parts 1 and 2 of Theorem 7.1, we now turn to the proof of Part
3. In this section we state Theorem 7.2 and use it to prove Part 3 of Theorem
7.1. The proof of Theorem 7.2 will be divided into several subsections.

We fix strings $x$ and $y$ and consider an execution of $\textsc{ED-
sketch}(x)$, $\textsc{ED-sketch}(y)$ and $\textsc{ED-recover}(\textsc{ED-
sketch}(x),\textsc{ED-sketch}(y))$. We want to show that the probability of
failure is at most 1/3.

Recall that the algorithm ED-recover first compares $\textbf{OR-print}(x)$ and
$\textbf{OR-print}(y)$ and outputs large if they are unequal. If they are
equal then it executes ED-recover to produce the set found-edges of annotated
edges and outputs large if $|\textbf{found-edges}|>k$ and outputs found-edges
if $|\textbf{found-edges}|\leq k$.

It simplifies the discussion to modify ED-recover so that it starts by
computing found-edges and only then compares $\textbf{OR-print}(x)$ to
$\textbf{OR-print}(y)$ and outputs large if the fingerprints differ and
outputs found-edges otherwise. This modified algorithm clearly has the same
output behavior as ED-recover but has the analytic advantage that the (random)
value of found-edges is independent of the event $\textbf{OR-
print}(x)=\textbf{OR-print}(y)$.

We will prove:

######  Theorem 7.2.

If $\textbf{ED}(x,y)<20ks_{{\mathrm{OR}}}$ then $\textbf{Pr}[\textbf{found-
edges}\neq\textbf{costly}({\textbf{canon}}^{+}(x,y))]\leq 1/4$.

Using this theorem, it is easy to bound the failure probability of ED-recover
to complete the proof of the third part of Theorem 7.1.

We divide into three cases depending on $\textbf{ED}(x,y)$.

Case (1): $\textbf{ED}(x,y)>20ks_{{\mathrm{OR}}}$. The algorithm correctly
outputs large unless $\textsc{OR-fingerprint}(x)=\textsc{OR-fingerprint}(y)$
and by Theorem 4.2, $\textsc{OR-fingerprint}(x)=\textsc{OR-fingerprint}(y)$
happens with probability at most $1/n^{4}$.

Case (2):$20ks_{{\mathrm{OR}}}>\textbf{ED}(x,y)>k$. The algorithm correctly
outputs large if $\textsc{OR-fingerprint}(x)\neq\textsc{OR-fingerprint}(y)$ or
if $\textbf{found-edges}=\textbf{costly}({\textbf{canon}}^{+}(x,y))$ (since
$|\textbf{costly}({\textbf{canon}}^{+}(x,y))|=\textbf{ED}(x,y)$). So the
output will be incorrect only if $\textbf{found-
edges}\neq\textbf{costly}({\textbf{canon}}^{+}(x,y))$. By Theorem 7.2 this
happens with probability at most $1/4$.

Case (3):$k\geq\textbf{ED}(x,y)$. Success requires the algorithm to output
$\textbf{costly}({\textbf{canon}}^{+}(x,y))$. This will fail only if
$\textsc{OR-fingerprint}(x)\neq\textsc{OR-fingerprint}(y)$ or $\textbf{found-
edges}\neq\textbf{costly}({\textbf{canon}}^{+}(x,y))$. By Theorem 4.2,
$\textbf{Pr}[\textsc{OR-fingerprint}(x)\neq\textsc{OR-
fingerprint}(y)]\leq\frac{ks_{{\mathrm{OR}}}}{20ks_{{\mathrm{OR}}}}=\frac{1}{20}$
and by Theorem 7.2, $\textbf{Pr}[\textbf{found-
edges}\neq\textbf{costly}({\textbf{canon}}^{+}(x,y))]\leq\frac{1}{4}$ so the
overall error probability is less than 1/3..

It remains to prove Theorem 7.2 which is done in the sections that follow.
Since the hypothesis of Theorem 7.2 is that
$\textbf{ED}(x,y)<20ks_{{\mathrm{OR}}}$ this assumption is made throughout.

###  7.4 Normal executions

In this section we identify certain events in the execution of ED-sketch and
ED-recover as _abnormal_ and prove that the probability of an abnormal
execution tends to 0 as $n$ gets large.

On input $x$, ED-sketch constructs a sequence of sketches $\textbf{main-
sk}_{i}(x)$ for $i\in\\{1,\ldots,10s+50\\}$.

For each corresponding pair $\textbf{main-sk}_{i}(x)$ and $\textbf{main-
sk}_{i}(y)$, the recovery algorithm applies $\textsc{main-
reconstruct}(\textbf{main-sk}_{i}(x),\textbf{main-sk}_{i}(y))$. If the output
is defined then it is a set $\textbf{candids}_{i}$ of annotated edges. The set
$\textbf{candids}_{i}$ is supposed to “approximate”
$\textbf{costly}({\textbf{canon}}(x,y))$ in a suitable sense. The final output
found-edges of ED-recover is the set of annotated edges that appear in more
than half the sets of $\textbf{candids}_{i}$.

Each run of $\textsc{main-sketch}(x)$ constructs a labeling
$\textbf{substrs}(x)$ of the tree $T(W^{d})$ by substrings and another
labeling $\textbf{grams}(x)$ of the same tree where for each $v$,
$\textbf{grams}_{v}$ is a bit-vector of length ${N}$ that encodes a grammar
for $\textbf{grams}(x)$. By the properties of basic-decomp these labelings
satisfy:

$\textbf{D}_{1}$(x):

$\textbf{substrs}(x)$ is a decomposition tree for $x$

$\textbf{D}_{2}$(x):

For each node $v$ for which $\textbf{substrs}_{v}(x)\neq\varepsilon$,
$\textbf{grams}_{v}(x)$ is an encoding of $\textbf{substrs}_{v}(x)$, i.e.
$\textbf{substrs}_{v}(x)=\textsc{basic-decode}(\textbf{grams}_{v}(x))$, and
the number of 1’s in $\textbf{grams}_{v}(x)$ is at most $k_{v}$

We now identify four _abnormal events_. We will prove that it is very unlikely
that any of these conditions occur.

Fingerprinting abnormality.

There is a node $v$, such that
$\textbf{substrs}^{*}_{v}(x)\neq\textbf{substrs}^{*}_{v}(y)$ and
${\textbf{fingerprints}}^{*}_{v}(x)={\textbf{fingerprints}}^{*}_{v}(y)$.

Threshold detection abnormality.

There is a node $v$ at a level $j$, such that
$\textbf{ED}(\textbf{substrs}_{v}(x),$ $\textbf{substrs}_{v}(y))\geq t_{j}$
and $\textbf{OR-prints}_{v}(x)=\textbf{OR-prints}_{v}(y)$.

HMR abnormality.

One of the calls to hmr-recover within the recovery algorithm fails to satisfy
the Completeness and Soundness conditions (see Theorem 5.1).

An execution of $\textsc{ED-sketch}(x)$, $\textsc{ED-sketch}(y)$, and
$\textsc{ED-recover}(\textsc{ED-sketch}(x),\textsc{ED-sketch}(y))$ is
_abnormal_ if any of these abnormalities ever occurs and is _normal_ if no
such abnormality occurs. We define Normal to denote the event that the
execution is normal, and Abnormal to denote the event that the execution is
abnormal.

######  Lemma 7.3.

For any $x,y$, $\textbf{Pr}[\mathrm{\textbf{Abnormal}}\,]$ tends to 0 as $n$
gets large.

###### Proof.

First consider decomposition abnormality for $x$. The decomposition tree is
built in main-decomp, which grows a decomposition starting at the root by
calling basic-decomp on each node for which $\textbf{substrs}_{v}$ is
nonempty. $\textbf{D}_{1}$ or $\textbf{D}_{2}$ fail only if some of the calls
to basic-decomp returns undefined. By Theorem 4.3 the probability that a
particular call to $\textsc{basic-decomp}(z)$ returns undefined is at most
$1/n^{4}$. In a given call to $\textsc{main-decomp}(x)$, the number of
nonempty strings at each level of the decomposition is at most $|x|\leq n$ so
the number of calls made to $\textsc{basic-decomp}(z)$ for nonempty $z$ is at
most $dn$. So the probability that there is a call to basic-decomp that
returns undefined is at most $d/n^{3}$. If every call to basic-decomp is
defined then a simple induction using the properties of basic-decomp ensures
that the resulting tree satisfies $\textbf{D}_{1}$ and $\textbf{D}_{2}$.
Taking a union bound over the $10s+50$ calls to main-decomp still gives a
probability of abnormality that is $\leq 1/n$ for $n$ large enough. Similarly
for $y$.

The probability that a fingerprinting abnormality occurs at a particular node
$v\in\textbf{vis-nodes}^{*}$ is at most $1/n^{4}$ by Theorem 4.1. Similarly,
the probability that a threshold detection abnormality occurs at
$v\in\textbf{vis-nodes}$ is at most $1/n^{4}$ by Theorem 4.2. Taking a union
bound over the at most $sdn$ nodes in vis-nodes and $\textbf{vis-nodes}^{*}$,
and the $10s+50$ calls to main-sketch yields a probability of either of these
abnormalities that is at most $1/n$ for $n$ large enough.

An HMR abnormality occurs if one of the calls to hmr-recover fails. (A failure
of hmr-recover is determined by the randomness used to build the sketches of
$x$ and $y$). We set the failure parameter of the hierarchical mismatch
recovery scheme to be $1/n^{4}$ and the number of its instances is
$(sd)^{O(1)}$ so the overall probability of failure tends to zero as $n$
grows. ∎

###  7.5 Reduction to the main lemma

In this section we introduce the Main Lemma (Lemma 7.5) and use it to prove
Theorem 7.2.

We need to define some subsets of the and edge sets of $\textbf{Grid}(x,y)$.

The _$i$ -th vertical edge slice_ $S_{V}(i)$ of the grid graph
$\textbf{Grid}(x,y)$ consists of all edges that join a vertex with first
coordinate $i-1$ to a vertex with first coordinate $i$. The _$j$ -th
horizontal edge slice_ $S_{H}(j)$ consists of all edges that join a vertex
with second coordinate $j-1$ to a vertex with second coordinate $j$.

Note that a vertical edge slice consists of horizontal and diagonal edges but
not vertical edges, and a horizontal edge slice consists of vertical and
diagonal edges but not horizontal edges. The union of all of the slices is the
entire edge set of $\textbf{Grid}(x,y)$. We leave the proof of the following
observation to the reader.

######  Proposition 7.4.

Any spanning path of $\textbf{Grid}(x,y)$ contains exactly one edge from each
horizontal slice and from each vertical slice. In particular,
$\textbf{costly}({\textbf{canon}}(x,y))$ contains at most one edge from any
slice.

The sketch-and-recover scheme $\textsc{ED-sketch}+\textsc{ED-recover}$
operates by performing $10s+50$ independent executions of $\textsc{main-
sketch}+\textsc{main-reconstruct}$ and taking majority vote. The Main Lemma
below states the key property of a single instance of $\textsc{main-
sketch}+\textsc{main-reconstruct}$, and Theorem 7.2 follows easily from it.

######  Lemma 7.5.

(Main Lemma) Let $x,y$ be strings such that
$\textbf{ED}(x,y)<20ks_{{\mathrm{OR}}}$. Consider a single run of main-sketch
on $x$ and $y$ producing $\textbf{main-sk}(x)$ and $\textbf{main-sk}(y)$,
followed by a run of main-reconstruct on $\textbf{main-sk}(x),\textbf{main-
sk}(y)$, which produces the set candids of annotated edges. For any
(horizontal or vertical) edge slice $S$

$\textbf{Pr}[(\textbf{candids}\cap
S\neq\textbf{costly}({\textbf{canon}}(x,y))\cap
S){\;\wedge\;}\mathrm{\textbf{Normal}}\,]$

tends to 0 as $n$ gets large.

###### Proof of Theorem 7.2 assuming Lemma 7.5.

Assume $\textbf{ED}(x,y)<20ks_{{\mathrm{OR}}}$. We must establish an upper
bound on $\textbf{Pr}[\textbf{found-
edges}\neq\textbf{costly}({\textbf{canon}}^{+}(x,y))]$. We have:

$\displaystyle\textbf{Pr}[$ $\displaystyle\textbf{found-
edges}\neq\textbf{costly}({\textbf{canon}}^{+}(x,y))]$
$\displaystyle\leq\textbf{Pr}[\mathrm{\textbf{Abnormal}}\,]+\textbf{Pr}[\textbf{found-
edges}\neq\textbf{costly}({\textbf{canon}}^{+}(x,y)){\;\wedge\;}\mathrm{\textbf{Normal}}\,].$

Since the first term tends to 0 as $n$ gets large it suffices to prove:

$\textbf{Pr}[\textbf{found-
edges}\neq\textbf{costly}({\textbf{canon}}^{+}(x,y)){\;\wedge\;}\mathrm{\textbf{Normal}}\,]\leq\frac{1}{5},$
(1)

The hypothesis of the theorem assumes $n$ is sufficiently large. We choose $n$
large enough so that in Lemma 7.5 for any edge slice $S$ the probability that
$\textbf{candids}(x,y)\cap S\neq\textbf{costly}({\textbf{canon}}(x,y))\cap S$
is at most $1/10$.

We note that every edge of $\textbf{Grid}(x,y)$ lies in some (horizontal or
vertical) edge slice. It follows that $\textbf{found-
edges}=\textbf{costly}({\textbf{canon}}^{+}(x,y))$ if and only if for all edge
slices $S$ we have $\textbf{found-edges}\cap
S=\textbf{costly}({\textbf{canon}}^{+}(x,y))\cap S$. Define the bad event
$B(S)$ to be the event that for more than half of the sets
$(\textbf{candids}_{i}:i\in\\{1,\ldots,10s+50\\})$, $\textbf{candids}_{i}\cap
S\neq\textbf{costly}({\textbf{canon}}^{+}(x,y))\cap S$. By the definition of
found-edges, if $\textbf{found-
edges}\neq\textbf{costly}({\textbf{canon}}^{+}(x,y))$ then there is at least
one slice $S$ for which $B(S)$ happens and so:

$\textbf{Pr}[\textbf{found-
edges}\neq\textbf{costly}({\textbf{canon}}^{+}(x,y)){\;\wedge\;}\mathrm{\textbf{Normal}}\,]\leq\sum_{S}\textbf{Pr}[B(S){\;\wedge\;}\mathrm{\textbf{Normal}}\,].$

Consider a particular slice $S$. By Lemma 7.5 and the above choice of $n$, for
each $i$, $\textbf{Pr}[(\textbf{candids}_{i}\cap
S\neq\textbf{costly}({\textbf{canon}}^{+}(x,y))\cap
S){\;\wedge\;}\mathrm{\textbf{Normal}}\,]\leq 1/10$. Therefore the Chernoff-
Hoeffding bound (Lemma 3.7), implies that
$\textbf{Pr}[B(S){\;\wedge\;}\mathrm{\textbf{Normal}}\,]\leq
2e^{-0.32(10s+50)}$ which is easily less than
$\frac{1}{10}2^{-s}\leq\frac{1}{10n}$. Since the number of horizontal and
vertical slices are each at most $n$:

$\displaystyle\textbf{Pr}[\textbf{found-
edges}\neq\textbf{costly}({\textbf{canon}}^{+}(x,y)){\;\wedge\;}\mathrm{\textbf{Normal}}\,]$
$\displaystyle\leq$ $\displaystyle
2n\max_{S}\textbf{Pr}[B(S){\;\wedge\;}\mathrm{\textbf{Normal}}\,]$
$\displaystyle\leq$ $\displaystyle\frac{1}{5},$

as required to complete the proof of Theorem 7.2. ∎

It remains to prove Lemma 7.5.

###  7.6 Preliminaries for the proof of Lemma 7.5

Lemma 7.5 concerns a single execution of main-sketch applied to $x$ and $y$
producing outputs $\textbf{main-sk}(x)$ and $\textbf{main-sk}(y)$ and a single
instance of main-reconstruct applied to $\textbf{main-sk}(x)$ and
$\textbf{main-sk}(y)$.

$\textsc{main-sketch}(x)$ generates three (partial) labelings
$\textbf{substrs},\textbf{grams},$ and OR-prints of the nodes of the tree
$T(W^{d})$. $\textbf{substrs}(x)$ is a string decomposition tree of $x$. The
set $\textbf{vis-nodes}(x)$ is the set of nodes $v$ such that
$\textbf{substrs}_{v}(x)\neq\varepsilon$. For all $v\in\textbf{vis-nodes}$,
$\textbf{grams}_{v}(x)$ is a bit-vector of length ${N}$ such that
$\textsc{basic-decode}(\textbf{grams}_{v}(x))=\textbf{substrs}_{v}(x)$;
$\textbf{OR-prints}_{v}(x)$ is the Ostrovsky-Rabani fingerprint of
$\textbf{substrs}_{v}(x)$.

$\textsc{main-sketch}(x)$ also generates three partial labelings
$\textbf{substrs}^{*},\textbf{grams}^{*},$ and ${\textbf{fingerprints}}^{*}$
of the binary tree $T(\\{0,1\\}^{ds})$. $\textbf{substrs}^{*}(x)$ is a
refinement of $\textbf{substrs}(x)$ to the tree $T(\\{0,1\\}^{ds})$.
$\textbf{substrs}^{*}_{v}(x)$ is explicitly defined on the set $\textbf{vis-
nodes}^{*}$, consisting of those binary strings that are prefixes (ancestors)
of nodes in vis-nodes. For $v\in\textbf{vis-nodes}^{*}$, $\textbf{left-
size}^{*}(x)$ is the size of the string assigned by $\textbf{substrs}^{*}$ to
the left-child $v\circ 0$ of $v$, and ${\textbf{fingerprints}}^{*}_{v}(x)$ is
the Karp-Rabin fingerprint of $\textbf{substrs}^{*}_{v}(x)$.

The sketch $\textbf{main-sk}(x)$ consists of two separate sketches:
$\textbf{str-sk}(x)$ and $\textbf{loc-sk}(x)$. $\textbf{str-sk}(x)$ is a
sequence of $d$ HMR sketches $\textbf{str-sk}^{j}(x)$ produced by grammar-
condense, one for each layer of grammars in grams. $\textbf{loc-sk}(x)$ is a
sequence of $ds-1$ sketches $\textbf{loc-sk}^{j}(x)$ produced by location-
condense for each layer of $\textbf{left-size}^{*}(x)$ other than the last
layer.

We make the following definitions associated to $\textbf{substrs}(x)$ and
$\textbf{substrs}(y)$: For each node $v$:

  * •

$\textbf{I}_{v}(x)$ denotes the interval location
$\textbf{Loc}(\textbf{substrs})_{v}(x)$ where $\textbf{substrs}_{v}(x)$ is
located within $x$ (as defined in Section 3.1). $\textbf{start}_{v}(x)$ is the
left endpoint of $\textbf{I}_{v}(x)$. This is equal to the sum of the lengths
of all strings at leaves that are to the left of (lexicographically precede)
$v$. Note that
$\textbf{I}_{v}(x)=(\textbf{start}_{v}(x),\textbf{start}_{v}(x)+|\textbf{substrs}_{v}(x)|]$.

  * •

$\textbf{Grid}_{v}$ denotes the subgrid
$\textbf{Grid}_{\textbf{I}_{v}(x)\times\textbf{I}_{v}(y)}$, and
$\textbf{E}_{v}=\textbf{E}_{v}(x,y)$ denotes the set of its edges.
$\textbf{E}_{v}^{+}$ denotes the set of annotated edges
$\\{e^{+}:e\in\textbf{E}_{v}\\}$.

  * •

$\textbf{ED}_{v}=\textbf{ED}(\textbf{substrs}_{v}(x),\textbf{substrs}_{v}(y))$,
and the canonical path
${\textbf{canon}}(x,y)_{\textbf{I}_{v}(x)\times\textbf{I}_{v}(y)}$ is denoted
by ${\textbf{canon}}_{v}$. $\textbf{costly}({\textbf{canon}}_{v})$ is the set
of costly edges of ${\textbf{canon}}_{v}$ (which has size $\textbf{ED}_{v}$),
and $\textbf{costly}({\textbf{canon}}^{+}_{v})$ is the set of costly edges
with annotations.

The procedure main-reconstruct, using subroutines find-strings and find-
locations constructs a set candids of annotated edges as follows:

  * •

find-strings takes as input $\textbf{str-sk}(x)$ and $\textbf{str-sk}(y)$ and
constructs (partial) labelings $\textbf{found-str}(x)$ and $\textbf{found-
str}(y)$ of the tree $T(W^{d})$. For a node $v\in W^{\leq d}$, if
$\textbf{found-str}_{v}(x)$ (resp. $\textbf{found-str}_{v}(y)$) is defined,
its value is a string.

  * •

find-locations takes as input $\textbf{loc-sk}(x)$ and $\textbf{loc-sk}(y)$
and constructs two (partial) labelings $\textbf{found-start}(x)$ and
$\textbf{found-start}(y)$ of $T(W^{d})$. For a node $v\in W^{d}$, if
$\textbf{found-start}_{v}(x)$ (resp. $\textbf{found-str}_{v}(y)$) is defined,
its value is a nonnegative integer.

  * •

In main-reconstruct, the set loc-nodes is defined to be the set of nodes $v$
for which $\textbf{found-str}_{v}(x)$, $\textbf{found-str}_{v}(y)$,
$\textbf{found-start}_{v}(x)$ and $\textbf{found-start}_{v}(y)$ are all
defined.

  * •

In main-reconstruct the set top-nodes is defined to be the subset of loc-nodes
consisting of those nodes in loc-nodes that have no ancestor in loc-nodes.

  * •

For each node $v\in\textbf{top-nodes}$, main-reconstruct computes a set of
annotated edges $\textbf{candids}_{v}$.

  * •

The output of main-reconstruct is the set
$\textbf{candids}=\bigcup_{v\in\textbf{top-nodes}}\textbf{candids}_{v}$.

For each $v\in\textbf{top-nodes}$ the set $\textbf{candids}_{v}$ is computed
in main-reconstruct as follows. $\textbf{found-str}_{v}(x)$ and
$\textbf{found-str}_{v}(y)$ together with $\textbf{found-start}_{v}(x)$ and
$\textbf{found-start}_{v}(y)$ determine an edit distance problem, and that
problem has a unique canonical path. The set of costly annotated edges in that
path is $\textbf{candids}_{v}$. In the procedure main-reconstruct,
$\textbf{candids}_{v}$ is evaluated only for $v\in\textbf{top-nodes}$, but the
definition makes sense for all $v\in\textbf{loc-nodes}$, and in what follows
we will refer to $\textbf{candids}_{v}$ for $v\in\textbf{loc-nodes}$.

We are hoping that candids is close, in a suitable probabilistic sense to the
set $\textbf{costly}({\textbf{canon}}^{+}(x,y))$. To show this we will need to
consider certain properties for classifying nodes.

The first set of properties is determined by $\textbf{substrs}_{v}(x)$ and
$\textbf{substrs}_{v}(y)$ produced by the main-sketch.

  * •

$v$ is _compatible_ if the box $\textbf{I}_{v}(x)\times\textbf{I}_{v}(y)$ is
$(x,y)$-compatible. (Recall that the box $I\times J$ is $(x,y)$-compatible
provided that the the canonical alignment ${\textbf{canon}}(x,y)$ passes
through the corner points of $\textbf{I}_{v}(x)\times\textbf{I}_{v}(y)$.) The
importance of this property is that if $v$ is compatible then
${\textbf{canon}}_{v}$ is equal to ${\textbf{canon}}(x,y)\cap\textbf{E}_{v}$,
the portion of ${\textbf{canon}}(x,y)$ that lies inside $\textbf{Grid}_{v}$.
This means that if we are able to reconstruct the substrings
$\textbf{substrs}_{v}(x)$ and $\textbf{substrs}_{v}(y)$ and the intervals
$\textbf{I}_{v}(x)$ and $\textbf{I}_{v}(y)$,
$\textbf{costly}({\textbf{canon}}^{+}_{v})$ will give us the portion of
$\textbf{costly}({\textbf{canon}}^{+}(x,y))$ that lies inside of
$\textbf{Grid}_{v}$.

  * •

$v$ is _compatibly split_ provided that all of the children of $v$ are
compatible. This depends on the run of basic-decomp on the strings
$\textbf{substrs}_{v}(x)$ and $\textbf{substrs}_{v}(y)$ that occurs inside of
main-decomp.

We say that:

  * •

_$\textbf{found-str}_{v}(x)$ (respectively, $\textbf{found-str}_{v}(y)$) is a
correct reconstruction_ provided that it is defined and equal to
$\textbf{substrs}_{v}(x)$ (respective, $\textbf{substrs}_{v}(y)$).

  * •

_$\textbf{found-start}_{v}(x)$ (resp. $\textbf{found-start}_{v}(y)$) is a
correct reconstruction_ provided that it is defined and equal to
$\textbf{start}_{v}(x)$ (resp. $\textbf{start}_{v}(y)$).

  * •

We say that _$v$ is correctly reconstructed_ if $\textbf{found-str}_{v}(x)$,
$\textbf{found-str}_{v}(y)$, $\textbf{found-start}_{v}(x)$ and $\textbf{found-
start}_{v}(y)$ are all correct reconstructions.

######  Lemma 7.6.

Let $v\in W^{\leq d}$. Under a normal execution:

  1. 1.

If $\textbf{found-str}_{v}(x)$ and $\textbf{found-str}_{v}(y)$ are both
defined by find-strings then $\textbf{found-
str}_{v}(x)=\textbf{substrs}_{v}(x)$ and $\textbf{found-
str}_{v}(y)=\textbf{substrs}_{v}(y)$.

  2. 2.

If $\textbf{found-start}_{v}(x)$ and $\textbf{found-start}_{v}(y)$ are both
defined by find-locations then $\textbf{start}_{v}(x)=\textbf{found-
start}_{v}(x)$ and $\textbf{start}_{v}(y)=\textbf{found-start}_{v}(y)$.

###### Proof.

Fix a node $v\in W^{\leq d}$ and let $j=|v|$.

Proof of 1. $\textbf{found-str}_{v}(x)$ and $\textbf{found-str}_{v}(y)$ are
determined during iteration $j$ of the main loop in find-strings as follows:
$\textsc{hmr-recover}(\textbf{str-sk}^{j}(x),\textbf{str-sk}^{j}(y))$ is
evaluated and assigned to $\textbf{gram-mismatch}^{j}$. This is a set of
mismatch triples of the form $((w,i),\alpha,\beta)$ where $(w,i)\in
W^{j}\times\\{1,\ldots,{N}\\}$, and $\alpha\neq\beta\in\mathbb{F}$. Letting
$\textbf{gram-mismatch}^{j}_{v}$ denote the set of those triples involving the
node $v$, $\textbf{found-gram}_{v}(x)$ and $\textbf{found-gram}_{v}(y)$ are
determined by $\textbf{gram-mismatch}^{j}_{v}$.

Under a normal execution, the call to hmr-recover is Sound, so $\textbf{gram-
mismatch}^{j}_{v}$ is a subset of the mismatch information
${\mathrm{MIS}}(\textbf{grams}^{j}_{v}(x),\textbf{grams}^{j}_{v}(y))$.

######  Claim 7.7.

$\textbf{found-gram}_{v}(x)\leq\textbf{grams}_{v}(x)$ and $\textbf{found-
gram}_{v}(y)\leq\textbf{grams}_{v}(y)$, where $\leq$ is entry-wise.

###### Proof.

We prove the first inequality; the second is analogous. Fix an index
$i\in\\{1,\ldots,{N}\\}$. Assume that $\textbf{found-gram}_{v,i}(x)=1$ we must
show that $\textbf{grams}_{v,i}(x)=1$. From the construction of
$\textbf{found-gram}(x)$ in find-strings, $\textbf{found-gram}_{v,i}(x)=1$
implies that there is a mismatch triple $((v,i),\alpha,\beta)\in\textbf{gram-
mismatch}^{j}$ such that $\alpha\neq 0$. Since $\textbf{gram-
mismatch}^{j}\subseteq{\mathrm{MIS}}(\textbf{grams}^{j}(x),\textbf{grams}^{j}(y))$
this implies that $\textbf{grams}^{j}_{v,i}(x)=\alpha\neq 0$ which implies
that $\textbf{grams}_{v,i}(x)c=1$ by the definition of $\textbf{grams}^{j}$. ∎

Now if $\textbf{found-gram}_{v}(x)=\textbf{grams}_{v}(x)$ and $\textbf{found-
gram}_{v}(y)=\textbf{grams}_{v}(y)$ then we have $\textbf{found-
str}_{v}(x)=\textsc{basic-decode}(\textbf{found-gram}_{v}(x))=\textsc{basic-
decode}(\textbf{grams}_{v}(x))=\textbf{substrs}_{v}(x)$ and similarly
$\textbf{found-str}_{v}(y)=\textbf{substrs}_{v}(y)$. The conclusion of the
first implication holds in this case. Now consider the case $\textbf{found-
gram}_{v}(x)\neq\textbf{grams}_{v}(x)$. By Claim 7.7, $\textbf{found-
gram}_{v}(x)<\textbf{grams}_{v}(x)$. By the minimality property of basic-
decode (see Section 4.3) $\textbf{found-str}_{v}(x)=\textsc{basic-
decode}(\textbf{found-gram}_{v}(x))$ is undefined. So the premise of the
implication does not hold. Similarly when $\textbf{found-
gram}_{v}(y)\neq\textbf{grams}_{v}(y)$. This completes the proof of the first
part of the lemma.

The argument for the second part of the lemma is similar, but has important
differences. $\textbf{found-start}_{v}(x)$ and $\textbf{found-start}_{v}(y)$
are determined in find-locations. The main loop of find-locations has $ds$
iterations, corresponding to the levels of the binary tree
$T(\\{0,1\\}^{ds})$. In iteration $i$, hmr-recover is applied to $\textbf{loc-
sk}^{i}(x),\textbf{loc-sk}^{i}(y)$ to produce $\textbf{size-mismatch}^{i}$.
The sketches $\textbf{loc-sk}^{i}(x)$ and $\textbf{loc-sk}^{i}(y)$ are
sketches of the $D$-vectors $\textbf{left-size}^{i}(x)$ and $\textbf{left-
size}^{i}(y)$ for $D=\\{0,1\\}^{i}$. $\textbf{size-mismatch}^{i}$ is a set of
mismatch triples of the form $(w,\alpha,\beta)$ where $w\in\\{0,1\\}^{i}$ and
$\alpha,\beta\in\mathbb{F}$. Let $L_{i}$ be the subset of nodes $u$ that
appear as first coordinate of some mismatch triple in $\textbf{size-
mismatch}^{i}$. $\textbf{size-mismatch}^{i}$ is used to define $\textbf{found-
size}_{u}(x)$ and $\textbf{found-size}_{u}(y)$ for all $u\in L_{i}$. The
soundness of hmr-recover (since the execution is normal) implies
$L_{i}\subseteq{\mathrm{MIS}}(\textbf{left-size}^{i}(x),\textbf{left-
size}^{i}(y))$ and this implies $\textbf{found-size}_{u}(x)=\textbf{left-
size}_{u}(x)$ and $\textbf{found-size}_{u}(y)=\textbf{left-size}_{u}(y)$.

Now $\textbf{found-start}_{v}(x)$ is the sum of $\textbf{found-size}_{u}(x)$
over left ancestors $u$ of $v$. It is undefined if any of the summands is
undefined. If all summands are defined, then by the above, the sum is equal to
the sum of $\textbf{left-size}_{u}(x)$ over all left ancestors $u$ of $v$
which is equal to $\textbf{start}_{v}(x)$. The same argument applies to show
$\textbf{found-start}_{v}(y)=\textbf{start}_{v}(y)$, completing the proof of
the second part of the lemma. ∎

######  Corollary 7.8.

Under a normal execution, suppose that $v\in W^{\leq d}$ is placed in loc-
nodes by main-reconstruct. Then

  1. 1.

Then $v$ is correctly reconstructed, i.e.
$\textbf{candids}_{v}=\textbf{costly}({\textbf{canon}}^{+}_{v})$.

  2. 2.

If, in addition, $v$ is compatible, then
$\textbf{candids}_{v}=\textbf{costly}({\textbf{canon}}^{+}(x,y))\cap\textbf{E}^{+}_{v}$.

###### Proof.

By the code for main-reconstruct, $v\in\textbf{loc-nodes}$ implies
$\textbf{found-str}_{v}(y)$, $\textbf{found-start}_{v}(x)$ and $\textbf{found-
start}_{v}(y)$ are all defined, and $\textbf{candids}_{v}$ is the set of
costly edges in the canonical path for the edit distance problem defined by
$\textbf{found-str}_{v}(x)$, $\textbf{found-str}_{v}(y)$, $\textbf{found-
start}_{v}(x)$ and $\textbf{found-start}_{v}(y)$. By Lemma 7.6, this is equal
to the set of costly edges in the canonical path associated to
$\textbf{substrs}_{v}(x)$, $\textbf{substrs}_{v}(y)$, $\textbf{I}_{v}(x)$ and
$\textbf{I}_{v}(y)$ which is the set ${\textbf{canon}}^{+}_{v}$. For the
second part, when $v$ is compatible, the conclusion follows from the first
part together with Proposition 3.5. ∎

##  8 Proof of Lemma 7.5.

Suppose $S$ is an arbitrary slice. Without loss of generality, assume that
$S=S_{V}(b)$ is the $b$-th vertical edge slice. We say that _slice $S$ is
correctly reconstructed_ provided that $\textbf{candids}(x,y)\cap
S=\textbf{costly}({\textbf{canon}}^{+}(x,y))\cap S$. We need to show:

$\textbf{Pr}[\text{slice $S$ is not correctly
reconstructed}{\;\wedge\;}\mathrm{\textbf{Normal}}\,]\rightarrow 0$ (2)

as $n$ gets large.

Since $\textbf{substrs}(x)$ is a string decomposition tree of $x$, for each
level $j\in\\{0,\ldots,d\\}$ there is a unique node $w(j)$ of $T(W^{d})$ such
that $b\in\textbf{I}_{w(j)}(x)$, and the sequence $w(0),\ldots,w(d)$ forms a
root-to-leaf path. The following lemma implies that, under a normal execution,
whether $S$ is correctly reconstructed only depends on the reconstruction of
nodes in $w(0),\ldots,w(d)$.

######  Proposition 8.1.

Assume a normal execution, and suppose $S$ is the $b$th vertical edge slice.

  1. 1.

$\textbf{candids}\cap S=\bigcup_{j\in\\{0,\ldots,d\\}:w(j)\in\textbf{top-
nodes}}\textbf{candids}_{w(j)}\cap S$

  2. 2.

If $w(j)$ is compatible and $w(j)\in\textbf{loc-nodes}$ then
$\textbf{candids}_{w(j)}\cap S=\textbf{costly}({\textbf{canon}}^{+})\cap S$.

###### Proof.

For (1), by definition in main-reconstruct $\textbf{candids}\cap
S=\bigcup_{v\in\textbf{top-nodes}}\textbf{candids}_{v}\cap S$. To establish
the claimed equality it suffices to show that $\textbf{candids}_{v}\cap
S=\emptyset$ for $v\not\in\\{w(0),\ldots,w(d)\\}$. By Corollary 7.8,
$\textbf{candids}_{v}=\textbf{costly}({\textbf{canon}}^{+}_{v})$. The path
${\textbf{canon}}_{v}$ only contains edges in vertical slices $S_{V}(\ell)$
for which $\ell\in\textbf{I}_{v}(x)$. Since $b\not\in\textbf{I}_{v}(x)$,
${\textbf{canon}}_{v}\cap S=\emptyset$.

For (2), suppose $w(j)$ is compatible. By Corollary 7.8(2),
$\textbf{candids}_{w(j)}=\textbf{costly}({\textbf{canon}}^{+})\cap\textbf{E}^{+}_{w(j)}$.
Since $b\in\textbf{I}_{w(j)}(x)$, $\textbf{E}^{+}_{w(j)}$ includes the edge of
canon from slice $S$, and the equality follows. ∎

As a corollary we get a sufficient condition for $S$ to be correctly
reconstructed:

######  Corollary 8.2.

Assume a normal execution. If either of the following conditions hold then $S$
is correctly reconstructed:

  1. 1.

$\textbf{costly}({\textbf{canon}}^{+})\cap S=\emptyset$ and none of the nodes
$w(0),\ldots,w(d)$ is in loc-nodes.

  2. 2.

There is an index $j\in\\{1,\ldots,d\\}$ such that $w(j)\in\textbf{loc-nodes}$
and $w(0),\ldots,w(j)$ are all compatible.

###### Proof.

For (1), if $\\{w(0),\ldots,w(d)\\}\cap\textbf{loc-nodes}=\emptyset$ then by
Proposition 8.1(1), $\textbf{candids}\cap
S=\emptyset=\textbf{costly}({\textbf{canon}}^{+})\cap S$.

For (2), let $j$ be the least index satisfying the hypothesis of (2). By
definition of top-nodes in main-reconstruct, $w(j)$ is the unique node among
$w(0),\ldots,w(d)$ that belongs to top-nodes and so by Proposition 8.1(1),
$\textbf{candids}\cap S=\textbf{candids}_{w(j)}\cap S$, which is equal to
$\textbf{costly}({\textbf{canon}}^{+})\cap S$ by Proposition 8.1(2). ∎

Our strategy is to show that with fairly high probability one of the two
sufficient conditions of this corollary is satisfied. To this end we define
the following events, indexed by $j\in\\{0,\ldots,d\\}$:

$\textbf{T}(j)$

is the event that $\textbf{ED}_{w(j)}<t_{j}$.

$\textbf{T}(\leq j)$

is the event that $\textbf{ED}_{w(i)}<t_{i}$ for all $i\leq j$.

$\textbf{C}(j)$

is the event that $w(j)$ is compatible.

$\textbf{C}(\leq j)$

is the event that $w(0),\ldots,w(j)$ are all compatible.

Recall that we have a global hypothesis that $\textbf{ED}(x,y)<\lceil
20ks_{{\mathrm{OR}}}\rceil_{2}=t_{0}$, so that $\textbf{T}(0)$ holds. Also,
$\textbf{C}(0)$ holds trivially. The following proposition says that if
$\textbf{ED}_{w(j)}<t_{j}$ and $w(j)$ is compatible then $w(j+1)$ is almost
certainly compatible:

######  Proposition 8.3.

  1. 1.

For all $j\in\\{1,\ldots,d\\}$,
$\textbf{Pr}[\textbf{T}(j-1){\;\wedge\;}\textbf{C}(j-1){\;\wedge\;}\neg\textbf{C}(j){\;\wedge\;}\mathrm{\textbf{Normal}}\,]\leq\frac{1}{\log^{2}n}$.

  2. 2.

$\textbf{Pr}[\exists j\in\\{1,\ldots,d\\}\text{ such that }\textbf{T}(\leq
j-1){\;\wedge\;}\neg\textbf{C}(\leq
j){\;\wedge\;}\mathrm{\textbf{Normal}}\,]\leq\frac{1}{\log n}$.

###### Proof.

For (1), note that events $\textbf{T}(j-1)$ and $\textbf{C}(j-1)$ are
determined by the first $j-1$ levels of $\textbf{substrs}(x)$ and
$\textbf{substrs}(y)$. Consider an arbitrary setting of the first $j-1$ levels
of $\textbf{substrs}(x)$ and $\textbf{substrs}(y)$ for which $\textbf{T}(j-1)$
and $\textbf{C}(j-1)$ hold. Then $\textbf{ED}_{w(j-1)}<t_{j-1}$. By Theorem
4.3, the conditional probability given this setting that $w(j-1)$ is not
compatibly split is at most:

$\frac{{s_{{\mathrm{split}}}\,}\textbf{ED}_{w(j-1)}}{k_{j}}\leq\frac{{s_{{\mathrm{split}}}\,}t_{j-1}}{k_{j}}\leq\frac{1}{\log^{2}n},$
(3)

where the final inequality uses the definitions of $t_{j-1}$ and $k_{j}$.
Since this holds for any setting of the first $j-1$ levels of
$\textbf{substrs}(x)$ and $\textbf{substrs}(y)$ for which $\textbf{T}(j-1)$
and $\textbf{C}(j-1)$ hold, we conclude that:

$\textbf{Pr}[\textbf{T}(j-1){\;\wedge\;}\textbf{C}(j-1){\;\wedge\;}\neg\textbf{C}(j){\;\wedge\;}\mathrm{\textbf{Normal}}\,]\leq\frac{1}{\log^{2}n},$

as required for (1).

For (2), if there is an index $j$ such that $\textbf{T}(\leq
j-1){\;\wedge\;}\neg\textbf{C}(\leq j)$ and $i$ is the least such index then
$\textbf{T}(i-1){\;\wedge\;}\textbf{C}(i-1){\;\wedge\;}\neg\textbf{C}(i)$
holds. Therefore:

$\textbf{Pr}[\exists j\in\\{1,\ldots,d\\},\textbf{T}(\leq
j-1){\;\wedge\;}\neg\textbf{C}(\leq
j){\;\wedge\;}\mathrm{\textbf{Normal}}\,]\\\
\leq\sum_{i=1}^{j}\textbf{Pr}[\textbf{T}(j-1){\;\wedge\;}\textbf{C}(j-1){\;\wedge\;}\neg\textbf{C}(j){\;\wedge\;}\mathrm{\textbf{Normal}}\,]\leq\frac{j}{\log^{2}n}\leq\frac{1}{\log
n}$ (4)

where the second to last inequality uses the first part of this proposition. ∎

Let $q\in\\{0,\ldots,d\\}$ be the largest index for which $\textbf{T}(q)$
holds. We emphasize that $q$ is a random variable that depends on the
execution. The following result says that with fairly high probability
$w(0),\ldots,w(q)$ are all compatible and if $q<d$ then with fairly high
probability $w(q+1)$ is also compatible.

######  Corollary 8.4.

  1. 1.

$\textbf{Pr}[(q<d){\;\wedge\;}\text{$w(0),\ldots,w(q+1)$ are not all
compatible }{\;\wedge\;}\mathrm{\textbf{Normal}}\,]\leq\frac{1}{\log n}$.

  2. 2.

$\textbf{Pr}[(q=d){\;\wedge\;}\text{$w(0),\ldots,w(d)$ are not all compatible
}{\;\wedge\;}\mathrm{\textbf{Normal}}\,]\leq\frac{1}{\log n}$.

###### Proof.

For both parts, $\textbf{T}(\leq q)$ holds so the event whose probability is
being bounded is included in the event whose probability is bounded in the
second part of Proposition 8.3. ∎

To prove (2) we need an upper bound on:

$\textbf{Pr}[\text{$S$ is not correctly
reconstructed}{\;\wedge\;}\mathrm{\textbf{Normal}}\,]\\\
=\textbf{Pr}[\text{$S$ is not correctly
reconstructed}{\;\wedge\;}\mathrm{\textbf{Normal}}\,{\;\wedge\;}(q=d)]\\\
+\textbf{Pr}[\text{$S$ is not correctly
reconstructed}{\;\wedge\;}\mathrm{\textbf{Normal}}\,{\;\wedge\;}(q<d)]$ (5)

The first term is easy to bound:

######  Proposition 8.5.

$\textbf{Pr}[\text{$S$ is not correctly
reconstructed}{\;\wedge\;}\mathrm{\textbf{Normal}}\,{\;\wedge\;}(q=d)]\leq\frac{1}{\log
n}$

###### Proof.

We write the probability as:

$\textbf{Pr}[\text{$S$ is not correctly
reconstructed}{\;\wedge\;}\mathrm{\textbf{Normal}}\,{\;\wedge\;}(q=d)]\\\
=\textbf{Pr}[\text{$S$ is not correctly
reconstructed}{\;\wedge\;}\mathrm{\textbf{Normal}}\,{\;\wedge\;}(q=d){\;\wedge\;}\textbf{C}(\leq
d)]\\\ +\textbf{Pr}[\text{$S$ is not correctly
reconstructed}{\;\wedge\;}\mathrm{\textbf{Normal}}\,{\;\wedge\;}(q=d){\;\wedge\;}\neg\textbf{C}(\leq
d)].$ (6)

In the final expression, the second term is at most $\frac{1}{\log n}$ by
Corollary 8.4(2). We claim that the first term is 0. To prove this we assume a
normal execution where $q=d$ and $\textbf{C}(\leq d)$ both hold and show that
$S$ is necessarily correctly reconstructed. Since $\textbf{C}(\leq d)$ holds,
every node in $w(0),w(1),\ldots,w(d)$ is compatible. If one of them belongs to
loc-nodes then by Corollary 8.2(2), $S$ is correctly reconstructed.

Now assume that no node of $\\{w(0),\ldots,w(d)\\}$ belongs to loc-nodes. By
assumption, $\textbf{ED}_{w(d)}<t_{d}=1$, which implies that
$\textbf{substrs}_{w(d)}(x)$ and $\textbf{substrs}_{w(d)}(y)$ are the same
string, which implies that
$\textbf{costly}({\textbf{canon}}_{w(d)})=\emptyset$, and the desired
conclusion follows from Corollary 8.2(1). ∎

To bound the second term in (5), we have:

$\textbf{Pr}[\text{$S$ not correctly
reconstructed}{\;\wedge\;}\mathrm{\textbf{Normal}}\,{\;\wedge\;}(q<d)]=\\\
\textbf{Pr}[\text{$S$ is not correctly
reconstructed}{\;\wedge\;}\mathrm{\textbf{Normal}}\,{\;\wedge\;}(q<d){\;\wedge\;}\neg\textbf{C}(\leq
q+1)]+\\\ \textbf{Pr}[\text{$S$ is not correctly
reconstructed}{\;\wedge\;}\mathrm{\textbf{Normal}}\,{\;\wedge\;}(q<d){\;\wedge\;}\textbf{C}(\leq
q+1)].$ (7)

The first term is at most $\frac{1}{\log n}$ by the Corollary 8.4(1). To bound
the second term define the events:

STR$(v)$:

$\textbf{found-str}_{v}(x)$ and $\textbf{found-str}_{v}(y)$ are both defined.

LOC$(v)$:

$\textbf{found-start}_{v}(x)$ and $\textbf{found-start}_{v}(y)$ are both
defined.

We will prove:

######  Lemma 8.6.

$\textbf{Pr}[\neg\textbf{STR}(w(q+1)){\;\wedge\;}\mathrm{\textbf{Normal}}\,{\;\wedge\;}(q<d){\;\wedge\;}\textbf{C}(\leq
q+1)]\leq\frac{1}{\log n}.$

######  Lemma 8.7.

$\textbf{Pr}[\neg\textbf{LOC}(w(q+1)){\;\wedge\;}\mathrm{\textbf{Normal}}\,{\;\wedge\;}(q<d){\;\wedge\;}\textbf{C}(\leq
q+1)]\leq\frac{1}{\log n}.$

$\textbf{STR}(w(q+1))$ and $\textbf{LOC}(w(q+1))$ together imply that $w(q+1)$
is correctly reconstructed. If in addition $\textbf{C}(w(q+1))$ holds then by
Corollary 8.2(2), $S$ is correctly reconstructed. Therefore these two lemmas
imply:

Pr $\displaystyle[\text{$S$ is not correctly
reconstructed}{\;\wedge\;}\mathrm{\textbf{Normal}}\,{\;\wedge\;}(q<d){\;\wedge\;}\textbf{C}(\leq
q+1)]\leq$
$\displaystyle\textbf{Pr}[\neg\textbf{STR}(w(q+1)){\;\wedge\;}\mathrm{\textbf{Normal}}\,{\;\wedge\;}(q<d){\;\wedge\;}\textbf{C}(\leq
q+1)]+$
$\displaystyle\textbf{Pr}[\neg\textbf{LOC}(w(q+1)){\;\wedge\;}\mathrm{\textbf{Normal}}\,{\;\wedge\;}(q<d){\;\wedge\;}\textbf{C}(\leq
q+1)]\leq\frac{2}{\log n}.$

This bounds the second term on the right of (7). Combined with the upper bound
on the first term we have $\textbf{Pr}[\text{$S$ not correctly
reconstructed}{\;\wedge\;}\mathrm{\textbf{Normal}}\,{\;\wedge\;}(q<d)]\leq\frac{3}{\log
n}$, and combining this with Proposition 8.5 yields $\textbf{Pr}[\text{$S$ is
not correctly
reconstructed}{\;\wedge\;}\mathrm{\textbf{Normal}}\,]\leq\frac{4}{\log n}$ as
required for Lemma 7.5.

To prove Lemmas 8.6 and 8.7 we will need.

######  Proposition 8.8.

Assume a normal execution for strings $x$,$y$. Let $v\in W^{\leq d}$ with
$j=|v|$ such that $\textbf{substrs}_{v}(x)\neq\textbf{substrs}_{v}(y)$.

  1. 1.

The following two conditions are together sufficient for $\textbf{found-
str}_{v}(x)$ and $\textbf{found-str}_{v}(y)$ to both be defined:

    1. (a)

$\textbf{OR-prints}_{v}(x)\neq\textbf{OR-prints}_{v}(y)$

    2. (b)

For the HMR-recovery problem associated to
$(\textbf{grams}^{j},T(W^{j}\times\\{1,\dots,{N}\\}),\kappa^{\leq
j},4(d+1),1/n^{4})$ (see the procedure grammar-condense), all of the nodes
$v_{\leq 0},\ldots,v_{\leq j-1}$ are $\frac{1}{4(d+1)}$-underloaded (as
defined in Section 5.1)

  2. 2.

The following condition is sufficient for $\textbf{found-start}_{v}(x)$ and
$\textbf{found-start}_{v}(y)$ to both be defined: View $v$ as a node of
$T(\\{0,1\\}^{ds})$ where its depth is $js$. For every $i\leq js$, for the
HMR-recovery problem associated to $(\textbf{left-
size}^{i},T(\\{0,1\\}^{i}),\lambda^{\leq i},4ds,1/n^{4})$ all of the nodes
$v_{\leq 0},\ldots,v_{\leq i-1}$ are $\frac{1}{4ds}$-underloaded.

###### Proof.

In both parts we apply Theorem 5.1. Since the execution is normal, there is no
HMR-abnormality so all executions of hmr-recover satisfy Completeness (see
Section 5.1), that every mismatch triple with accessible index is correctly
recovered, and Soundness, that no incorrect triple is recovered.

When hmr-recover is applied to $\textsc{hmr-recover}(\textbf{str-
sk}^{j}(x),\textbf{str-sk}^{j}(y))$ it recovers all $\frac{1}{4d}$-accessible
mismatch triples correctly. We claim that all indices belonging to
$\\{(v,i):i\in\\{1,\ldots,{N}\\}\\}$ are $\frac{1}{4d}$-accessible and for
this we need that $v_{\leq 0},\ldots,v_{\leq j}=v$ are all
$\frac{1}{4d}$-underloaded. Condition 2(b) says that $v_{\leq
0},\ldots,v_{\leq j-1}$ are all $\frac{1}{4d}$-underloaded. $v$ itself is also
$\frac{1}{4d}$-underloaded, because the load on $v$ is at most the number of
mismatches between $\textbf{grams}^{j}_{v}(x)$ and $\textbf{grams}^{j}_{v}(y)$
which is at most the total number of non-zero entries in both. By Theorem 4.3,
$\textbf{grams}_{v}(x)$ and $\textbf{grams}_{v}(y)$ each have at most $k_{j}$
non-zero entries, so the load of $v$ is at most $2k_{j}$ which is at most
$\frac{1}{4\log(n)}\kappa_{j}$ (with room to spare).

Therefore all indices in $\\{(v,i):i\in\\{1,\ldots,{N}\\}\\}$ are
$\frac{1}{4d}$-accessible and so all mismatches between
$\textbf{grams}^{j}_{v}(x)$ and $\textbf{grams}^{j}_{v}(y)$ are recovered
correctly. Thus $\textbf{found-gram}_{v}(x)=\textbf{grams}_{v}(x)$ and
$\textbf{found-gram}_{v}(y)=\textbf{grams}_{v}(y)$ and so $\textsc{basic-
decode}(\textbf{found-gram}_{v}(x))=\textbf{substrs}_{v}(x)$ and
$\textsc{basic-decode}(\textbf{found-gram}_{v}(y)=\textbf{substrs}_{v}(y)$,
completing the proof of the first part.

For the second part, we are now working on the binary tree
$T(\\{0,1\\}^{ds}$), from the code for find-locations, if $\textbf{found-
size}_{v_{\leq i}}(x)$ is defined for all $i<j$ then $\textbf{found-
start}_{v}(x)$ will be defined. $\textbf{found-size}_{v_{\leq i}}(x)$ is
defined from the run of hmr-recover on the HMR-sketch of $(\textbf{left-
size}^{i},$ $T(\\{0,1\\}^{i}),$ $\lambda^{\leq i},$ $4ds,1/n^{4})$. The
mismatch triples of this run correspond to nodes $w$ at level $i$ for which
$\textbf{left-size}^{i}_{w}(x)\neq\textbf{left-size}^{i}_{w}(y)$ or
${\textbf{fingerprints}}^{*}_{w}(x)\neq{\textbf{fingerprints}}^{*}_{w}(y)$.
Since we are assuming a normal execution,
${\textbf{fingerprints}}^{*}_{w}(x)\neq{\textbf{fingerprints}}^{*}_{w}(y)$ if
and only if $\textbf{substrs}^{*}_{w}(x)\neq\textbf{substrs}^{*}_{w}(y)$.
Since $\textbf{substrs}_{v}(x)\neq\textbf{substrs}_{v}(y)$ by hypothesis, it
follows that $\textbf{substrs}_{w}(x)\neq\textbf{substrs}_{w}(y)$ for all
ancestors $w$ of $v$. (If $\textbf{substrs}_{w}(x)=\textbf{substrs}_{w}(y)$
then basic-decomp acts identically on both and so the $\textbf{substrs}(x)$
and $\textbf{substrs}(y)$ would be identical below $w$.) Therefore for $i\leq
j$, there is a mismatch triple corresponding to $v_{\leq i}$. Thus in the HMR-
recovery problem associated to $(\textbf{left-
size}^{i},T(\\{0,1\\}^{i}),\lambda^{\leq i},4ds,1/n^{4})$, if every node on
the path from $v_{\leq i}$ to the root (including $v_{\leq i}$) is
$\frac{1}{4ds}$-underloaded then the mismatch triple associated to $v_{\leq
i}$ will be recovered. The hypothesis of the second part ensures says that
$v_{\leq 0},\ldots,v_{\leq i-1}$ are all $\frac{1}{4ds}$-underloaded. $v_{\leq
i}$ is also because its load is just 1. Therefore $\textbf{found-
size}_{v_{\leq i}}(x)$ and $\textbf{found-size}_{v_{\leq i}}(y)$ will both be
defined, as required to conclude that $\textbf{found-start}_{v}(x)$ and
$\textbf{found-start}_{v}(y)$ to both be defined. ∎

It remains to prove Lemmas 8.6 and 8.7.

###  8.1 Proof of Lemma 8.6

For $i,j$ with $0\leq i\leq j\leq d$ define the following event:

$\textbf{F}(i,j)$:

$w(i)$ is $\frac{1}{4(d+1)}$-overloaded with respect to the HMR-recovery
problem associated with
$(\textbf{grams}^{j},T(W^{j}\times\\{1,\dots,{N}\\}),\kappa^{\leq
j},4(d+1),1/n^{4})$, which means $\widehat{\kappa}^{\leq
j}_{w(i)}\geq\frac{1}{4(d+1)}\kappa^{\leq j}_{i}$.

Note that by the first part of Proposition 8.8:

$\textbf{Pr}[\neg\textbf{STR}(w(q+1)){\;\wedge\;}\mathrm{\textbf{Normal}}\,{\;\wedge\;}(q<d){\;\wedge\;}\textbf{C}(\leq
q+1)]\\\ \leq\textbf{Pr}[(\textbf{OR-prints}_{w(q+1)}(x)=\textbf{OR-
prints}_{w(q+1)}(y)){\;\wedge\;}(q<d){\;\wedge\;}\mathrm{\textbf{Normal}}\,]\\\
+\textbf{Pr}[\bigvee_{0\leq i\leq
q}(\textbf{F}(i,q+1){\;\wedge\;}\mathrm{\textbf{Normal}}\,{\;\wedge\;}(q<d){\;\wedge\;}\textbf{C}(\leq
i){\;\wedge\;}T(\leq i))]\\\ =\textbf{Pr}[\bigvee_{0\leq i\leq
q}(\textbf{F}(i,q+1){\;\wedge\;}\mathrm{\textbf{Normal}}\,{\;\wedge\;}(q<d){\;\wedge\;}\textbf{C}(\leq
i){\;\wedge\;}T(\leq i))]\\\ \leq\textbf{Pr}[\bigvee_{0\leq i\leq
q}(\textbf{F}(i,q+1){\;\wedge\;}\mathrm{\textbf{Normal}}\,{\;\wedge\;}(q<d){\;\wedge\;}\textbf{C}(\leq
i){\;\wedge\;}T(\leq i))]\\\ \leq\textbf{Pr}[\bigvee_{0\leq i<j\leq
d}(\textbf{F}(i,j){\;\wedge\;}\mathrm{\textbf{Normal}}\,{\;\wedge\;}\textbf{C}(\leq
i){\;\wedge\;}T(\leq i))]$ (8)

The equality holds since $\textbf{ED}_{w(q+1)}\geq t_{q+1}$ by definition of
$q$ and so a normal execution implies $\textbf{OR-
prints}_{w(q+1)}(x)\neq\textbf{OR-prints}_{w(q+1)}(y)$.

Yo prove an upper bound on the right hand side of ( 8) we will prove an upper
bound on $\mathbb{E}[\widehat{\kappa}^{\leq j}_{w(i)}]$ and use Markov’s
inequality. To obtain such an upper bound, we introduce an auxiliary integer
labeling $\textbf{load-ub}^{j}$ on the nodes of $T(W^{\leq j})$ which depends
on the execution of ED-sketch on $x$ and $y$ and is an upper bound on
$\widehat{\kappa}^{\leq j}$. (Below,
${s_{{\mathrm{E}\rightarrow\mathrm{H}}}\,}$ is the parameter appearing in
Theorem 4.3.)

$\textbf{load-
ub}^{j}_{v}=\begin{cases}\min({s_{{\mathrm{E}\rightarrow\mathrm{H}}}\,}\textbf{ED}_{v},\kappa_{j})&\text{if
$|v|=j$ and $\textbf{OR-prints}_{v}(x)=\textbf{OR-prints}_{v}(y)$}\\\
2k_{j}&\text{if $|v|=j$ and $\textbf{OR-prints}_{v}(x)\neq\textbf{OR-
prints}_{v}(y)$}\\\ \sum_{w\in\textbf{child}(v)}\textbf{load-
ub}^{j}_{w}&\text{if $|v|<j$ and $v$ is compatibly split}\\\
\kappa_{|v|}&\text{if $|v|<j$ and $v$ is not compatibly split}\end{cases}$

######  Proposition 8.9.

Suppose $j\in\\{1,\ldots,d\\}$. For all nodes $v$ of $T(W^{\leq j})$,
$\widehat{\kappa}^{\leq j}_{v}\leq\textbf{load-ub}^{j}_{v}$.

###### Proof.

Fix $j\in\\{1,\ldots,d\\}$ and let $v$ be a node of $T(W^{\leq j})$. We
proceed by reverse induction on $|v|$.

The base case is $|v|=j$. $\widehat{\kappa}^{\leq j}$ is defined on the nodes
of $T(W^{j}\times\\{1,\ldots,{N}\\})$. The leaves of this tree are pairs
$(v,i)\in W^{j}\times\\{1,\ldots,{N}\\}$ and by definition,
$\widehat{\kappa}^{\leq j}_{v,i}$ is 1 if and only if
$\textbf{grams}^{j}_{v,i}(x)\neq\textbf{grams}^{j}_{v,i}(y)$. Thus for $v$
with $|v|=j$ in $T(W^{\leq j})$, by definition $\widehat{\kappa}^{\leq
j}_{v}=\min(\kappa_{j},\sum_{i=1}^{{N}}\widehat{\kappa}^{\leq
j}_{v,i})=\min(\kappa_{j},\textbf{Ham}(\textbf{grams}^{j}_{v}(x),\textbf{grams}^{j}_{v}(y)))$.

$\textbf{Ham}(\textbf{grams}^{j}_{v}(x),\textbf{grams}^{j}_{v}(y))=\textbf{Ham}(\textbf{grams}_{v}(x)\times\textbf{OR-
prints}_{v}(x),\textbf{grams}_{v}(y)\times\textbf{OR-prints}_{v}(y))$.If
$\textbf{OR-prints}_{v}(x)=\textbf{OR-prints}_{v}(y)$, by Theorem 4.3,
$\textbf{Ham}(\textbf{grams}_{v}(x),\textbf{grams}_{v}(y))\leq{s_{{\mathrm{E}\rightarrow\mathrm{H}}}\,}\textbf{ED}_{v}$,
and so $\widehat{\kappa}^{\leq
j}_{v}\leq\min({s_{{\mathrm{E}\rightarrow\mathrm{H}}}\,}\textbf{ED}_{v},\kappa_{j})$.
If $\textbf{OR-prints}_{v}(x)\neq\textbf{OR-prints}_{v}(y)$, this is at most
the total number of nonzero entries of $\textbf{grams}_{v}(x)$ and
$\textbf{grams}_{v}(y)$ which is at most $2k_{j}$.

Now suppose $v$ is a node of depth $i<j$. By definition:

$\widehat{\kappa}^{\leq
j}_{v}=\min(\kappa_{|v|},\sum_{w\in\textbf{child}(v)}\widehat{\kappa}^{\leq
j}_{w}).$

If $v$ is not compatibly split, then $\textbf{load-
ub}^{j}_{v}=\kappa_{|v|}\geq\widehat{\kappa}^{\leq j}_{v}$, as required.

If $v$ is compatibly split, then by the induction hypothesis

$\displaystyle\textbf{load-ub}^{j}_{v}$ $\displaystyle=$
$\displaystyle\sum_{w\in\textbf{child}(v)}\textbf{load-ub}^{j}_{w}$
$\displaystyle\geq$
$\displaystyle\sum_{w\in\textbf{child}(v)}\widehat{\kappa}^{\leq j}_{w}$
$\displaystyle\geq$ $\displaystyle\widehat{\kappa}^{\leq j}_{v}.$

∎

Let $i\leq d$. For the analysis we will fix the outcome of the decomposition
tree up-to level $i$, and analyze the decomposition conditioned on the fixed
part. Let $g^{\leq i}(x),g^{\leq i}(y)$ be possible outcomes for the random
variables $\textbf{substrs}^{\leq i}(x)$ and $\textbf{substrs}^{\leq i}(y)$
and let $A_{i}=A(g^{\leq i}(x),g^{\leq i}(y))$ denote the event that
$\textbf{substrs}^{\leq i}(x)=g^{\leq i}(x)$ and $\textbf{substrs}^{\leq
i}(y)=g^{\leq i}(y)$. The event $A_{i}$ determines the value for
$\textbf{ED}_{v}$ for all $v$ at depth at most $i$, and we denote this value
by $\textbf{ED}_{v}(A_{i})$. $A_{i}$ also determines whether $\textbf{C}(\leq
i)$ and $\textbf{T}(\leq i)$ hold. We now will show:

######  Proposition 8.10.

Let $i\leq j\leq d$. Let $g^{\leq i}(x)$ and $g^{\leq i}(y)$ be a possible
outcome for the first $i$ levels of $\textbf{substrs}(x)$ and
$\textbf{substrs}(y)$. Let $v$ be a node in $T(W^{\leq j})$ at depth $i$ such
that under the event $A_{i}$, $v$ is compatible and $\textbf{ED}_{v}<t_{v}$.
Then

  1. 1.

$\mathbb{E}[\textbf{load-
ub}^{j}_{v}|A_{i}]\leq{s_{\mathrm{load}}\,}\textbf{ED}_{v}(A_{i})\times(j-i+2)$.

  2. 2.

For any $R$, $\textbf{Pr}[\widehat{\kappa}^{\leq
j}_{v}\geq\frac{1}{R}\kappa_{i}|A_{i}]\leq\frac{R}{4\log^{5}n}$.

Note that the event $\widehat{\kappa}^{\leq j}_{v}\geq\frac{1}{R}\kappa^{\leq
j}_{i}$ is precisely the event that $v$ is $R$-overloaded, and this will allow
us to prove an upper bound on the right hand side of ( 8).

###### Proof.

The main thing to prove is the first part. The second part follows easily from
the first part:

$\displaystyle\textbf{Pr}[\widehat{\kappa}^{\leq
j}_{v}\geq\frac{1}{R}\kappa_{i}|A_{i}]$ $\displaystyle\leq$
$\displaystyle\frac{R\,\mathbb{E}[\widehat{\kappa}^{\leq
j}_{v}|A_{i}]}{\kappa_{i}}$ $\displaystyle\leq$
$\displaystyle\frac{R\,\mathbb{E}[\textbf{load-
ub}^{j}_{v}|A_{i}]}{\kappa_{i}}$ $\displaystyle\leq$
$\displaystyle\frac{R\,{s_{\mathrm{load}}\,}\textbf{ED}_{v}(A_{i})(2\log
n)}{\kappa_{i}}$ $\displaystyle\leq$
$\displaystyle\frac{R\,{s_{\mathrm{load}}\,}t_{i}(2\log n)}{\kappa_{i}}$
$\displaystyle\leq$ $\displaystyle\frac{R}{4\log^{5}n}.$

Here the first inequality comes from Markov’s inequality, the second comes
from Proposition 8.9, the third comes from the first part of this proposition,
the fourth comes from the hypothesis that $\textbf{ED}_{v}(A_{i})<t_{i}$ and
the final inequality follows from the definitions of $t_{i}$ and $\kappa_{i}$.

We prove the first part by reverse induction on $i$. The base case is $i=j$.
In this case, using Theorem 4.2 we have:

$\displaystyle\mathbb{E}[\textbf{load-ub}^{j}_{v}|A_{j}]$ $\displaystyle=$
$\displaystyle\hphantom{+}\;\textbf{Pr}[\textbf{OR-prints}_{v}(x)=\textbf{OR-
prints}_{v}(y)|A_{j}]\cdot{s_{{\mathrm{E}\rightarrow\mathrm{H}}}\,}\cdot\textbf{ED}_{v}(A_{j})$
(9) $\displaystyle+\;\textbf{Pr}[\textbf{OR-prints}_{v}(x)\neq\textbf{OR-
prints}_{v}(y)|A_{j}]\cdot 2k_{j}$ $\displaystyle\leq$
$\displaystyle{s_{{\mathrm{E}\rightarrow\mathrm{H}}}\,}\textbf{ED}_{v}(A_{j})+\frac{\textbf{ED}_{v}(A_{j})\cdot
s_{{\mathrm{OR}}}}{t_{j}}\cdot 2k_{j}$ $\displaystyle\leq$
$\displaystyle({s_{{\mathrm{E}\rightarrow\mathrm{H}}}\,}+{s_{\mathrm{load}}\,})\cdot\textbf{ED}_{v}(A_{j})\leq
2{s_{\mathrm{load}}\,}\cdot\textbf{ED}_{v}(A_{j}).$

Now suppose $i<j$ and condition on $A_{i}$. Suppose $v$ is a node at depth
$i$.

Let $CS$ be the set of nodes that are compatibly split

$\displaystyle\mathbb{E}[\textbf{load-ub}^{j}_{v}|A_{i}]$ $\displaystyle=$
$\displaystyle\textbf{Pr}[v\not\in CS|A_{i}]\cdot\kappa_{i}+\textbf{Pr}[v\in
CS|A_{i}]\cdot\mathbb{E}[\textbf{load-ub}^{j}_{v}|A_{i}{\;\wedge\;}v\in CS]$
$\displaystyle\leq$ $\displaystyle\textbf{Pr}[v\not\in
CS|A_{i}]\cdot\kappa_{i}+\mathbb{E}[\textbf{load-
ub}^{j}_{v}|A_{i}{\;\wedge\;}v\in CS].$

By Theorem 4.3:

$\textbf{Pr}[v\not\in
CS|A_{i}]\cdot\kappa_{i}\leq{s_{{\mathrm{split}}}\,}\frac{\textbf{ED}_{v}(A_{i})}{k_{i+1}}\kappa_{i}\leq\frac{{s_{\mathrm{load}}\,}}{2}\textbf{ED}_{v}(A_{i}).$
(10)

To bound the second summand we condition further on the $(i+1)$-st level of
$\textbf{substrs}(x)$ and $\textbf{substrs}(y)$. This extension determines
whether $v$ is compatibly split, and we let $g^{\leq i+1}(x),g^{\leq i+1}(y)$
denote a possible extension of $g^{\leq i}(x),g^{\leq i}(y)$ to level $i+1$
such that $v$ is compatibly split. Let $A_{i+1}=A(g^{\leq i+1}(x),g^{\leq
i+1}(y))$.

Let $CS_{v}(A_{i+1})$ be the set of children of $v$ that are compatibly split
and $NCS_{v}(A_{i+1})$ be the set of children of $v$ that are not compatibly
split, conditioned on $A_{i+1}$. In what follows we write $\\#A$ for the
cardinality of the set $A$ instead of $|A|$ to avoid confusion with the $|$ in
conditional expectation.

$\displaystyle\mathbb{E}[\textbf{load-ub}^{j}_{v}|A_{i+1}]$ $\displaystyle=$
$\displaystyle\sum_{w\in\textbf{child}(v)}\mathbb{E}[\textbf{load-
ub}^{j}_{w}|A_{i+1}]$ $\displaystyle\leq$
$\displaystyle\sum_{w\in\textbf{child}(v)}\textbf{Pr}[w\in
NCS_{v}|A_{i+1}]\kappa_{i+1}$
$\displaystyle+\sum_{w\in\textbf{child}(v)}\textbf{Pr}[w\in
CS_{v}|A_{i}+1]{s_{\mathrm{load}}\,}\textbf{ED}_{w}(A_{i+1})\times(j-i+1)$
$\displaystyle\leq$
$\displaystyle\kappa_{i+1}\times\mathbb{E}[\\#NCS(v)|A_{i+1}]$
$\displaystyle+{s_{\mathrm{load}}\,}\textbf{ED}_{v}(A_{i})\times(j-i+1)$

For each child $w$ of $v$, by Theorem 4.3, $\textbf{Pr}[w\in
NCS(v)|A_{i+1}]\leq{s_{{\mathrm{split}}}\,}\frac{\textbf{ED}_{w}(A_{i+1})}{k_{i+2}}$.
Therefore
$\mathbb{E}[\\#NCS(v)|A_{i+1}]\leq\sum_{w\in\textbf{child}(v)}\frac{{s_{{\mathrm{split}}}\,}\textbf{ED}_{w}(A_{i+1})}{k_{i+2}}={s_{{\mathrm{split}}}\,}\frac{\textbf{ED}_{v}(A_{i})}{k_{i+2}}$
where the final equality uses that $v$ is compatibly split. Therefore:

$\displaystyle\kappa_{i+1}\times\mathbb{E}[\\#NCS(v)|A_{i+1}]$
$\displaystyle\leq$
$\displaystyle{s_{{\mathrm{split}}}\,}\frac{\kappa_{i+1}}{k_{i+2}}\textbf{ED}_{v}(A_{i})\leq\frac{1}{2}{s_{\mathrm{load}}\,}\textbf{ED}_{v}(A_{i}).$
(11)

and so:

$\displaystyle\mathbb{E}[\textbf{load-ub}^{j}_{v}|A_{i+1}]$
$\displaystyle\leq$
$\displaystyle{s_{\mathrm{load}}\,}\textbf{ED}_{v}(A_{i})\times(j-i+\frac{3}{2})$

This upper bound is the same for all extensions $A_{i+1}$ of $A_{i}$ for which
$v$ is compatibly split, so:

$\displaystyle\mathbb{E}[\textbf{load-ub}^{j}_{v}|A_{i}{\;\wedge\;}(v\in CS)]$
$\displaystyle\leq$
$\displaystyle{s_{\mathrm{load}}\,}\textbf{ED}_{v}(A_{i})\times(j-i+\frac{3}{2})$

Combining with (10) yields the desired conclusion:

$\displaystyle\mathbb{E}[\textbf{load-ub}^{j}_{v}]$ $\displaystyle\leq$
$\displaystyle{s_{\mathrm{load}}\,}\textbf{ED}_{v}(A_{i})\times(j-i+2)$

∎

Using this Proposition we obtain:

######  Lemma 8.11.

  1. 1.

For all $i,j$ with $0\leq i\leq j\leq d$,
$\textbf{Pr}[\textbf{F}(i,j){\;\wedge\;}\textbf{C}(\leq i){\;\wedge\;}T(\leq
i)]\leq\frac{1}{\log^{4}n}$.

  2. 2.

$\textbf{Pr}[\bigvee_{0\leq i<j\leq
d}(\textbf{F}(i,j){\;\wedge\;}\mathrm{\textbf{Normal}}\,{\;\wedge\;}\textbf{C}(\leq
i){\;\wedge\;}T(\leq i))]\leq\frac{1}{\log^{2}n}$.

###### Proof.

For (1), apply Proposition 8.10(2) with $R=4(d+1)\leq 4\log n$ to get
$\textbf{Pr}[\textbf{F}(i,j){\;\wedge\;}\mathrm{\textbf{Normal}}\,|A_{i}]\leq\frac{1}{\log^{4}n}$,
and then average over all choices of $A_{i}$ for which $\textbf{C}(\leq
i){\;\wedge\;}T(\leq i)$ hold. The second part follows immediately by applying
a union bound to the first part, ∎

Part (2) of this lemma implies that the right hand side of (8) is at most
$\frac{1}{\log n}$, as required to prove Lemma 8.6.

###  8.2 Proof of Lemma 8.7

The proof of this lemma is closely related to that of Lemma 8.6 and we will
reuse parts of that proof. One difference is that in find-locations the HMR-
recovery operates on the tree $T(\\{0,1\\}^{ds})$ rather than $T(W^{d})$.
Since the depth of this tree is $ds$ the overload parameter for the HMR-
recovery scheme is set to $\frac{1}{4ds}$ instead of $\frac{1}{4(d+1)}$.
Levels of the binary tree are denoted by ordered pairs $(i,r)$ where $0\leq
i\leq d$ and $0\leq r\leq s-1$. Level $(i,r)$ refers to level $is+r$ of
$T(\\{0,1\\}^{ds})$. (If $i=d$ then $r$ can only be 0.) Level $(i,0)$ in the
binary tree corresponds to level $i$ in $T(W^{d})$. The order on levels
$(i,r)$ is lexicographic, We say that $v$ has depth $(i,r)$ if $|v|=is+r$, and
has depth at most $(i,r)$ if $|v|\leq is+r$.

The nodes in the path of $T(\\{0,1\\}^{ds})$ that corresponds to the path from
$w(0)$ to $w(d)$ in $T(W^{d})$ are denoted by $w(i,r)$ where
$(0,0)\leq(i,r)\leq(d,0)$.

For $m=is+r$ we abbreviate the HMR-recovery problem $(\textbf{left-
size}^{m},T(\\{0,1\\}^{m}),\lambda^{\leq m},4ds,1/n^{4})$ by
$\textbf{loc}(i,r)$. We write $\lambda^{\leq(i.r)}$ for $\lambda^{\leq m}$.
Recall that by definition, for a node $v$ at depth
$(i^{\prime},r^{\prime})\leq(i,r)$, its capacity for $\textbf{loc}(i,r)$ is
$\lambda^{\leq(i,r)}_{v}=\kappa_{i^{\prime}}$, and its load is denoted
$\widehat{\lambda}^{\leq(i,r)}_{v}$.

The algorithm find-locations, perform $ds$ instances of HMR-recovery
corresponding to the labelings $\textbf{left-size}^{j}$ for $0\leq j\leq
sd-1$. This is not done for the final level $sd$ because $\textbf{left-
size}^{*}_{v}$ is not undefined for leaves of the binary tree. For analysis
purposes it is convenient to augment the algorithm by defining $\textbf{left-
size}_{v}=0$ for all $v\in\textbf{vis-nodes}^{*}$ and performing HMR sketch-
and-recover for level $sd$, and including it as part of the sketch. We assume
that the (trivial) recovery of this level defines $\textbf{found-
size}^{*}_{v}(x)=\textbf{found-size}^{*}_{v}(y)=0$ for all nodes
$v\in\\{0,1\\}^{ds}$ where
$\textbf{substrs}^{*}_{v}(x)\neq\textbf{substrs}^{*}_{v}(y)$.) This additional
step plays no role in recovering the canonical alignment of $x,y$, but makes
it easier to reuse a part of the proof of Lemma 8.6. We must prove:

$\textbf{Pr}[\neg\textbf{LOC}(w(q+1,0)){\;\wedge\;}\mathrm{\textbf{Normal}}\,{\;\wedge\;}(q<d){\;\wedge\;}\textbf{C}(\leq
q+1)]\leq\frac{1}{\log n}.$

Analogous to the events $\textbf{F}(i,j)$ defined in the previous section, for
$(i,r)\leq(j,t)$, we define the bad event:

$\textbf{L}((i,r),(j,t))$

is the event that $w(i,r)$ is $\frac{1}{4ds}$-overloaded with respect to
$\textbf{loc}(j,t)$, i.e.,
$\widehat{\lambda}^{\leq(j,t)}_{w(i,r)}\geq\frac{1}{4ds}\kappa_{i}$.

We have:

$\displaystyle\textbf{Pr}[$ $\displaystyle\neg\textbf{LOC}$
$\displaystyle(w(q+1,0)){\;\wedge\;}\mathrm{\textbf{Normal}}\,{\;\wedge\;}(q<d){\;\wedge\;}\textbf{C}(\leq
q+1)]$ (12) $\displaystyle\leq$
$\displaystyle\sum\textbf{Pr}[\bigvee_{(i,r)<(j,t)<(q+1,0)}\textbf{L}((i,r),(j,t)){\;\wedge\;}\mathrm{\textbf{Normal}}\,{\;\wedge\;}(q<d){\;\wedge\;}\textbf{C}(\leq
i){\;\wedge\;}\textbf{T}(\leq i)]$ $\displaystyle\leq$
$\displaystyle\textbf{Pr}[\bigvee_{(i,r)<(j,t)\leq(d,0)}\textbf{L}((i,r),(j,t)){\;\wedge\;}\mathrm{\textbf{Normal}}\,{\;\wedge\;}\textbf{C}(\leq
i){\;\wedge\;}\textbf{T}(\leq i)]$

We will bound this last quantity by $\frac{1}{\log n}$. The first step is to
show that it suffices to bound the probability of bad events of the form
$\textbf{L}((i,0),(j,0))$:

######  Proposition 8.12.

For $(i,r)<(j,t)\leq(d,0)$, if $t\neq 0$, event $\textbf{L}((i,r),(j,t))$
implies (is contained in) event $\textbf{L}((i,0),(j+1,0))$, and if $t=0$
event $\textbf{L}((i,r),(j,t))$ implies $\textbf{L}((i,0),(j,0))$, and
therefore:

$\textbf{Pr}[\bigvee_{(i,r)<(j,t)\leq(d,0)}\textbf{L}((i,r),(j,t)){\;\wedge\;}\mathrm{\textbf{Normal}}\,{\;\wedge\;}\textbf{C}(\leq
i){\;\wedge\;}\textbf{T}(\leq i)]\\\ =\textbf{Pr}[\bigvee_{i<j\leq
d}\textbf{L}((i,0),(j,0)){\;\wedge\;}\mathrm{\textbf{Normal}}\,{\;\wedge\;}\textbf{C}(\leq
i){\;\wedge\;}\textbf{T}(\leq i)]$ (13)

###### Proof.

######  Claim 8.13.

For any $(i,r)<(j,t)$, $\textbf{L}((i,r),(j,t))$ implies
$\textbf{L}((i,0),(j,t))$.

###### Proof.

From the recurrence relation for $\widehat{\lambda}^{\leq(j,t)}$, and the fact
that $\lambda$ of a node is at most $\lambda$ of its parent it follows that
$\widehat{\lambda}^{\leq(j,t)}$ at a node is at most the
$\widehat{\lambda}^{\leq(j,t)}$ of its parent, and therefore
$\widehat{\lambda}^{\leq(j,t)}$ does not decrease along paths to the root.
Therefore
$\widehat{\lambda}^{\leq(j,t)}_{w(i,r)}\leq\widehat{\lambda}^{\leq(j,t)}_{w(i,0)}$.
Since $\lambda_{(i,0)}=\lambda_{(i,r)}=\kappa_{i}$, $\textbf{L}((i,r),(j,t))$
implies $\textbf{L}((i,0),(j,t))$. ∎

######  Claim 8.14.

If $(i,0)\leq(j,t)$ with $t\neq 0$ then $\textbf{L}((i,0),(j,t))$ implies
$\textbf{L}((i,0),(j+1,0))$.

###### Proof.

This follows from a more general claim: If $v$ is any node of the binary tree
at level $(i,r)\leq(j,t)$ and $(j,t)<(j^{\prime},t^{\prime})$ then
$\widehat{\lambda}^{\leq(j,t)}_{v}\leq\widehat{\lambda}^{\leq(j^{\prime},t^{\prime})}_{v}$.
We prove this by reverse induction on $(i,r)$. For the basis, $(i,r)=(j,t)$,
we have that $\widehat{\lambda}^{\leq(j,t)}_{v}$ is 0 or 1, and is 1 if and
only if $\textbf{substrs}^{*}_{v}(x)\neq\textbf{substrs}^{*}_{v}(y)$. So we
need that if $\textbf{substrs}^{*}_{v}(x)\neq\textbf{substrs}^{*}_{v}(y)$ then
$\widehat{\lambda}^{\leq(j^{\prime},t^{\prime})}_{v}\geq 1$. Since
$\textbf{substrs}^{*}_{v}(x)\neq\textbf{substrs}^{*}_{v}(y)$ there is a
descendant $w$ of $v$ at level $(j^{\prime},t^{\prime})$ such that
$\textbf{substrs}^{*}_{w}(x)\neq\textbf{substrs}^{*}_{w}(y)$ and so
$\widehat{\lambda}^{\leq(j^{\prime},t^{\prime})}_{w}=1$. Since
$\widehat{\lambda}^{\leq(j^{\prime},t^{\prime})}$ does not decrease along
paths to the root, $\widehat{\lambda}^{\leq(j^{\prime},t^{\prime})}_{v}\geq
1$, as required for the basis step. For the induction step, if $(i,r)<(j,t)$
then by induction we have:

$\displaystyle\widehat{\lambda}^{\leq(j,t)}_{v}$ $\displaystyle=$
$\displaystyle\min(\lambda^{\leq(j,t)}_{v},\sum_{w\text{ child of
}v}\widehat{\lambda}^{\leq(j,t)})$ $\displaystyle\leq$
$\displaystyle\min(\lambda^{\leq(j^{\prime},t^{\prime})}_{v},\sum_{w\text{
child of
}v}\widehat{\lambda}^{\leq(j^{\prime},t^{\prime})}_{v})=\widehat{\lambda}^{\leq(j^{\prime},t^{\prime})}_{v},$

∎

Combining the claims we have that for $t\neq 0$, $\textbf{L}((i,r),(j,t))$
implies $\textbf{L}((i,0),(j,t))$ implies $\textbf{L}((i,0),(j,0))$, and if
$t=0$ then the first claim gives $\textbf{L}((i,r),(j,0))$ implies
$\textbf{L}((i,0),(j,0))$. ∎

It is useful to recall the connection between the trees $T(W^{d})$ and
$T(\\{0,1\\}^{sd}$. Since $W=\\{0,1\\}^{s}$, there is a natural mapping from
$W^{d}$ to $\\{0,1\\}^{sd}$, where $v=v_{1}\ldots,v_{j}$ maps to the binary
string $v_{1}\circ\cdots\circ v_{j}$ of length $sj$. This gives a 1-1
correspondence from nodes at level $j$ in $T(W^{d})$ to nodes at level $(j,0)$
in $T(\\{0,1\\}^{sd}$. For node $v$ in $T(W^{d}$, let $v^{\prime}$ be the
associated node in $T(\\{0,1\\}^{sd}$. The HMR-recovery problem for
$(\textbf{grams}^{j},T(W^{j}\times\\{1,\dots,{N}\\}),\kappa^{\leq
j},4ds,1/n^{4})$ analyzed in the previous subsection operated on the tree
$T(W^{j}\times\\{1,\dots,{N}\\})$.

######  Proposition 8.15.

For any $j\leq d$, and for any node $v$ of $T(W^{j})$, for any execution, if
the corresponding node $v^{\prime}$ in $T(\\{0,1\\}^{sd})$ is
$\frac{1}{4ds}$-overloaded for $\textbf{loc}(j,0)$ then $v$ is
$\frac{1}{4ds}$-overloaded for the HMR-recovery problem for
$(\textbf{grams}^{j},T(W^{j}\times\\{1,\dots,{N}\\}),\kappa^{\leq
j},4ds,1/n^{4})$.

###### Proof.

First we claim that for any non-leaf node $v$ of
$T(W^{j}\times\\{1,\dots,{N}\\})$,
$\widehat{\lambda}^{\leq(j,0)}_{v^{\prime}}\leq\widehat{\kappa}^{\leq j}_{v}$.
We prove this by reverse induction on $|v|$. For the basis, $|v|=j$,
$\widehat{\lambda}^{\leq(j,0)}_{v^{\prime}}\in\\{0,1\\}$ and is 1 if and only
if $\textbf{substrs}_{v}(x)\neq\textbf{substrs}_{v}(y)$. If
$\textbf{substrs}_{v}(x)\neq\textbf{substrs}_{v}(y)$ then
$\textbf{grams}_{v}(x)\neq\textbf{grams}_{v}(y)$, which implies that for some
$a\in\\{1,\ldots,{N}\\}$ the child $(v,a)$ of $v$ satisfies
$\textbf{grams}_{v\circ a}(x)\neq\textbf{grams}_{v\circ a}(y)$ which implies
that $\widehat{\kappa}^{\leq j}_{v}\geq 1$.

For the induction step, suppose $|v|=i<j$. For a node $w$ at level less than
$(i+1,0)$ in $T(\\{0,1\\}^{ds}$, let $D(u)$ be the set of its descendants at
level $(i+1,0)$.

######  Claim 8.16.

For all $w$ that is a descendant of $v$ at level less than $(i+1,0)$
(including $v$ itself):
$\widehat{\lambda}^{\leq(j,0)}_{u}=\min(\kappa_{i},\sum_{w\in
D(u)}\widehat{\lambda}^{\leq(j,0)}_{w})$.

This claim follows easily by (reverse) induction using the recurrence
$\widehat{\lambda}^{\leq(j,0)}_{v}=\min(\lambda_{v},\sum_{w\text{ a child of
}v}\widehat{\lambda}^{\leq(j,0)}_{u})$ and the fact that
$\lambda_{(i,r)}=\kappa_{i}$ for any $r\in[0,s)$.

Observe that $D(v^{\prime})=\\{w^{\prime}:w\text{ is a child of $v$ in
}T(W^{d})\\}$. From the previous claim, we have:

$\displaystyle\widehat{\lambda}^{\leq(j,0)}_{v^{\prime}}$ $\displaystyle=$
$\displaystyle\min(\kappa_{i},\sum_{w\text{ a child of $v$ in
}T(W^{d})}\widehat{\lambda}^{\leq(j,0)}_{w^{\prime}}$ $\displaystyle\leq$
$\displaystyle\min(\kappa_{i},\sum_{w\text{ a child of
v}}\widehat{\kappa}^{\leq j}_{w})=\widehat{\kappa}^{\leq j}_{v}..$

Since $\lambda^{\leq(j,0)}_{v^{\prime}}=\kappa^{\leq j}_{v}$, it follows that
if $v^{\prime}$ is overloaded with respect to $\textbf{loc}(j,0)$ then $v$ is
$\frac{1}{4ds}$-overloaded with respect to
$(\textbf{grams}^{j},T(W^{j}\times\\{1,\dots,{N}\\}),\kappa^{\leq
j},4ds,1/n^{4})$. ∎

We can now complete the proof of Lemma 8.7 Given these propositions we have:

$\textbf{Pr}[\bigvee_{(i,r)<(j,t)\leq(d,0)}\textbf{L}((i,r),(j,t)){\;\wedge\;}\mathrm{\textbf{Normal}}\,{\;\wedge\;}\textbf{C}(\leq
i){\;\wedge\;}\textbf{T}(\leq i)]\\\ =\textbf{Pr}[\bigvee_{i<j\leq
d}\textbf{L}((i,0),(j,0)){\;\wedge\;}\mathrm{\textbf{Normal}}\,{\;\wedge\;}\textbf{C}(\leq
i){\;\wedge\;}\textbf{T}(\leq i)]\\\ \leq\sum_{i<j\leq
d}\textbf{Pr}[\textbf{L}((i,0),(j,0)){\;\wedge\;}\mathrm{\textbf{Normal}}\,{\;\wedge\;}\textbf{C}(\leq
i){\;\wedge\;}\textbf{T}(\leq i)]\\\ =\sum_{i<j\leq
d}\textbf{Pr}[\widehat{\lambda}^{\leq(j,0)}_{w(i,0)}\leq\frac{1}{4ds}\kappa_{i}{\;\wedge\;}\mathrm{\textbf{Normal}}\,{\;\wedge\;}\textbf{C}(\leq
i){\;\wedge\;}\textbf{T}(\leq i)]\\\ \leq\sum_{i<j\leq
d}\textbf{Pr}[\widehat{\kappa}^{\leq
j}_{w(i)}\leq\frac{1}{4ds}\kappa_{i}{\;\wedge\;}\mathrm{\textbf{Normal}}\,{\;\wedge\;}\textbf{C}(\leq
i){\;\wedge\;}\textbf{T}(\leq i)].$ (14)

Using the second part of Proposition 8.10, each term in the final expression
is at most $\frac{ds}{\log^{5}n}\leq\frac{1}{\log^{3}n}$, and summing over all
$i,j$ gives an upper bound of $\frac{1}{\log n}$, as required to prove Lemma
8.7.

##  9 Constraints for the choice of our parameters

In Section 6.1 we defined various parameters for the scheme. The parameters
$t_{i}$, $k_{i}$ and $\kappa_{i}$ are adjusted to satisfy various constraints
that arise in the analysis. As stated in Theorem 7.1, the length of the sketch
is $\tilde{O}(\kappa_{0})$ so we choose the parameters to satisfy the
constraints while (approximately) minimizing $\kappa_{0}$. For convenient
reference, here we collect the constraints that these parameters must satisfy.

  * •

$t_{0}=\lceil 20ks_{{\mathrm{OR}}}\rceil_{2}$. This ensures that condition
$\textbf{C}(0)$ holds as noted prior to Proposition 8.3,

  * •

$t_{d}=1$ which is used inside the proof of Proposition 8.5.

For $j\in\\{1,\ldots,d\\}$:

  1. 1.

$k_{j}\geq\kappa_{j-1}\frac{2{s_{{\mathrm{split}}}\,}}{{s_{\mathrm{load}}\,}}$.
This is used both in (10) and (11) to bound the contribution of nodes that are
not compatibly split to the expectation of $\widehat{\kappa}^{\leq j}$.

  2. 2.

$t_{j}\geq\frac{2s_{{\mathrm{OR}}}}{{s_{\mathrm{load}}\,}}k_{j}$. This is used
in (9) to bound the contribution to $\widehat{\kappa}^{\leq j}$ from leaves
for which $\textbf{OR-prints}_{v}(x)\neq\textbf{OR-prints}_{v}(y)$.

  3. 3.

$k_{j}\geq({s_{{\mathrm{split}}}\,}\log^{2}n)\cdot t_{j-1}$. This is used in
(3) to bound the probability that a node $v$ for which $\textbf{OR-
prints}_{v}(x)=\textbf{OR-prints}_{v}(y)$ is not compatibly split by
$\frac{1}{\log^{2}n}$. This constraint does not need to be explicitly enforced
because it follows from the combination of constraints 1 and 4

  4. 4.

$\kappa_{j}\geq(8{s_{\mathrm{load}}\,}\log^{6}n)\cdot t_{j}$. This allows us
to use Markov’s inequality to deduce the second part of Proposition 8.10 to
bound the probability that a node is overloaded with respect to
$\widehat{\kappa}^{\leq j}$. $\kappa_{j}\geq 4k_{j}$. When doing hmr-recover
on the sketches $\textbf{str-sk}^{j}(x),\textbf{str-sk}^{j}(y)$, every node
$v$ at level $j$ is underloaded.

  5. 5.

$\kappa_{j}\geq(8\log n)\cdot k_{j}$. This is used in the proof of Proposition
8.8. This constraint does not need to be explicitly enforced because it
follows from the combinations of constraints 3 and 4.

  6. 6.

${s_{\mathrm{load}}\,}\geq{s_{{\mathrm{E}\rightarrow\mathrm{H}}}\,}$. This is
used in the basis step of the proof of Proposition 8.10. It is implied by the
constraint obtained by multiplying together 1, 2, and 4.

## References

  * [AN20] Alexandr Andoni and Negev Shekel Nosatzki.  Edit distance in near-linear time: it’s a constant factor.  CoRR, abs/2005.07678, 2020.
  * [AS08] Noga Alon and Joel H. Spencer.  The Probabilistic Method, Third Edition.  Wiley-Interscience series in discrete mathematics and optimization. Wiley, 2008.
  * [BI18] Arturs Backurs and Piotr Indyk.  Edit distance cannot be computed in strongly subquadratic time (unless seth is false).  SIAM Journal on Computing, 47(3):1087–1097, 2018.
  * [BK23] Sudatta Bhattacharya and Michal Koucký.  Locally consistent decomposition of strings with applications to edit distance sketching.  In Barna Saha and Rocco A. Servedio, editors, Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023, pages 219–232. ACM, 2023.
  * [BR20] Joshua Brakensiek and Aviad Rubinstein.  Constant-factor approximation of near-linear edit distance in near-linear time.  In Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, pages 685–698. ACM, 2020.
  * [BZ16] Djamal Belazzougui and Qin Zhang.  Edit distance: Sketching, streaming, and document exchange.  In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 51–60, 2016.
  * [CDG+20] Diptarka Chakraborty, Debarati Das, Elazar Goldenberg, Michal Koucký, and Michael E. Saks.  Approximating edit distance within constant factor in truly sub-quadratic time.  J. ACM, 67(6):36:1–36:22, 2020.
  * [CEPR09] Raphaël Clifford, Klim Efremenko, Ely Porat, and Amir Rothschild.  From coding theory to efficient pattern matching.  In Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009, New York, NY, USA, January 4-6, 2009, pages 778–784. SIAM, 2009.
  * [CGK16] Diptarka Chakraborty, Elazar Goldenberg, and Michal Koucký.  Streaming algorithms for embedding and computing edit distance in the low distance regime.  In Daniel Wichs and Yishay Mansour, editors, Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 712–725. ACM, 2016.
  * [CKP19] Raphaël Clifford, Tomasz Kociumaka, and Ely Porat.  The streaming k-mismatch problem.  In Timothy M. Chan, editor, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 1106–1125. SIAM, 2019.
  * [Die96] Martin Dietzfelbinger.  Universal hashing and k-wise independent random variables via integer arithmetic without primes.  In Claude Puech and Rüdiger Reischuk, editors, STACS 96, 13th Annual Symposium on Theoretical Aspects of Computer Science, Grenoble, France, February 22-24, 1996, Proceedings, volume 1046 of Lecture Notes in Computer Science, pages 569–580. Springer, 1996.
  * [FKSV02] Joan Feigenbaum, Sampath Kannan, Martin Strauss, and Mahesh Viswanathan.  An approximate l1-difference algorithm for massive data streams.  SIAM J. Comput., 32(1):131–151, 2002.
  * [FNSS92] Amos Fiat, Moni Naor, Jeanette P. Schmidt, and Alan Siegel.  Nonoblivious hashing.  volume 39, pages 764–782, 1992.
  * [GKLS22] Arun Ganesh, Tomasz Kociumaka, Andrea Lincoln, and Barna Saha.  How compression and approximation affect efficiency in string distance measures.  In Joseph (Seffi) Naor and Niv Buchbinder, editors, Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, VA, USA, January 9 - 12, 2022, pages 2867–2919. SIAM, 2022.
  * [Gra16] Szymon Grabowski.  New tabulation and sparse dynamic programming based techniques for sequence similarity problems.  Discret. Appl. Math., 212:96–103, 2016.
  * [JNW21] Ce Jin, Jelani Nelson, and Kewen Wu.  An improved sketching algorithm for edit distance.  In 38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021,, volume 187 of LIPIcs, pages 45:1–45:16, 2021.
  * [KPS21] Tomasz Kociumaka, Ely Porat, and Tatiana Starikovskaya.  Small-space and streaming pattern matching with $k$ edits.  In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 885–896, 2021.
  * [KR87] Richard M. Karp and Michael O. Rabin.  Efficient randomized pattern-matching algorithms.  IBM J. Res. Dev., 31(2):249–260, mar 1987.
  * [KS20] Michal Koucký and Michael E. Saks.  Constant factor approximations to edit distance on far input pairs in nearly linear time.  In Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, pages 699–712. ACM, 2020.
  * [LMS98] Gad M. Landau, Eugene W. Myers, and Jeanette P. Schmidt.  Incremental string comparison.  SIAM J. Comput., 27(2):557–582, 1998.
  * [MP80] William J. Masek and Mike Paterson.  A faster algorithm computing string edit distances.  J. Comput. Syst. Sci., 20(1):18–31, 1980.
  * [OR07] Rafail Ostrovsky and Yuval Rabani.  Low distortion embeddings for edit distance.  J. ACM, 54(5):23, 2007.
  * [PL07] Ely Porat and Ohad Lipsky.  Improved sketching of hamming distance with error correcting.  In Bin Ma and Kaizhong Zhang, editors, Combinatorial Pattern Matching, 18th Annual Symposium, CPM 2007, London, Canada, July 9-11, 2007, Proceedings, volume 4580 of Lecture Notes in Computer Science, pages 173–182. Springer, 2007.
  * [WF74] Robert A. Wagner and Michael J. Fischer.  The string-to-string correction problem.  J. ACM, 21(1):168–173, 1974.