tcb@breakable

# Reconstructing Ultrametric Trees from Noisy Experiments

Eshwar Ram Arunachaleswaran  Anindya De  Sampath Kannan

###### Abstract

The problem of reconstructing evolutionary trees or phylogenies is of great
interest in computational biology. A popular model for this problem assumes
that we are given the set of leaves (current species) of an unknown binary
tree and the results of ‘experiments’ on triples of leaves $(a,b,c)$, which
return the pair with the deepest least common ancestor. If the tree is assumed
to be an ultrametric (i.e., with all root-leaf paths of the same length), the
experiment can be equivalently seen to return the closest pair of leaves. In
this model, efficient algorithms are known for reconstructing the tree.

In reality, since the data on which these ‘experiments’ are run is itself
generated by the stochastic process of evolution, these experiments are noisy.
In all reasonable models of evolution, if the branches leading to the three
leaves in a triple separate from each other at common ancestors that are very
close to each other in the tree, the result of the experiment should be close
to uniformly random. Motivated by this, in the current paper, we consider a
model where the noise on any triple is just dependent on the three pairwise
distances (referred to as _distance-based noise_). Our results are the
following:

  1. 1.

Suppose the length of every edge in the unknown tree is at least
$\tilde{O}(\frac{1}{\sqrt{n}})$ fraction of the length of a root-leaf path.
Then, we give an efficient algorithm to reconstruct the topology of the
unknown tree for a broad family of distance-based noise models. Further, we
show that if the edges are asymptotically shorter, then topology
reconstruction is information-theoretically impossible.

  2. 2.

Further, for a specific distance-based noise model – which we refer to as the
homogeneous noise model – we show that the edge weights can also be
approximately reconstructed under the same quantitative lower bound on the
edge lengths. Note that in the noiseless case, such reconstruction of edge
weights is impossible.

##  1 Introduction

The problem of clustering is an important computational problem and a
primitive that is used in multiple domains with the goal of grouping elements
based on some underlying notion of distance in order to understand the
relationship among them. In the standard clustering problem, the set of given
elements is to be partitioned into a few sets with the goal of putting similar
elements in the same partition (captured by minimizing an objective function).
A natural and well studied variant (and generalization) of this problem is
hierarchical clustering, where the goal is to find a hierarchical partition of
the elements, in which groups of elements form a nested structure.
Equivalently, a hierarchical clustering can be thought of as a rooted tree
with the elements at the leaves. Thus, the task of hierarchical clustering can
be seen as the task of recovering the underlying unknown rooted tree.

Naturally, canonical applications of the problem of hierarchical clustering
are settings where there is an underlying tree structure – examples include
learning evolutionary trees of a set of species and evolutionary trees of
languages. In particular, the problem of reconstructing evolutionary trees or
phylogenies from data about extant species is an important one in
computational biology [39, 40, 18, 30, 22, 3, 5, 12, 14, 24, 16] and is the
principal motivation for this paper.

In order to define a hierarchical clustering problem, we need the precise
notion of similarity, as well as the mode by which the algorithm gets access
to this information. The formulation that is closest to the one in this paper
is from [24]. Here, the evolutionary tree is assumed to be an ultrametric
binary tree, which is a weighted, rooted tree in which all root-leaf paths
have the same length. This assumption is often justified in the computational
biology literature based on the so-called molecular clock hypothesis, whereby
the lengths of edges correspond to the evolutionary time that they represent.
Then since all extant species are alive today and they are the leaves of this
tree, they have all evolved for the same length of time. Consequently, all
root to leaf paths have the same length. The model in [24] assumes that we are
able to perform experiments on any 3 extant species (leaves) $a,b,$ and $c$
and the result of the experiment (alternately, referred to as query) is the
pair that is closest together, i.e., has the most recent least common
ancestor. In this model, the authors [24] give efficient algorithms for
reconstruction of the tree topology – in fact, they give several procedures,
each obtaining a different tradeoff between the running time and the number of
experiments (i.e., queries).

A principal shortcoming of [24] is the assumption that the experiments do not
have any noise – on any triple $(a,b,c)$, the queries always returns the
closest pair. However, experiments are often noisy and thus it is natural to
ask if we can design a tree-reconstruction algorithm which is tolerant to
noise in the experiments. Several works [9, 1, 16] have explored this theme.
In particular, in [16], the authors gave an algorithm to reconstruct the
(topology of the) ultrametric tree with $O(n\log n)$ queries even in presence
of noise. However, in all the previous works [9, 1, 16], the noise is
identical across queries – in other words, each experiment is assumed to give
an incorrect answer with some fixed probability $p<1/2$.

In this paper, we study the tree reconstruction problem under a broad family
of noise models where the noise on any triple $(a,b,c)$ is just dependent on
the three pairwise distances between the leaves $a$, $b$ and $c$ – note that
by the ultrametric assumption, the two largest distances are the same. We
refer to such noise models as distance-based noise models. Our motivation is
that if the data at the leaves is generated by a process like evolution then
the data at each leaf is the result of a set of stochastic mutations
encountered on the path from the root to that leaf. If we have three leaves
$a,b,$ and $c$ where the least common ancestor of $a$ and $b$ is at distance 1
from the leaves, while the least common ancestor of $c$ with either $a$ or $b$
is at distance $1+\epsilon$, then the expected number of mutational
differences between $a$ or $b$ on the one hand and $c$ on the other hand, is
quite close to the expected number of mutational differences between $a$ and
$b$. Any experiment trying to assess which pair is closest based on mutational
differences would therefore have a good probability of identifying the wrong
pair in this situation. Finally, similar to [9] (as well as many other results
in the phylogenetic reconstruction literature), we assume that the noise in
each experiment is permanent – i.e., repeating the same experiment always
yields the same outcome. Since repetitions of an experiment will use the same
noisy data, this assumption is justified. This naturally rules out repeating
the same experiment as a way to denoise the answers, thus making the algorithm
design more challenging.

Our results: We now give an overview of our results. First of all, by
rescaling the edge lengths (alternatively referred to as weights), we can
assume that all root to leaf paths are of unit length. For our first
algorithmic result, we define a so-called general noise model. This is any
distance-based noise model that satisfies two mild assumptions we refer to as
the monotonicity and anti-Lipschitzness conditions. Roughly speaking, these
conditions say that (i) the probability of getting the correct pair is always
greater than $1/3$ and (ii) Fixing the larger distance among pairs in the
triple, the probability of the experiment returning the closest pair is
sufficiently sensitive to the distance between the closest pair. The exact
conditions are described in Section 3.

Our first algorithmic result shows that in the general noise model, as long as
each edge length is at least $\tilde{\Omega}(n^{-1/2})$ (where $n$ is the
number of leaves), there is an algorithm that takes the results of the
$\binom{n}{3}$ experiments and reconstructs the topology of tree with high
probability (Theorem 1). We also show a matching lower bound – namely, if the
minimum edge length is $\tilde{o}(n^{-1/2})$, then it is information-
theoretically impossible to recover the topology of the tree (Theorem 3).
Thus, together Theorem 1 and Theorem 3 give the minimal requirements under
which topology of the tree can be recovered in the general noise model.

For our second algorithmic result, we explore a special instance of the
general noise model which we refer to as the homogeneous noise model. Let us
denote this model by $\mathbf{Q}_{h}(\cdot)$ – then, on the triple $(a,b,c)$,
the probability of returning the pair $(a,b)$ is given by

$\Pr[\mathbf{Q}_{h}(a,b,c)=(a,b)]=\frac{d(a,c)+d(b,c)}{2(d(a,b)+d(b,c)+d(a,c))},$

where $d(\cdot,\cdot)$ denotes the distance function on the tree. Under
natural ‘boundary conditions’ that the probability of any pair being returned
should approach 1/3 as the 3 pairwise distances approach each other, and that
the probability of the closest pair being returned should approach some higher
constant value when the other two distances tend to infinity,
$\mathbf{Q}_{h}(\cdot)$ is essentially the only probability function that is a
ratio of linear functions. One particularly appealing feature is that the
model is invariant upon rescaling of the distance function $d(\cdot,\cdot)$.
For the homogeneous noise model, we can achieve a significantly stronger
result than Theorem 1. In particular, in Theorem 2, we show that as long as
all the edge weights are at least $\tilde{\Omega}(n^{-1/2})$, there is an
efficient algorithm to approximately reconstruct the edge weights. In other
words, for the homogeneous noise model, we can not just recover the topology
of the tree but the actual distances between leaves. Such a reconstruction of
the edge weights is information-theoretically impossible in models such as
[24, 9, 1, 16] where either the queries have no noise or the noise only
depends on the order between the distances and not their precise values. We
remark that our techniques for reconstructing distances are quite general, and
should be applicable to other instantiations of the general noise model.
Determining the general conditions under which the entire ultrametric can be
reconstructed is left as a topic for future work.

##  2 Related Work

The problem of reconstructing evolutionary trees has received a lot of
attention over the years. There are many formulations of this problem based on
the type of data available and the objective function being optimized. Most
formulations assume that the observed data is on extant species or leaves of
an unknown tree. Objective functions seek to capture properties of the
evolutionary process, with the hope that the optimal tree under an objective
function is in fact the true evolutionary tree. The most popular formulations
are distance-based methods [19, 14, 15, 39, 32, 13] (where we are given a
matrix of distances between leaves and we want to find the best-fitting edge-
weighted tree), character-based methods [4, 25, 31, 33, 41], where we want to
explain the evolution of different characters, each taking on a state in each
extant species using the fewest number of state changes, and likelihood
methods [34, 17, 18, 37], where we assume that evolution is a stochastic
process drawn from a family of processes, and want to estimate the most likely
parameters. In all cases the data observed at the leaves is the result of the
stochastic process of evolution. These formulations and other related types
lend themselves naturally to the model considered in this paper.

As noted earlier, the closest formulation to that in our paper is the one
introduced by [24] on learning an ultrametric tree through experiments
involving three leaves. This paper motivated several follow-ups [16, 9, 1]
with closely related models. In particular, in [16], the authors considered a
noisy version of these experiments, with each experiment independently failing
with some probability $p<1/2$. In the current paper, we consider the same
problem but with a different, incomparable noise model. Similar to [16], the
noise in each experiment is independent. However, unlike [16], the probability
of getting an incorrect answer is not the same for every triple. In
particular, for three leaves $a$, $b$ and $c$, where the pairwise distances
are close to each other (in the ultrametric tree), the probability of getting
the correct answer can be as small as $1/3+\theta(\frac{\log n}{\sqrt{n}})$.
An additional feature of our model is that each experiment can only be
performed once (similar to [9]). In contrast, [16] allows for repetition of
the same experiment multiple times with fresh randomness each time. Finally,
we remark that while [16] allows for repetition of the same experiment, they
view the number of experiments (equivalently the query complexity) as a key
measure of performance of their algorithm – in fact, their topology
reconstruction algorithm has query complexity $O(n\log n)$ (which is
essentially optimal). In contrast, the focus of this paper is to identify a
broad class of noise models under which tree reconstruction is possible.

Besides evolutionary biology, “distance based noise models” have also been
studied in other reconstruction problem. In [42], Tamuz _et al._ study the
following problem: there are $n$ elements with an unknown embedding in the
Euclidean space. The algorithm gets noisy answers to relative similarity
queries and the goal is to reconstruct this embedding. More precisely, the
algorithm can query any triple $(a,b,c)$ with the underlying semantics being
“Is $a$ closer to $b$ or to $c$?”. On such a query, it gets the pair $(a,b)$
with probability $\frac{d(a,c)}{d(a,b)+d(a,c)}$ (and otherwise the pair
$(a,c)$ is returned). Here $d(\cdot)$ is the underlying distance metric. We
note that the model is both in form and spirit, very similar to the
homogeneous noise modelstudied in Theorem 2. Indeed, as the distances $d(a,b)$
and $d(a,c)$ approach each other, the response to the query $(a,b,c)$ is
basically a coin flip. On the other hand, if one of the distances is much
smaller than the other, then the probability of returning the closer pair
approaches $1$. Along similar lines, Van der Maaten et al. [43] study the
problem of learning a low dimensional embedding of a set of elements in
Euclidean space based upon seeing the closest pair in a triplet. Just as in
our model, each possible closest pair appears with a probability that depends
upon an underlying dissimilarity/ distance function relating these elements.

Distance-based models are also quite popular in the ranking literature. In
particular, in the well-known Bradley-Terry-Luce (BTL) model [8, 26], there
are $n$ elements where the $i^{th}$ element is assigned (an unknown) weight
$w_{i}\in[0,1]$ – thus defining a total order on these elements. The algorithm
queries pairs $(i,j)$ and is returned $i$ with probability
$w_{i}/(w_{i}+w_{j})$. Note that this can be interpreted as a noisy comparison
query where the probability of returning the larger element depends on the
relative scores of the two elements. The goal in the BTL model is to recover
the underlying ranking given these noisy comparison queries. Again, the BTL
model bears strong syntactic resemblance to our homogeneous noise model(from
Theorem 2). In fact, similar to the current paper, in the BTL model, each
query can be made at most once. We also note that higher arity generalizations
of the BTL model have also been explored in literature [35, 27] (under the
name multinomial logistic model).

Outside of distance based noise models, there is large body of literature in
computer science which aims to model relations between elements by an
(unknown) embedding in some metric space. The algorithm makes relational
queries and gets noisy responses where the noise is governed by the hidden
embedding. Several models including the famous stochastic block model [28, 29,
11, 2] and its variants [10] fit this motif and the current paper can be seen
as yet another instantiation of this general framework. Further examples from
the world of machine learning include [21], [23], [6], [20], [38].

##  3 Model, Notation, and Preliminaries

There is an underlying weighted tree $T$ with the weights constrained such
that the distance function between leaves is an ultrametric. The set of leaves
of the tree is represented by $L(T)$. We assume that the height of the tree
$h(T)$ is normalized to $1$.

Distance-Based Noise Model: For each triple of leaves $(a,b,c)$, we perform an
experiment and get back one of the pairs $(a,b)$, $(b,c)$, or $(c,a)$
probabilistically. Such an experiment will be denoted by $Q(a,b,c)$. Repeating
an experiment produces the same answer, and results of distinct experiments
are independent of each other. Recall that in an ultrametric, the largest two
of the three pairwise distances are equal. Thus we will model the
probabilities of different answers as a function of just two distances —
$d_{1}$, the distance between the closest pair of leaves and $d_{2}$ the
distance between either of the two other pairs in the triple. (So $d_{1}\leq
d_{2}$. ) In our model, the two incorrect pairs have equal probabilities of
being returned, which is justified because their pairwise distances are the
same. Thus, we define two probability functions: $p_{\textsc{correct}}$ and
$p_{\textsc{incorrect}}$ where $p_{\textsc{correct}}$ denotes the probability
that the closest pair is returned and $p_{\textsc{incorrect}}$ denotes the
probability that one of the other pairs is returned. Thus $\forall
d_{1},d_{2},\
p_{\textsc{correct}}(d_{1},d_{2})+2p_{\textsc{incorrect}}(d_{1},d_{2})=1$.

We impose some mild conditions on the probability functions. First, we
naturally insist that $p_{\textsc{correct}}>p_{\textsc{incorrect}}$, since
otherwise the output of the experiment is not useful. Second, we require that
the probability of returning the correct pair is sufficiently sensitive to the
change in distance. In mathematical terms, for any $d_{2}$ and
$0<d_{1}<d_{2}$, $\frac{\partial p_{\textsc{correct}}(d_{1},d_{2})}{\partial
d_{1}}\leq-\varepsilon$ for some constant $\varepsilon>0$. We are implicitly
also assuming that the probability functions are continuous in each coordinate
since we are assuming that their partial derivatives are defined.

We will refer to this model as the distance-based noise model or the general
noise model.

When it comes to reconstructing weights (Section 5), we show that it is
possible for a specific instantiation of the distance based model, called the
homogeneous model, denoted by $\mathbf{Q}_{h}(a,b,c)$. Recall the definition
of this model from the introduction - on the triple $(a,b,c)$, the probability
of returning the pair $(a,b)$ is given by

$\Pr[\mathbf{Q}_{h}(a,b,c)=(a,b)]=\frac{d(a,c)+d(b,c)}{2(d(a,b)+d(b,c)+d(a,c))},$

where $d(\cdot,\cdot)$ denotes the distance function on the tree.

If $d(a,b)$ is the smallest of the 3 pairwise distances, then the probability
of the experiment returning $(a,b)$ is between 1/3 and 1/2. Since the other
two distances, $d(a,c)$ and $d(b,c)$ are equal in an ultrametric, the
experiment has equal probability of returning $(a,c)$ or $(b,c)$. Thus for
pairs $a,b$ that are very close and $c$ that is much farther, the probability
of getting the result $(a,b)$ approaches .5, while for triples $(a,b,c)$ whose
least common ancestors are very close, the probability of getting any pair
approaches $1/3$. In the introduction we provided intuition on why this is a
natural model.

Even in this simple model, we cannot hope to reconstruct arbitrary
ultrametrics as the following example shows. Suppose the underlying tree is a
balanced binary tree, where the edge at depth $i$ has weight $C\cdot
2^{2^{i}}$. Let the height of the tree be $\log n$ and the constant $C$ is
chosen so that any root to leaf path has weight
$C\cdot\sum_{i=0}^{h-1}2^{2^{i}}=1$. Now, consider any three leaves $a$, $b$
and $c$ such that the least common ancestor for any of the pairs is at height
$h/2$. Further, for any three leaves $x,y,z$, let us call
$\mathbf{Q}_{h}(x,y,z)$ to be $\delta$-random if any of the pairs is returned
with probability $1/3\pm\delta$. Then, the following can be easily verified.
(i) The experiment $\mathbf{Q}_{h}(a,b,c)$ is $\exp(-\Theta(n))$-random. (ii)
If $x\not=a,b,c$ is any other leaf, then the experiments,
$\mathbf{Q}_{h}(a,b,x)$, $\mathbf{Q}_{h}(b,c,x)$ and $\mathbf{Q}_{h}(a,c,x)$
are $\exp(-\Theta(n))$-random. (iii) If $x,y\not=a,b,c$ are two other leaves,
then the experiments, $\mathbf{Q}_{h}(a,x,y)$, $\mathbf{Q}_{h}(b,x,y)$ and
$\mathbf{Q}_{h}(c,x,y)$ are $\exp(-\Theta(n))$-random. From the above, it
easily follows that using just $\binom{n}{3}$ experiments, the relative
topology of the leaves $a$, $b$ and $c$ cannot be resolved.

Thus, we will need to impose some conditions on the ultrametric to make the
problem tractable. Specifically, we show that a lower bound on the length of
each edge is necessary and sufficient (up to log factors) for reconstructing
the topology in the general model, and reconstructing the weights in the
homogeneous model.

Without loss of generality, we will assume that the tree is a full binary
tree, since an internal node with 1 child does not affect the response to any
query and can be eliminated.

Through this paper, when we refer to events having overwhelmingly high
probability, we mean a probability of at least $1-\frac{1}{n^{6}}$. Since we
will consider at most $o(n^{5})$ such events, using the union bound, we can
assume that all of them happen with very high probability (at least
$1-\frac{1}{n}$), and condition our analysis upon this event.

We fix some standard notation for full binary trees that will be used in our
algorithms.

Subtrees:  By a subtree of some tree $T$, we will mean the entire tree rooted
at some internal node of $T$. (Thus we use the term “subtree” in a more
restrictive manner than usual.) For any tree $T$, $L(T)$ denotes the set of
leaves of $T$. We will also refer to the set of all leaves in the tree by $L$.

Subtree-Induced Partition: If $T_{B}$ is a subtree of $T$, it naturally
partitions $L(T)-L(T_{B})$ into buckets $S_{1},S_{2},\cdots S_{k}$ , where $x$
and $y$ are in the same bucket if and only if for any $z\in L(T_{B})$, the
least common ancestors of $x$ and $z$, and of $y$ and $z$ are the same. An
alternative characterization of these buckets is that $x$ and $y$ are in the
same bucket if and only if for any $z$ in $T_{B}$, the closest pair out of the
triple $(x,y,z)$ is $(x,y)$. Each bucket can be thought of as a subtree
hanging off from the path from the root of $T_{B}$ to the root of $T$. Thus
there is a natural order on the buckets that is defined by this path, with
$S_{1}$ being the bucket closest to $T_{B}$ and $S_{k}$ the farthest. A visual
depiction is shown in Figure 1.For any $j\in[k]$, the set of leaves in
$T_{B},S_{1},S_{2}\cdots S_{j}$ form the leaves of a subtree.

Figure 1: Partition of buckets with respect to Subtree $T_{B}$

Induced Topology: For any subset of leaves $S$, the induced topology on $S$ is
defined by removing all leaves outside of $S$ and removing internal nodes that
now have only one child. (Since we are talking about weighted trees, when we
have an internal node $v$ with one child, we replace the two edges incident on
$v$ by a single edge whose weight is the sum of the weights of the two edges.)
It is not hard to see that the weighted tree obtained by this process will
define an ultrametric on $S$. As a special case, when $T_{B}$ is a subtree of
$T$, we will denote the induced topology on the leaves not in $T_{B}$ by
$T-T_{B}$. We will also define a slightly different induced topology where we
replace $T_{B}$ by a single leaf (of $T_{B}$). We think of this operation as
taking the quotient of $T$ with respect to $T_{B}$, and denote the resulting
topology by $T\,/\,T_{B}$.

By the topology of a triple of leaves $(x,y,z)$ we mean the induced subtree of
$T$ with just these leaves. This topology is completely specified by
specifying the pair among $x,y,$ and $z$ that has the least common ancestor of
smallest height.

Finally, we use some standard concentration inequalities and results about
measures of statistical distance in our paper. These can be found in Appendix
D (Supplementary Material).

##  4 Reconstructing Full Binary Trees

This section is devoted to the proof of the following result.

######  Theorem 1.

Let $T$ be a weighted full binary tree tree where all root-leaf paths are of
length 1. Suppose that the weight on each edge is at least
$\tau\sqrt{\frac{\log n}{n}}$, for some large constant $\tau$. Then, given
access to the general model on the leaves of this tree, there exists an
efficient algorithm Topology-Reconstruction that, with high probability,
exactly reconstructs the topology of this tree.

We start by providing a high-level description of the algorithm Topology-
Reconstruction. We want to infer an unknown tree $T$ on a given set of leaves
$L$. We are given the results of experiments on all triples $(a,b,c)\in L$.
This result is one of the three possible pairs with probabilities specified by
the distance-based noise model (defined in Section 3). We use the phrase
‘resolving the topology’ of a subtree $T^{\prime}$ to mean that we know the
rooted tree representation of $T^{\prime}$.

Before describing the algorithm, we make an important observation regarding
the probability of getting the correct answer.

######  Observation 1.

The assumption that all edge weights are at least $\tau\sqrt{(\log n/n)}$
implies that $d_{1}+2\tau\sqrt{(\log n/n)}\leq d_{2}$ for the distances
$d_{1},d_{2}$ involved in every experiment $Q(a,b,c)$. Thus, using the
properties of the model, we observe that $p_{\textsc{correct}}\geq
p_{\textsc{incorrect}}+2\tau\sqrt{(\log n/n)}$.

Our algorithm works by resolving the topologies of small subtrees, and then
stitching these together until all of $T$ is resolved.

  1. 1.

In a bottom-up manner by combining sibling subtrees, we build a “base” tree
$T_{B}$ containing between $\sqrt{n}$ and $2\sqrt{n}$ leaves that is a subtree
of $T$ with high probability. (This is as large a tree as we can build to be
confident that we have a subtree of $T$.)

  2. 2.

We use the same idea to build a ”pivot” tree $T_{P}$ on about the same number
of leaves outside of $L(T_{B})$. With high probability, $T_{P}$ will also be a
subtree of the induced tree on $L-L(T_{B})$.

  3. 3.

Using the fact that $|L(T_{B})|*|L(T_{P})|=\Omega(n)$, we partition the leaves
in $L(T)-L(T_{B})$ into 3 parts (some possibly empty) — leaves in buckets to
the left of $T_{P}$ (i.e., buckets with smaller indices than the buckets that
the leaves of $T_{P}$ come from), leaves in the same bucket as $T_{P}$, and
leaves in buckets to the right of $T_{P}$ (i.e., buckets with smaller indices
than the buckets that the leaves of $T_{P}$ come from).

  4. 4.

We show that if a subtree excludes $\Omega(n)$ leaves then we can infer its
entire topology with high probability. Likewise, if it contains $\Omega(n)$
leaves, we can infer the topology of the complement of the subtree with high
probability. Using these two facts, we fully resolve the topology of all but
one of the 3 parts in the previous step and recurse on the unresolved part.
When this part has fewer than $\frac{11n}{12}$ leaves, we can infer its
topology directly from the leaves outside, and the recursion bottoms out.

Before describing the proofs of the different parts used in our algorithm, we
state a simple lemma about sums of independent random variables that recurs in
multiple proofs. The proof of this lemma is in Appendix A.

######  Lemma 1.

Let $L\geq\frac{n}{16}$, let $X_{1},X_{2},\cdots X_{L}$ and
$Y_{1},Y_{2},\cdots Y_{L}$ be two sets of independent $0-1$ random variables
such that for all $i\in[L]$,
$\mathbb{E}[X_{i}]\leq\mathbb{E}[Y_{i}]-c\sqrt{(\log n/n)}$, for a
sufficiently large constant $c$. Let $X=\sum_{i=1}^{l}X_{i}$ and let
$Y=\sum_{i=1}^{l}Y_{i}$ Then, with high probability, i.e. at least
$1-1/n^{6}$, we have $Y>X+24\sqrt{n\log n}$.

Alternatively, if $X_{i}$ and $Y_{i}$ are identical random variables for each
$i$, with high probability, we have $|X-Y|<12\sqrt{n\log n}$.

We will now elaborate on the algorithm. To begin, we state a lemma that
establish the claims made in Step 4 above.

######  Lemma 2.

Let $T$ be a tree with $n$ leaves and $T^{\prime}$ a subtree.

  1. 1.

If $T^{\prime}$ contains at least $\frac{n}{12}$ leaves, given the set
$L(T^{\prime})$, there exists an algorithm Completion that, with high
probability, resolves the topology of the quotient $T\,/\,T^{\prime}$. (Recall
that this quotient is arrived at by collapsing $T^{\prime}$ to a single leaf
and taking the induced topology on the resulting set of leaves.)

  2. 2.

If $T^{\prime}$ has at most $\frac{11n}{12}$ leaves, given the set
$L(T^{\prime})$, the algorithm Completion resolves the induced topology on
this set with high probability.

The proof of this lemma can be found in Appendix A.

We now fill in the details of Step 1 in our algorithm outline above,
describing and analyzing an algorithm that constructs an approximately
$\sqrt{n}$ sized subtree within the induced tree of a large enough set of
leaves.

######  Lemma 3.

Given a subset $S\subseteq L$ of leaves with $|S|\geq\frac{n}{12}$, denoting
the (unknown) induced topology on $S$ by $T_{S}$, there exists an algorithm
Build-Subtree that, whp, finds a subtree $T^{\prime}$ of $T_{S}$ such that
$|L(T^{\prime})|\in[\sqrt{n},2\sqrt{n}]$.

###### Proof.

The algorithm Build-Subtree builds subtrees of $T_{S}$ from the ground up,
starting with each leaf in $S$ as a singleton subtree. Let $T_{1},T_{2},\cdots
T_{l}$ represent subtrees of $T_{S}$ whose leaves form a disjoint partition of
$S$ \- in each step the algorithm, with high probability, combines two of
these subtrees to form a larger subtree of $T_{S}$. Let $L_{i}$ represent the
set of leaves of $T_{i}$. Using this procedure and starting with the initial
configuration, the algorithm repeatedly keep applies this step until the size
of the largest subtree exceeds $\sqrt{n}-1$. Since each step can at most
double the size of the largest subtree, we obtain a subtree of $T_{S}$ of size
in the range $[\sqrt{n},2\sqrt{n}]$.

Now, we describe the key step (combining subtrees) of the algorithm Build-
Subtree. For each pair $T_{i},T_{j}$, a score $s_{ij}$ is generated in the
following manner. Fix arbitrary $a\in L_{i}$, and $b\in L_{j}$ and define a
$0-1$ random variable $X^{x}_{ij}$ for each leaf $x\in S\setminus(L_{i}\cup
L_{j})$ to be $1$ if the experiment $Q(a,b,x)$ gives $(a,b)$ as the answer,
and 0 otherwise.

$s_{ij}:=\sum_{x\in S\setminus(L_{i}\cup L_{j})}X^{x}_{ij}$

We claim that (whp) the tree pair with the highest score is in fact a “sibling
- tree pair”, i.e., a pair of subtrees of $T_{S}$ that can be combined through
a shared parent internal node to form a subtree of $T_{S}$. There always
exists such a sibling-tree pair, since these leaf-disjoint subtrees of $T_{S}$
themselves form a full binary tree.

We start with a simple observation: For any pair $T_{k},T_{l}$ that is not a
sibling pair, there is a sibling pair $T_{i},T_{j}$ such that their least
common ancestor is strictly below the root of either $T_{k}$ or $T_{l}$.

To see this we consider the full binary tree resulting from starting with $T$
and collapsing each set of leaves $L_{i}$ into a single node and look at the
subtree rooted at the least common ancestor of $T_{k}$ and $T_{l}$. There must
be a deepest internal node in this tree whose children are sibling subtrees
$T_{i}$ and $T_{j}$, completing the proof. Figure 2, in Appendix E shows such
a set of trees.

######  Claim 1.

With high probability, $s_{kl}<s_{ij}$.

###### Proof.

Intuitively, this claim is true because the number of leaves that are used to
generate the scores of both pairs $T_{i},T_{j}$ and $T_{k},T_{l}$ is
sufficiently large (at least $\frac{n}{16}$), and that these leaves all favor
the pair $T_{i},T_{j}$ (by at least $\theta(\sqrt{(\log n/n)})$ each).
Further, the number of leaves that are used to generate only one of the scores
is bounded by $2\sqrt{n}$. Consequently, these leaves do not alter the signal
created by comparing the action of the leaves used to generate both scores.

We introduce some notation to formalize the above intuition. Let
$S_{1}:=S\setminus(L_{k}\cup L_{l})$ and $S_{2}:=S\setminus(L_{i}\cup L_{j})$.
$S_{1}$ is the set of leaves used to compute the score $s_{kl}$ and $S_{2}$ is
the set of leaves used to compute the score $s_{ij}$. We can write
$S_{1}=A\cup B_{1}$ and $S_{2}=A\cup B_{2}$ where $A:=S_{1}\cap S_{2}$,
$B_{1}:=L_{i}\cup L_{j}$ and $B_{2}:=L_{k}\cup L_{l}$. Since
$|L_{k}|,|L_{l}|,|L_{i}|,|L_{j}|\leq\sqrt{n}$, we can assume that
$|A|\geq\frac{n}{16}$ and $|B_{1}|,|B_{2}|\leq 2\sqrt{n}$.

Using the condition on minimum edge length and the bound on the partial
derivative of the function $p_{\textsc{correct}}(d_{1},d_{2})$, it is easy to
see (Ref Fig 2) that :

$\forall x\in
A:\mathbb{E}[X^{x}_{ij}]-\mathbb{E}[X^{x}_{kl}]\geq\frac{\tau\sqrt{\log
n}}{9\sqrt{n}}$

Expanding $S_{1}$ and $S_{2}$, we get:

$s_{kl}=\sum_{x\in A}X^{x}_{kl}+\sum_{y\in B_{1}}X^{y}_{kl}$

$s_{ij}=\sum_{x\in A}X^{x}_{ij}+\sum_{x\in B_{2}}X^{x}_{ij}$

Taking the difference and using linearity of expectation, we get:

$\displaystyle\mathbb{E}[s_{ij}]-\mathbb{E}[s_{kl}]$ $\displaystyle=\sum_{x\in
A}(\mathbb{E}[X^{x}_{ij}]-\mathbb{E}[X^{x}_{kl}])+\sum_{y\in
B_{2}}E[X^{y}_{ij}]-\sum_{y\in B_{1}}E[X^{y}_{kl}]$
$\displaystyle\geq\sum_{x\in
A}(\mathbb{E}[X^{x}_{ij}]-\mathbb{E}[X^{x}_{kl}])-\sum_{y\in
B_{1}}E[X^{y}_{kl}]$ $\displaystyle\geq\frac{\tau\sqrt{n\log
n}}{144}-2\sqrt{n}$

where the last inequality derives from the fact that each $X^{y}_{kl}$ is a
$0-1$ random variable and hence has expectation upper bounded by $1$.

Since both $s_{kl}$ and $s_{ij}$ are each sums of at least $n/16$ independent
$0-1$ random variables, we can use the Chernoff bound to conclude that their
expectations do not differ from their value by more than $24\sqrt{n\log n}$
with very high probability. Putting together these inequalities, we conclude
that, for large enough $\tau$, we have $s_{kl}<s_{ij}$ with high probability.
The proof of this claim assumes that $O(n^{2})$ high probability events occur
simultaneously, since it suffices that a correct subtree pair beats every
wrong subtree pair, of which there are at most $n^{2}$.

∎

An immediate corollary of this claim, via an application of the union bound is
that the highest scoring pair is in fact a sibling-tree pair. This gives an
efficient algorithm that correctly combines subtrees of $T_{S}$ to form a
larger subtree of $T_{S}$. The proof of correctness of one call to the
algorithm Build-Subtree assumes the simultaneous occurrence of $O(n^{3})$ high
probability events - since the subroutine to combine subtrees is used at most
$n$ times (from the fact that each such subroutine introduces an internal
vertex, and there are most $n$ of them). ∎

We show how to partition the leaves within a contiguous interval of buckets
onto either side of a $\sqrt{n}$ sized subtree in the induced topology on the
leaves within this interval.

######  Lemma 4.

Let $T_{B}$ be a subtree of $T$ with $|T_{B}|\geq\sqrt{n}$ and let $I$ be a
contiguous interval in the partition of buckets with respect to $T_{B}$. Let
$T_{P}$ be a subtree of the tree induced on $L(I)$ with between $\sqrt{n}$ and
$2\sqrt{n}$ leaves. Then there exists an algorithm Partition that partitions
$L(I)-L(T_{P})$ into 3 sets $P_{1},P_{2},$ and $P_{3}$ such that $P_{1}$
consists of all leaves in lower indexed buckets than the leaves of $T_{P}$,
$P_{2}$ consists of leaves in the same bucket as $T_{P}$, and $P_{3}$ consists
of leaves in higher numbered buckets. In the case that $L(T_{P})$ comprises
leaves from more than one bucket $P_{1}$ and $P_{2}$ are empty.

###### Proof.

When $P_{2}$ is non empty, all leaves in $T_{P}$ are equidistant from $T_{B}$,
implying that $P_{2}$ must be contained within a single bucket $S_{i}$.

We describe the algorithm Partition that does the partitioning. For each leaf
$x\in L-(T_{B}\cup T_{P})$, introduce $0-1$ random variables $X^{x}_{ab}$ and
$Y^{x}_{ab}$ for each $a\in T_{B},b\in T_{P}$. Each such leaf $x$ has $2n$
such associated random variables, since $|T_{B}|,|T_{P}|\geq\sqrt{n}$.
$X^{x}_{ab}$ is set to $1$ if $Q(a,b,x)$ is $(a,x)$ and $0$ otherwise.
$Y^{x}_{ab}$ is set to $1$ if $Q(a,b,x)$ is $(a,b)$ and $0$ otherwise. Let
$X^{x}=\sum_{a\in T_{B},b\in T_{P}}X^{x}_{ab}$ and $Y^{x}=\sum_{a\in
T_{B},b\in T_{P}}Y^{x}_{ab}$. If $X^{x}-Y^{x}>24\sqrt{n\log n}$, then, $x$ is
placed in set $P^{\prime}_{1}$. If If $Y^{x}-X^{x}>24\sqrt{n\log n}$, then,
$x$ is placed in set $P^{\prime}_{3}$. Otherwise if $|Y^{x}-X^{x}|\leq
24\sqrt{n\log n}$, $x$ is placed in $P^{\prime}_{2}$. We claim that for
$i\in[3],P^{\prime}_{i}=P_{i}$ with high probability.

The first case is $x\in P_{1}$, we know that $d(a,b)\geq
d(a,x)+2\tau\sqrt{\frac{\log n}{n}}$, for all $a\in T_{B},b\in T_{P}$, by the
definition of $S_{1}$ and the minimum weight condition. Using Observation 1,
we conclude that
$\mathbb{E}[X^{x}_{ab}]-\mathbb{E}[Y^{x}_{ab}]\geq\frac{\tau\sqrt{\log
n}}{3\sqrt{n}}$. Using Lemma 1, we conclude that the
$X^{x}-Y^{x}>24\sqrt{n\log n}$, with high probability.

Next, consider $x\in P_{3}$, we know that $d(a,x)\geq
d(a,b)+2\tau\sqrt{\frac{\log n}{n}}$, for all $a\in T_{B},b\in T_{P}$, by the
definition of $S_{1}$ and the minimum weight condition (Observation 1).
Through similar analysis as the previous case, we conclude $x$ is correctly
placed in $P^{\prime}_{3}$ whp.

Finally, we see the case of $x\in P_{2}$. We know that $d(a,x)=d(a,b)>d(b,x)$
for all $a\in T_{B},b\in T_{P}$, by the definition of $S_{2}$.Thus,
$X^{x}_{ab}$ and $Y^{x}_{ab}$ are identical random variables, since the
incorrect answers to any query appear with equal probability. Using the second
part of Lemma 1, we get the desired result about the comparison of $X^{x}$ and
$Y^{x}$, with high probability. Thus, $x$ is correctly placed in
$P^{\prime}_{2}$ whp.

In total, we need $O(n)$ high probability events to happen simultaneously (one
for partitioning each leaf) in this proof of correctness.

We index the buckets of the contiguous interval $I$ as
$S_{j_{1}},S_{j_{1}+1},\cdots$. For the final part of the claim, we analyze
the case where $T_{P}$ consists of leaves from more than one bucket. Let us
index these buckets as $S_{i_{1}},S_{i_{1}+1},\cdots$ where $i_{1}\geq j_{1}$.
Clearly, $T_{P}$ must consist of all leaves in an interval of buckets, since
leaves within a bucket are always closer to each other than leaves in another
bucket (recall that the leaves of each bucket are the leaves of a subtree of
$T$, Ref Fig 1). Due to this property, $P_{2}$ must be empty. Recall that the
set of leaves in $T_{B},S_{1},S_{2}\cdots S_{i}$ forms a tree for any index
$i$. Consequently, every leaf $l\in L(S_{i})$ is closer to any leaf in
$T_{B},S_{1},S_{2},\cdots S_{i-1}$ than to a leaf in $S_{j}$ with $j>i$. Now,
consider the case in which $T_{P}$ consists of leaves contained in a union of
buckets - $S_{i_{1}},S_{i_{1}+1}\cdots S_{i_{2}}$ where $i_{1}>j_{1}$. The
leaves of $T_{P}$ cannot be a set of leaves of a tree in the induced topology
of $L(I)$, since any leaf in $S_{i_{1}}$ is closer to a leaf in $S_{j_{1}}$
(which is part of the set $L(I)$) than to a leaf in $S_{i_{2}}$. We have a
contradiction, invalidating the assumption $i_{1}>j_{1}$. Thus, we must have
$i_{1}=j_{1}$, implying that $P_{1}$ is also empty.

∎

We now have all the details in place for a full description of the algorithm
Topology-Reconstruction. The algorithm creates a base tree $T_{B}$ using
Build-Subtree (Lemma 3) at the beginning. We use the same technique to build a
subtree $T_{P}$ of $L(T)-L(T_{B})$, also with $\Theta(\sqrt{n})$ leaves.

For any two leaves $x,y$ not in $L(T_{B})\cup L(T_{P})$, we will say that
$x\preceq_{T_{B}}y$ iff $x$’s bucket has index less than or equal to $y$’s.
$x$ and $y$ are in the same bucket iff $x\preceq_{T_{B}}y$ and
$y\preceq_{T_{B}}x$. (When the base tree is clear from the context, we will
drop the subscript on the relation symbol.) Using $T_{B}$ and $T_{P}$ and the
technique in Lemma 4, we determine the $\preceq$ relationship for all pairs
$x,y\in L-(L(T_{B})\cup L(T_{P}))$. Based on this, we partition these leaves
into $P_{1},P_{2},$ and $P_{3}$ using Partition( as described in Lemma 4).

Since $T_{P}$ is a subtree of the tree induced on $L-L(T_{B})$, there are two
possibilities for what $T_{P}$ looks like with regard to the partition into
buckets based on $T_{B}$. Either $T_{P}$ is entirely contained within one of
these buckets, or it is the union of an initial interval of buckets. In the
latter case, $P_{1}$ and $P_{2}$ are empty.

If the number of leaves in any of the 3 parts is less than $\frac{11n}{12}$ we
will say that that part is small.

######  Claim 2.

The topology of a small part can be resolved completely with high probability
using the algorithm Completion (from Lemma 2).

###### Proof.

If $P_{1}$ is small, noting that $T_{B}\cup P_{1}$ form a subtree and
appealing to Lemma 2, the topology of $P_{1}$ is inferred using Completion. If
$P_{2}$ is small, there are two cases: if $P_{1}$ is large, an appeal to Lemma
2 suffices, noting that $P_{2}$ lies outside of a large subtree. Else, $P_{3}$
must be large, and once again, we appeal to Lemma 2, but this time using the
fact that $P_{2}$ is part of a small subtree. Finally, when $P_{3}$ is small,
it is very easy to see how the same Lemma implies that the topology of $P_{3}$
can be resolved. ∎

Since there are at least two small parts in the partition, at most one part
will be unresolved at the end of this process. Let us call this part $R$. In
the case that $T_{P}$ did not lie entirely within one bucket, $R$ will be
$P_{3}$ (the only non-empty part).

We now explain how our algorithm recursively resolves the topology of this
contiguous interval. If the pivot tree $T_{P}$ in the current step lies within
$R$ (we must be in the case where $T_{P}$ lies entirely in one bucket, and the
unresolved part is this bucket), then we recurse on $R\,/T_{P}$, the quotient
of $R$ with respect to $T_{P}$. Since $T_{P}$ has at most $2\sqrt{n}$ leaves,
the number of nodes in the quotient will still be large. This recursive call
finds a new base tree, a partition with respect to this tree, and so on. If,
on the other hand, $T_{P}$ lies outside of the unresolved part, we recurse on
the unresolved part, keeping the same base tree and finding a pivot tree
within this part. We will maintain the invariant that $R$ is a contiguous
interval of buckets with respect to the current base tree. If $|R|$ is less
than $11n/12$, we can reconstruct it using Claim 2.

In the case that we change the base, $R$ is an entire bucket, and hence a
subtree of the overall tree. Again if $R$ becomes small enough, we can
reconstruct it directly by appealing to Lemma 2.

Thus, we will be able to complete the reconstruction of the whole tree. One
final subtle point that the reader may wonder about: Could we lose enough
nodes from the quotient-finding operations that $R$ becomes small while the
number of nodes outside of $R$ is also small? A careful accounting shows that
this does not happen: Each time we compute a quotient and remove at most
$2\sqrt{n}$ leaves, we have also created a new base tree with at least
$\sqrt{n}$ leaves, which lies outside and to the left of $R$. Thus if $R$
becomes small due to the quotient operation, the number of leaves on the left
side must be large enough to allow reconstruction of $R$.

To conclude the proof of Theorem 1, we argue that the algorithm Topology-
Reconstruction succeeds with high probability. The key observation is that we
use the various subroutines Completion, Build-Subtree and Partition at most
$O(\sqrt{n})$ times each. This is because we reduce the size of the unresolved
part by $\sqrt{n}$ using only a constant number of calls to these subroutines.
Each of them assume at most $O(n^{3})$ high probability events to be
simultaneously true to succeed, implying that we only need a total of
$O(n^{7/2})$ high probability events to all be true for the algorithm to
correctly recover the topology of the tree. Since each of them occurs with
probability at least $1-\frac{1}{n^{6}}$, an application of the union bound
gives us the desired result. Further, since each subroutine runs in polynomial
time, the overall algorithm is also efficient.

##  5 Weight Reconstruction

In the previous section, we gave an algorithm to reconstruct the topology of
the tree in the general model. In this section, we will show how to
approximately reconstruct the edge weights in the homogeneous model. The
precise theorem is stated below (Theorem 2). Assuming that each root to leaf
path has unit weight, our algorithm can reconstruct the tree as long as each
edge has weight at least $\tau\cdot\log n/\sqrt{n}$. Note that the condition
required here is stronger than Theorem 1 where it suffices that each edge
weight is $\Omega(\sqrt{\log n/n})$.

######  Theorem 2.

Let $T$ be a weighted full binary tree tree such that the weights induce an
ultrametric on the distances between leaves and that the weight on each edge
is at least $\tau\frac{\log n}{\sqrt{n}}$, for some large constant $\tau$.
Then there exists an algorithm Tree-reconstruct-weight, which given access to
the homogeneous model on the leaves of this tree, reconstructs the weight of
each edge with high probability within an additive error $\kappa\frac{\log
n}{\sqrt{n}}$, where $\tau\gg\kappa$).

We explain the high-level strategy for procedure Tree-reconstruct-weight.
Instead of estimating the weight of each edge, we will give a procedure which
for any vertex $v$, will estimate the weight of the path from root to $v$ up
to an additive $\kappa\log n/2\sqrt{n}$. This trivially implies reconstruction
of the weight of each edge up to $\pm\kappa\log n/\sqrt{n}$. Our algorithm
assumes that $\tau\gg\kappa$.

Since the homogeneous model is a special case of the general model (with
$\epsilon=1/6$) and the edge weights satisfy the condition required by Theorem
1 on the edge weights, we can first run Topology-Reconstruction to reconstruct
the topology of the tree (with high probability). The rest of the proof
assumes we have access to the topology of the tree. The main workhorse for
weight reconstruction is the idea that if we have two leaves $a$ and $b$ that
lie in the left subtree of some node $v$, and the right subtree of $v$ has
$\Omega(n)$ leaves, then we can get a good approximation to the height of the
least common ancestor of $a$ and $b$. A related idea is that if we have an
internal node $v$ such that the product of the number of leaves in its left
and right subtrees is $\Omega(n)$, then we can also get a good approximation
to the height of $v$. This leaves the case of nodes $v$ for which neither of
these properties is true and much of the technical difficulty of our algorithm
is in handling such nodes (Lemma 9). For such a node we get several coarse
approximations of its height, which need to be combined carefully because of
subtle dependence between these approximations.

We start by fixing some notation. Let $\mathsf{NL}(v)$ denote the number of
leaves in the sub-tree rooted at vertex $v$. We will adopt the convention that
the children of each node are ordered so that for any node $v$ with right
child $\mathsf{rc}$ and left child $\mathsf{lc}$,
$\mathsf{NL}(\mathsf{rc})\geq\mathsf{NL}(\mathsf{lc})$. Further, without loss
of generality, we can also assume that the binary tree is full – otherwise, if
an internal node $v$ has exactly one child, we can collapse the two edges
incident on $v$ into one. This modification does not affect the output
probabilities associated with any triple of leaves. Finally, for any vertex
$v$, we define $h_{v}$ as the “height” of $v$ – i.e., the total weight of any
path from $v$ to a leaf in its subtree. Because the distance on the tree is an
ultrametric, the choice of the leaf is immaterial.

######  Definition 1.

A vertex $v$ is said to be heavy if $\mathsf{NL}(v)\geq\alpha n+1$ where
$\alpha=\frac{1}{6}$. Otherwise, the vertex is said to be light. By
definition, the root $r$ is a heavy vertex.

Next, given a rooted tree as above, we identify a distinguished vertex $v_{f}$
as follows. Let $P$ be the rightmost path from the root to a leaf . Starting
from the root $r$, let the vertices in $P$ (in order) be $r$,
$v_{1},\ldots,v_{\ell^{\ast}}$ where $v_{\ell^{\ast}}$ is the rightmost leaf.
We define $f$ to be maximum index such that $v_{f}$ is a heavy vertex.

Consider the root $r$, with left child $\mathsf{lc}_{r}$ and right child
$\mathsf{rc}_{r}$. Observe that by our convention, $\mathsf{rc}_{r}$ is a
heavy vertex. We now give a procedure to (approximately) compute $h_{v}$ for
any vertex $v$ in the subtree rooted at $\mathsf{lc}_{r}$.

######  Lemma 5.

There is a procedure Compute-light-tree which with high probability, computes
$h_{v}$ for all vertices $v$ in the tree rooted at $\mathsf{lc}_{r}$ with
accuracy $\Theta(\sqrt{\log n/n})$.

###### Proof.

Consider any non-leaf vertex $v$ in the subtree of $\mathsf{lc}_{r}$. Since
$v$ is a non-leaf vertex, there is a leaf $a$ in its left subtree and $b$ in
the right subtree. Additionally, since $\mathsf{rc}_{r}$ is a heavy vertex,
there are at least $\alpha n$ leaves under it - indexed by
$\\{c_{i}\\}_{i=1}^{k}$ where $k\geq\alpha n$ . Let $\mathbf{X}_{i}$ be the
indicator random variable that query $Q(a,b,c_{i})$ returns $(a,b)$. Each
$\mathbf{X}_{i}$ is an independent (and in fact identically distributed)
random variable such that

$\Pr[\mathbf{X}_{i}=1]=\frac{d(a,c_{i})+d(b,c_{i})}{2(d(a,b)+d(a,c_{i})+d(b,c_{i}))}=\frac{4}{2(4+2h_{v})}=\frac{1}{2+h_{v}}.$

Let us define $\mathbf{A}:=(1/k)\cdot(\sum_{i=1}^{k}\mathbf{X}_{i})$. Define
$h^{\prime}_{v}$ to be such that $\mathbf{A}=\frac{1}{2+h^{\prime}_{v}}$. Now,
by Hoeffding’s inequality (Theorem 5), we get that with overwhelmingly high
probability,

$\bigg{|}\mathbf{A}-\frac{1}{2+h_{v}}\bigg{|}\leq\kappa_{2}\sqrt{\frac{\log
n}{n}}.$

Thus

$\bigg{|}\frac{1}{2+h^{\prime}_{v}}-\frac{1}{2+h_{v}}\bigg{|}\leq\kappa_{2}\sqrt{\frac{\log
n}{n}}.$

This means that

$|h_{v}-h^{\prime}_{v}|\leq\kappa_{2}\sqrt{\frac{\log
n}{n}}(2+h_{v})(2+h^{\prime}_{v}).$

Note that $h_{v}\leq 1$. Because
$\big{|}\frac{1}{2+h^{\prime}_{v}}-\frac{1}{2+h_{v}}\big{|}\leq 1/6$, it
follows that $h^{\prime}_{v}\leq 4$. Thus, it follows that
$|h_{v}-h^{\prime}_{v}|\leq\Theta(\sqrt{\log n/n})$. ∎

Recall that we had define $P$ as the rightmost path in the tree with vertices
$\\{v_{i}\\}_{i=1}^{\ell^{\ast}}$ such that $v_{f}$ is the last heavy vertex
in the sequence. Next, we have the following lemma.

######  Lemma 6.

There is a procedure Reconstruct-right-path which with high probability
computes $h_{v}$ up to $\pm\Theta(\sqrt{\log n/n})$ for any $v_{\ell}$ in the
path $P$ where $\ell\leq f$.

###### Proof.

Consider vertex $v_{\ell}$, since $\ell\leq f$, we know that
$\mathsf{NL}(v_{\ell})\geq\alpha n+1$. Let the number of leaves in the left
(resp. right) subtree of $v_{\ell}$ be $s_{\ell}$ (resp. $s_{r}$). We have
$s_{\ell}+s_{r}\geq\alpha n+1$. It immediately follows that the number of
pairs of the form $(a_{i},b_{i})$ where $a_{i}$ is in the left subtree and
$b_{i}$ is in the right subtree is at least $\alpha n$. Now, let $c$ be a leaf
in the left subtree of the root $r$ – we know that there exists at least one.

Let us now define $\mathbf{X}_{i}$ to be the indicator variable that the query
on triple $(a_{i},b_{i},c)$ returns $(a_{i},b_{i})$. Observe that each
$\mathbf{X}_{i}$ is an i.i.d. Bernoulli random variable such that
$\Pr[\mathbf{X}_{i}=1]=\frac{1}{2+h_{v_{\ell}}}$. Now repeating the same
calculation as done at end of Lemma 5, we obtain an estimate $h^{\prime}_{v}$
such that with overwhelmingly high probability,
$|h^{\prime}_{v}-h_{v}|=\Theta(\sqrt{\log n/n})$.

∎

######  Lemma 7.

Let $v$ be an internal vertex of the tree and let $v_{\ell}$ be a heavy vertex
on path $P$ such that (i) $v_{\ell}$ is an ancestor of vertex $v$; (ii) There
are $k\geq 100$ leaves in the sub-tree of $v_{\ell}$ that does not contain
$v$. Let $a$ and $b$ be leaves in distinct subtrees of $v$ and $c$ a vertex in
the subtree of $v_{l}$ not containing $v$. Let $p$ be the probability that a
query on the triple $(a,b,c)$ returns $(a,b)$. Note that $p$ is independent of
the particular choices of $a,b,$ and $c$ as constrained above. Then, there is
an algorithm that outputs an estimate $\hat{p}$ such that

  1. 1.

$|\hat{p}-p|=O\big{(}\sqrt{\log k/k}\big{)}$.

  2. 2.

$\hat{p}$ is an unbiased estimator of $p$.

We say that vertex $v$ has been anchored to vertex $v_{l}$ to obtain this
estimate.

###### Proof.

We index the leaves in the sub-tree of $v_{\ell}$ not containing $v$ as
$c_{1},c_{2},..c_{k}$. Let $c\in\\{c_{1},\ldots,c_{k}\\}$. As noted in the
statement of the lemma, the probability that $Q(a,b,c)$ returns $(a,b)$ is a
constant $p$ independent of $c$.

The pairwise distances are $d(a,b)=2h_{v}$ and $d(a,c)=d(b,c)=2h_{v_{\ell}}$.
This implies that $p=\frac{h_{v_{\ell}}}{2h_{v_{\ell}}+h_{v}}$. Let
$\mathbf{X}_{i}$ be the indicator random variable that $Q(a,b,c_{i})$ returns
$(a,b)$. Note that

$\Pr[\mathbf{X}_{i}=1]=\frac{h_{v_{\ell}}}{2h_{v_{\ell}}+h_{v}}.$

Now, define $\hat{p}:=(\sum_{i=1}^{k}\mathbf{X}_{i})/k$. Hoeffding’s
inequality (Theorem 5) and linearity of expectation now immediately imply the
claim. ∎

######  Lemma 8.

Suppose $v$ is an internal vertex which lies in the left subtree of $v_{\ell}$
– where $v_{\ell}$ lies on the path $P$ and $1\leq\ell\leq f$. There is a
procedure Reconstruct-height-left-heavy which given as input such a vertex
$v$, reconstructs the height of $v$ up to error $O(\alpha^{-1}\cdot\sqrt{\log
n/n})$.

###### Proof.

We are given that $v_{\ell}$ is an ancestor of $v$. The right subtree of
$v_{\ell}$ has at least $\alpha n$ leaves. Thus, applying Lemma 7, we can
obtain an estimate $\hat{p}$ such that

$\bigg{|}\hat{p}-\frac{h_{v_{\ell}}}{h_{v}+2h_{v_{\ell}}}\bigg{|}=O\bigg{(}\frac{1}{\alpha}\cdot\sqrt{\frac{\log
n}{n}}\bigg{)}.$

Now, $h_{v}$ can be expressed in terms of $h_{v_{\ell}}$ and $p$ as follows:

$h_{v}=\frac{h_{v_{\ell}}\cdot(1-2p)}{p}:=f(v_{\ell},p).$

Using Lemma 6, we can obtain an estimate $\widehat{h_{v_{\ell}}}$ such that

$\big{|}h_{v_{\ell}}-\widehat{h_{v_{\ell}}}\big{|}=\Theta\bigg{(}\sqrt{\frac{\log
n}{n}}\bigg{)}.$

The estimate of the procedure is $\widehat{h_{v}}$ defined as
$f(\widehat{h_{v_{\ell}}},\hat{p})$. We now observe that by triangle
inequality,

$\displaystyle~{}\big{|}f(\widehat{h_{v_{\ell}}},\hat{p})-f(h_{v_{\ell}},p)\big{|}\leq\big{|}f({h_{v_{\ell}}},\hat{p})-f(h_{v_{\ell}},p)\big{|}+\big{|}f(\widehat{h_{v_{\ell}}},\hat{p})-f({h_{v_{\ell}}},\hat{p})\big{|}.$
(1)

To bound the terms on the right hand side, observe that $h_{v_{\ell}}\leq 1$
and $p\in[1/3,1]$. Thus, by Lemma 7, we can assume that $\hat{p}\geq 1/4$.
Consequently,

$~{}\big{|}f({h_{v_{\ell}}},\hat{p})-f(h_{v_{\ell}},p)\big{|}=O\bigg{(}\frac{|p-\hat{p}|}{p^{2}}\bigg{)}=O(|p-\hat{p}|).$
(2)
$~{}\big{|}f({h_{v_{\ell}}},\hat{p})-f(\widehat{h_{v_{\ell}}},\hat{p})\big{|}=O\bigg{(}\frac{\big{|}h_{v_{\ell}}-\widehat{h_{v_{\ell}}}\big{|}}{\hat{p}^{2}}\bigg{)}=O\big{(}\big{|}h_{v_{\ell}}-\widehat{h_{v_{\ell}}}\big{|}\big{)}.$
(3)

Plugging (2) and (3) into (1) gives us the stated claim. ∎

Using Lemma 6 and Lemma 8, we have constructed $h_{v}$ approximately (to
additive $O(\pm\sqrt{\log n/n})$) for all vertices except the ones in the
subtree of $v_{f+1}$. For such vertices $v$, we next show how to compute
$h_{v}$ up to an additive $O(\log n/\sqrt{n})$. Note that this estimate is
slightly worse than the ones achieved in Lemma 8 and Lemma 6.

The above lemmas reconstruct $h_{v}$ for any vertex in the left subtree of any
heavy vertex except the last, as well as any vertex in the “rightmost path”.
We next describe how to compute $h_{v}$ for the remaining vertices, i.e., the
vertices in the subtree rooted at $v_{f+1}$. At this point, we also note that
if there was a vertex $v$ with two heavy children, then the obvious adaptation
of Lemma 5 gives us the weight of every edge in the subtree rooted at $v$, and
hence the entire tree $T$. However, in general, there is no guarantee that
this will happen and we have to go for a more significantly more complicated
procedure. Towards this, we prove the following crucial lemma.

######  Lemma 9.

There is a procedure Reconstruct-Internal-left which given any internal vertex
$v$ in the subtree of $v_{f+1}$, outputs an estimate of $h_{v}$ that has
additive error $O(\log n/\sqrt{n})$ .

This lemma completes the proof of Theorem 2, since we have successfully
reconstructed the heights of all internal vertices of the tree within additive
error $O(\frac{\log n}{\sqrt{n}})$. Since this proof is considerably more
involved than the previous proofs, we present it in Appendix B.

##  6 Necessary Conditions

The goal of this section is to show that to reconstruct the topology of the
tree, it is necessary for each edge to have weight $\Omega(1/{\sqrt{n}})$ –
thus, essentially matching the lower bound assumption in Theorem 1. Recall
that we normalize the edge weights so that the height (weighted root to leaf
distance) of the tree is $1$.

In the theorem below, we give a nearly matching lower bound on the minimum
weight of each edge even for topology reconstruction in our model. We also
note that such edge weight lower bounds are commonplace in the literature on
phylogenetic reconstruction[17, 18, 14].

######  Theorem 3.

Let $T$ be the set of weighted full binary trees tree such that the weights
induce an ultrametric on the distances between leaves (within each tree).
Then, given access to the homogeneous model, as described in Section 3), on
the leaves of this tree, there exists no algorithm that can reconstruct the
topology of the tree if the edge weights can be as small as
$\frac{\rho}{\sqrt{n}}$ where $\rho$ is a sufficiently small constant
($\rho\leq\frac{1}{100}$). A fortiori, we obtain the same lower bound for the
general model as well.

To prove this result, we construct two trees with the following properties:

  1. 1.

They have distinct topologies and the weight of each edge is at least
$\rho/\sqrt{n}$.

  2. 2.

It is information-theoretically impossible to distinguish between the trees
with probability more than $0.51$ (in the homogeneous model).

The two trees $T_{1}$ and $T_{2}$ are as follows. Both have roots with
identical weighted left subtrees $B$. The right subtrees of both $T_{1}$ and
$T_{2}$ both have three leaves $a,b,$ and $c$ but with different induced
topologies. In $T_{1}$, $a$ and $b$ are sibling leaves with parent $p$. The
parent of $c$ and $p$ is the node $q$, which is the right child of the root.
In $T_{2}$, $a$ and $c$ are siblings, whose parent is $x$. $x$ and $b$ have a
parent $y$, which is the right child of the root. All ‘corresponding’ edge
lengths are identical and in particular, the edges $(p,q)$ and $(x,y)$ have
weight $\frac{\rho}{\sqrt{n}}$. The edges to the sibling pair of leaves in the
right subtree of both trees have the same weight, say $\frac{1}{3}$. The two
trees we construct are shown in Figures 3 and 4 in Appendix E (supplementary
material).

The rest of the proof of Theorem 3 has been moved to Appendix C, in interest
of space.

## References

  * Ga [08] Gang Wu and Ming-Yang Kao and Guohui Lin and Jia-Huai You.  Reconstructing phylogenies from noisy quartets in polynomial time with a high success probability.  Algorithms for Molecular Biology, 3(1):377–390, 2008.
  * Abb [17] Emmanuel Abbe.  Community detection and stochastic block models: recent developments.  The Journal of Machine Learning Research, 18(1):6446–6531, 2017\.
  * AC [05] Nir Ailon and Moses Charikar.  Fitting tree metrics: Hierarchical clustering and phylogeny.  In 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS’05), pages 73–82. IEEE, 2005.
  * AFB [94] Richa Agarwala and David Fernández-Baca.  A polynomial-time algorithm for the perfect phylogeny problem when the number of character states is fixed.  SIAM J. Computing, 23:1216–1224, January 1994.
  * Ami [98] Amir Ben-Dor and Benny Chor and Dan Graur and Ron Ophir and Dan Pelleg.  Constructing phylogenies from quartets: elucidation of eutherian superordinal relationships. .  Journal of Computational Biology, pages 377–390, Jan 1998.
  * AWC+ [07] Sameer Agarwal, Josh Wills, Lawrence Cayton, Gert Lanckriet, David Kriegman, and Serge Belongie.  Generalized non-metric multidimensional scaling.  In Artificial Intelligence and Statistics, pages 11–18. PMLR, 2007\.
  * BHH+ [08] Boaz Barak, Moritz Hardt, Ishay Haviv, Anup Rao, Oded Regev, and David Steurer.  Rounding parallel repetitions of unique games.  In 2008 49th Annual IEEE Symposium on Foundations of Computer Science, pages 374–383. IEEE, 2008.
  * BT [52] Ralph Allan Bradley and Milton E. Terry.  Rank Analysis of Incomplete Block Designs: I. The Method of Paired Comparisons.  Biometrika, 39(3/4):324–345, 1952.
  * BT [13] Daniel Brown and Jakub Truszkowski.  Fast error-tolerant quartet phylogeny algorithms.  Theoretical Computer Science, 483:104–114, 2013.
  * CKK [20] Yu Chen, Sampath Kannan, and Sanjeev Khanna.  Near-perfect recovery in the one-dimensional latent space model.  In Proceedings of The Web Conference 2020, pages 1932–1942, 2020\.
  * DKMZ [11] Aurelien Decelle, Florent Krzakala, Cristopher Moore, and Lenka Zdeborová.  Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications.  Physical Review E, 84(6):066106, 2011.
  * DMR [06] Constantinos Daskalakis, Elchanan Mossel, and Sébastien Roch.  Optimal phylogenetic reconstruction.  In Proceedings of the thirty-eighth Annual ACM Symposium on Theory of Computing, pages 159–168, 2006.
  * DR [13] Constantinos Daskalakis and Sebastien Roch.  Alignment-free phylogenetic reconstruction: Sample complexity via a branching process analysis.  The Annals of Applied Probability, 23(2):693–721, 2013.
  * [14] Péter L Erdős, Michael A Steel, László A Székely, and Tandy J Warnow.  A few logs suffice to build (almost) all trees (i).  Random Structures & Algorithms, 14(2):153–184, 1999.
  * [15] Péter L Erdös, Michael A Steel, LászlóA Székely, and Tandy J Warnow.  A few logs suffice to build (almost) all trees: Part II.  Theoretical Computer Science, 221(1-2):77–118, 1999.
  * EZK [18] Ehsan Emamjomeh-Zadeh and David Kempe.  Adaptive Hierarchical Clustering Using Ordinal Queries.  In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, page 415–429, 2018.
  * Fel [81] Joseph Felsenstein.  Evolutionary trees from DNA sequences: a maximum likelihood approach.  Journal of Molecular Evolution, 17(6):368–376, 1981.
  * FK [99] Martin Farach and Sampath Kannan.  Efficient algorithms for inverting evolution.  Journal of the ACM (JACM), 46(4):437–449, 1999.
  * FKW [95] M. Farach, S. Kannan, and T. Warnow.  A robust model for finding optimal evolutionary trees.  Algorithmica, 13(1-2):155–179, February 1995.
  * HA [15] Elad Hoffer and Nir Ailon.  Deep metric learning using triplet network.  In International workshop on similarity-based pattern recognition, pages 84–92. Springer, 2015.
  * JN [11] Kevin G Jamieson and Robert Nowak.  Active ranking using pairwise comparisons.  Advances in neural information processing systems, 24, 2011.
  * KHM [97] Paul E. Kearney, Ryan B. Hayward, and Henk Meijer.  Inferring Evolutionary Trees from Ordinal Data.  In Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 418–426, 1997.
  * KL [14] Matthäus Kleindessner and Ulrike Luxburg.  Uniqueness of ordinal embedding.  In Conference on Learning Theory, pages 40–67. PMLR, 2014.
  * KLW [96] Sampath K Kannan, Eugene L Lawler, and Tandy J Warnow.  Determining the evolutionary tree using experiments.  Journal of Algorithms, 21(1):26–50, 1996.
  * KW [94] Sampath Kannan and Tandy Warnow.  Inferring evolutionary history from dna sequences.  SIAM J. Computing, 23(4):713–737, August 1994.
  * Luc [59] R Duncan Luce.  Individual choice behavior: A theoretical analysis.  Courier Corporation, 1959.
  * McF [73] Daniel McFadden.  Conditional logit analysis of qualitative choice behavior.  1973\.
  * McS [01] Frank McSherry.  Spectral partitioning of random graphs.  In Proceedings 42nd IEEE Symposium on Foundations of Computer Science, pages 529–537. IEEE, 2001.
  * MNS [18] Elchanan Mossel, Joe Neeman, and Allan Sly.  A proof of the block model threshold conjecture.  Combinatorica, 38(3):665–708, 2018.
  * Mos [07] Elchanan Mossel.  Distorted Metrics on Trees and Phylogenetic Forests.  IEEE/ACM Transactions on Computational Biology and Bioinformatics, 4(1):108–116, 2007.
  * MR [05] Elchanan Mossel and Sébastien Roch.  Learning nonsingular phylogenies and hidden Markov models.  In Proceedings of the thirty-seventh annual ACM symposium on Theory of Computing, pages 366–375, 2005.
  * MR [17] Elchanan Mossel and Sebastien Roch.  Distance-based species tree estimation under the coalescent: information-theoretic trade-off between number of loci and sequence length.  The Annals of Applied Probability, 27(5):2926–2955, 2017.
  * MS [07] Elchanan Mossel and Mike A. Steel.  How much can evolved characters tell us about the tree that generated them?  In Olivier Gascuel, editor, Mathematics of Evolution and Phylogeny. Oxford University Press, 2007.
  * Ney [71] Jerzy Neyman.  Molecular studies of evolution: a source of novel statistical problems.  In Statistical decision theory and related topics, pages 1–27. Elsevier, 1971.
  * Pla [75] Robin L Plackett.  The analysis of permutations.  Journal of the Royal Statistical Society: Series C (Applied Statistics), 24(2):193–202, 1975.
  * Pol [01] David Pollard.  A User’s Guide to Measure Theoretic Probability.  Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2001.
  * RS [17] Sebastien Roch and Allan Sly.  Phase transition in the sample complexity of likelihood-based phylogeny inference.  Probability Theory and Related Fields, 169(1):3–62, 2017.
  * SJ [03] Matthew Schultz and Thorsten Joachims.  Learning a distance metric from relative comparisons.  Advances in neural information processing systems, 16, 2003.
  * SN [87] Naruya Saitou and Masatoshi Nei.  The neighbor-joining method: a new method for reconstructing phylogenetic trees.  Molecular biology and evolution, 4(4):406–425, 1987.
  * SS [03] C. Semple and M. Steel.  Phylogenetics. Oxford Lecture Series in Mathematics and Its Applications.  Oxford University Press, 2003.
  * Ste [16] Mike Steel.  Phylogeny: discrete and random processes in evolution.  SIAM, 2016.
  * TLB+ [11] Omer Tamuz, Ce Liu, Serge Belongie, Ohad Shamir, and Adam Tauman Kalai.  Adaptively learning the crowd kernel.  In International Conference on Machine Learning (ICML), 2011.
  * VDMW [12] Laurens Van Der Maaten and Kilian Weinberger.  Stochastic triplet embedding.  In 2012 IEEE International Workshop on Machine Learning for Signal Processing, pages 1–6. IEEE, 2012.

##  Appendix A Proofs from Section 4 (Topology Reconstruction)

###  A.1 Proof of Lemma 1

Since $X$ and $Y$ are each sums of at least $\frac{n}{16}$ independent $0,1$
random variables, we use the Hoeffding bound (Theorem 5) to argue that the
events $|X-\mathbb{E}[X]|\leq 6\sqrt{n\log n}$ and $|Y-\mathbb{E}[Y]|\leq
6\sqrt{n\log n}$ each happen with high probability, i.e with
$1-\frac{1}{2n^{6}}$. Using the union bound, both events happen with
probability at least $1-\frac{1}{n^{6}}$.

For the first part of the lemma, since for each $i\in[L]$,
$\mathbb{E}[X_{i}]\leq\mathbb{E}[Y_{i}]-c\sqrt{\frac{\log n}{n}}$, using
linearity of expectation gives :
$\mathbb{E}[X]\leq\mathbb{E}[Y]-c\sqrt{\frac{\log n}{n}}$. Using the triangle
inequality, we conclude that $|X-Y|<12\sqrt{n\log n}$ is true with probability
at least $1-\frac{1}{n^{6}}$.

For the second part of the lemma, since $X_{i}$ and $Y_{i}$ are identical
random variables, $\mathbb{E}[X]=\mathbb{E}[Y]$. Using the triangle
inequality, we conclude that $Y>X+24\sqrt{n\log n}$ is true with probability
at least $1-\frac{1}{n^{6}}$.

###  A.2 Proof of Lemma 2

Part 1: First, we describe how Completion reconstructs the buckets
$S_{1},S_{2},\cdots S_{k}$ that partition $L(T)-L(T^{\prime})$. Let
$L^{\prime}$ be the set of leaves in $T^{\prime}$.

The following test is used to resolve the relative order of two leaves $x,y\in
L\setminus L^{\prime}$. For each $a\in L^{\prime}$, the random variable
$X_{a}$ is set to 1 if the result of the experiment $Q(a,x,y)$ is $(a,x)$, and
to 0 otherwise. Similarly, the random variable $Y_{a}$ is set to 1 if the
result of this experiment is $(a,y)$, and to 0 otherwise. Let $X=\sum_{a\in
L^{\prime}}X_{a}$ and $Y=\sum_{a\in L^{\prime}}Y_{a}$.

If $X-Y>24\sqrt{n\log n}$, then we declare that $x$’s bucket has a lower index
than $y$’s. Otherwise, if $|X-Y|\leq 24\sqrt{n\log n}$, we say that $x$ and
$y$ are in the same bucket. We prove that this algorithm is correct with high
probability.

We first show that the above method of comparison works correctly for any pair
of leaves $x,y$ in different buckets. Without loss of generality, $x\in S_{i}$
and $y\in S_{j}$ with $i<j$. Using Observation 1 about experiment $Q(a,x,y)$,
we conclude that $\mathbb{E}[X_{a}]-\mathbb{E}[Y_{a}]\geq
2\tau\sqrt{\frac{\log n}{n}}$. Using Lemma 1, we get the desired result about
the comparison of $X$ and $Y$, with high probability.

We next extend the result to pairs of leaves $x,y$ in the same bucket $S_{i}$.
We know that $d(a,x)=d(a,y)>d(x,y)$ for all $a\in L^{\prime}$.Thus, $X_{a}$
and $Y_{a}$ are identically distributed random variables (since our noise
model guarantees that the two incorrect answers to a experiment appear with
equal probability). Using the second part of Lemma 1, we get the desired
result about the comparison of $X$ and $Y$, with high probability.

Finally, Completion labels the buckets generated by doing all pairwise tests
using a standard topological sorting algorithm to recover the original labels.
$O(n^{2})$ high probability events are assumed to simultaneously occur as part
of this proof, since we are comparing all pairs of leaves.

In the next phase, the algorithm Completion resolves the closest pair of three
leaves from the same bucket. A score $s_{ab}$ is associated with each pair of
leaves $a,b\in S_{i}$ and a $0-1$ random variables $X^{x}_{ab}$ is defined for
each $x\in L^{\prime}$. Each pair $a,\,b$ has at least $\frac{n}{12}$
associated random variables. $X^{x}_{ab}$ is set to $1$ if $Q(a,b,x)$ is
$(a,b)$ and $0$ otherwise. Let $s_{ab}=\sum_{x\in L^{\prime}}X^{x}_{ab}$.
Given three leaves $a,b,c\in S_{i}$ the pair with the highest score is
declared to be the closest pair.

We argue that this test succeeds with high probability. Let $(a,b)$ be the
closest pair among $(a,b,c)$. We will show that with high probability
$s_{ab}>s_{bc}$. (An identical argument helps establish that $s_{ab}>s_{ac}$.)
We observe that $d(b,c)\geq d(a,b)+2\tau\sqrt{\frac{\log n}{n}}$ and
$d(a,b)<d(b,c)<d(a,x)=d(b,x)=d(c,x)$ for all $x\in L^{\prime}$. By the
properties of the noise model (the bound on the partial derivative), we get
$\mathbb{E}[X^{x}_{ab}]-\mathbb{E}[X^{x}_{ac}]\geq 2\tau\sqrt{\frac{\log
n}{n}}$. Using Lemma 1, we get the desired result about the comparison of
$s_{ab}$ and $s_{bc}$, with high probability.

$O(n^{3})$ high probability events are assumed to simultaneously occur as part
of this proof, since we are separately arguing correct recovery of the closest
pair for every possible set of three leaves.

Part 2: Let $L^{\prime}$ be the set of leaves in $T^{\prime}$. We describe how
the algorithm Completion recovers the topology of $T^{\prime}$.

A score $s_{ab}$ is associated with each pair of leaves $a,b\in L^{\prime}$
and a $0-1$ random variables $X^{x}_{ab}$ is defined for each $x\in L\setminus
L^{\prime}$. Each leaf pair $a,b$ has at least $\frac{n}{12}$ associated
random variables. $X^{x}_{ab}$ is set to $1$ if $Q(a,b,x)$ is $(a,b)$ and $0$
otherwise. Let $s_{ab}=\sum_{x\in L\setminus L^{\prime}}X^{x}_{ab}$. Given
three leaves $a,b,c\in L^{\prime}$, the closest pair is chosen as the pair
with the largest score. The argument that this test succeeds with high
probability uses Lemma 1 in a manner similar to the proof of Part 1 and hence
we omit it. $O(n^{3})$ high probability events are assumed to simultaneously
occur as part of this proof, since we are separately arguing correct recovery
of the closest pair for every possible set of three leaves.

##  Appendix B Proof of Lemma 9 (Weights Reconstruction)

Recall that the vertices in path $P$ are $v_{0},\ldots,v_{f}$ (in order) where
$v_{0}$ is the root and $v_{f}$ is the last heavy vertex. By definition, this
implies that the total number of leaves in the left subtrees of $v_{0}$,
$v_{1}$, $\ldots$, $v_{f}$ is at least $(1-\alpha)n-1$. For $0\leq i\leq f$,
let $\mathsf{C}_{i}$ be the set of leaves in the left subtree of $v_{i}$. Then
$\sum_{i=0}^{f}|\mathsf{C}_{i}|\geq(1-\alpha)n-1>n/2$ (as $\alpha\leq 0.49$).
Let $\mathcal{A}:=\\{v_{i}:|\mathsf{C}_{i}|<n/(4(1+f))\\}$. It easily follows
that $\sum_{i\not\in A}|\mathsf{C}_{i}|>n/4$.

Let the elements of $\overline{\mathcal{A}}$ (in order) be
$t_{1},\ldots,t_{k}$. Let $c\in\mathsf{C}_{t_{i}}$ and let $a$ and $b$ be
vertices in different subtrees of $v$. Then, note that the probability with
which $Q(a,b,c)$ returns $(a,b)$ is $p_{i}$ where
$p_{i}=h_{t_{i}}/(2h_{t_{i}}+h_{v})$. We now apply Lemma 7 and using
$v_{t_{i}}$ as an anchor for $v$ – with overwhelmingly high
probability($1-\frac{1}{n^{6}}$), this gives us an estimate $\hat{p}_{i}$ such
that

$|\hat{p}_{i}-p_{i}|\leq
4\bigg{(}\sqrt{\frac{\log|\mathsf{C}_{t_{i}}|}{|\mathsf{C}_{t_{i}}|}}\bigg{)}$

At this point, one might ask whether any of the estimates $\hat{p}_{i}$ is
good enough to construct a good estimate $\widehat{h}_{v}$ for the height of
vertex $v$. However, note that the best guarantee that we can give for any
$|C_{t_{i}}|$ is at most $\theta(\sqrt{n}\log n)$, since the number of
vertices on a root to leaf path (to which $f$ may be comparable) can
potentially be as bad as $\frac{\sqrt{n}}{\log n}$. To demonstrate such an
instance, consider the tree where each edge the rightmost path from the root
to leaf path has weight $\theta(\frac{\sqrt{n}}{\log n})$, and each heavy
vertex has $\theta(\sqrt{n}\log n)$ vertices in its left subtree. With such a
guarantee, using similar techniques as in the proof of Lemma 8, we can only
obtain an estimate for $h_{v}$ such that the additive error is upper bounded
by $O(\frac{1}{n^{1/4}\log n})$. Such an estimate falls well short of our
target of $O(\frac{\log n}{n})$ additive error.

To get a better estimate, we use the fact that the set of random variables
$\\{\hat{p}_{i}\\}_{i\in[k]}$ are independent, owing to the fact that they are
functions of disjoint sets of queries. We expect to see that errors in these
random variables balance out when we aggregate them in some fashion. A natural
approach is to use each $\hat{p}_{i}$ to construct an estimator
$\widehat{h}^{i}_{v}=\widehat{h}_{t_{i}}(\frac{1}{\hat{p}_{i}}-2)$ for $h_{v}$
and take the weighted average (weighted by the $|C_{t_{i}}|$s). However, this
approach runs into difficulties, triggered by the fact that the random
variables $\widehat{h}^{i}_{v}$ are not unbiased estimators for $h_{v}$. To
avoid this issue, we aggregate the $\hat{p}_{i}$’s directly and then recover a
single estimate $\widehat{h}_{v}$ for $h_{v}$ from the aggregated quantity. In
particular, we focus on estimating the quantity
$Q:=\frac{\sum_{i}|C_{t_{i}}|p_{i}}{\sum_{i}|C_{t_{i}}|}$ through an estimator
$\widehat{Q}$ and recovering a good estimate $\widehat{h}_{v}$ for$h_{v}$
using the estimate $\widehat{Q}$. The proof is complete if we prove the
following two claims.

######  Claim 3.

From the estimators $\\{\hat{p}_{i}\\}_{i\in[k]}$, there exists an algorithm
to recover an estimator $\widehat{Q}$ for
$Q=\frac{\sum_{i}|C_{t_{i}}|p_{i}}{\sum_{i}|C_{t_{i}}|}$ such that
$|\widehat{Q}-Q|\leq\theta\bigg{(}\frac{\log n}{\sqrt{n}}\bigg{)}$.

######  Claim 4.

Given a good estimate $\widehat{Q}$ for
$Q=\frac{\sum_{i}|C_{t_{i}}|p_{i}}{\sum_{i}|C_{t_{i}}|}$, i..e, with additive
error $O\bigg{(}\frac{\log n}{\sqrt{n}}\bigg{)}$, there exists an algorithm
Final- Estimate that uses estimators $\\{\widehat{h}_{t_{i}}\\}_{i\in[k]}$ to
construct an estimator $\widehat{h}_{v}^{f}$ for $h_{v}$ with additive error
$O\bigg{(}\frac{\log n}{\sqrt{n}}\bigg{)}$.

Proof of Claim 3: Assume, for sake of a thought experiment, that each
$\hat{p}_{i}$ is restricted to a range of
$\theta\bigg{(}\sqrt{\frac{\log|\mathsf{C}_{t_{i}}|}{|\mathsf{C}_{t_{i}}|}}\bigg{)}$
around $p_{i}$. Then, if we take the weighted average
$\frac{\sum_{i}|C_{t_{i}}|\hat{p}_{i}}{\sum_{i}|C_{t_{i}}|}$ of the
$\hat{p}_{i}$s, the size of the range of each term
$\frac{|C_{t_{i}}|\hat{p}_{i}}{\sum_{i}|C_{t_{i}}|}$ is at most
$\theta\bigg{(}\frac{\sqrt{|C_{t_{i}}|\log n}}{n}\bigg{)}$. Thus, the variance
of the sum is upper bounded by $O(\frac{\log n}{n})$ (this uses the fact that
$n\geq\sum_{i}|C_{t_{i}}|\geq\frac{n}{4}$). Using an exponential tail bound
would lead us to the desired result under this thought experiment.

Consequently, the natural approach is to directly take the weighted average of
the $\hat{p}_{i}$s, since this would be an unbiased estimator for $Q$.
However, we only have the guarantee that each $\hat{p}_{i}$ is at most
$\theta\bigg{(}\sqrt{\frac{|\mathsf{C}_{t_{i}}|\log
n}{|\mathsf{C}_{t_{i}}|}}\bigg{)}$ away from $p_{i}$ as a high probability
event rather than as absolute truth. To get around this roadblock, for each
$i\in[k]$, we define a real valued random variable $\widetilde{p}_{i}$, and
introduce the following coupling between $\hat{p}_{i}$ and $\widetilde{p}_{i}$
based on truncating $\hat{p}_{i}$:

$\widetilde{p}_{i}=\begin{cases}\hat{p}_{i},\text{ when
}|\hat{p}_{i}-p_{i}|\leq
4\bigg{(}\sqrt{\frac{\log|\mathsf{C}_{t_{i}}|}{|\mathsf{C}_{t_{i}}|}}\bigg{)}\\\
p_{i}+4\bigg{(}\sqrt{\frac{\log|\mathsf{C}_{t_{i}}|}{|\mathsf{C}_{t_{i}}|}}\bigg{)},\text{
when
}\hat{p}_{i}-p_{i}>4\bigg{(}\sqrt{\frac{\log|\mathsf{C}_{t_{i}}|}{|\mathsf{C}_{t_{i}}|}}\bigg{)}\\\
p_{i}-4\bigg{(}\sqrt{\frac{\log|\mathsf{C}_{t_{i}}|}{|\mathsf{C}_{t_{i}}|}}\bigg{)},\text{
otherwise }\end{cases}$

We complete the description of the algorithm by defining our final estimator :
$\widehat{Q}:=\frac{|C_{t_{i}}|\hat{p}_{i}}{\sum_{i}|C_{t_{i}}|}$ .

We observe that the random variables $\\{\widetilde{p}_{i}\\}_{i\in[k]}$ are
independent. This follows from the fact that the random variables
$\\{\hat{p}_{i}\\}_{i\in[k]}$ are themselves independent. As a consequence of
this doing this truncation, the resultant $\widetilde{p}_{i}$ is no longer an
unbiased estimator of $p_{i}$, however we show that this does not functionally
affect us. To do so, we prove a claim showing that the expectations of the
coupled random variables are very close to each other.

######  Claim 5.

For each $i\in[k]$,
$|\mathbb{E}[\widetilde{p}_{i}]-\mathbb{E}[\hat{p}_{i}]|\leq\frac{2}{n^{6}}$.

###### Proof.

We already know that
$\Pr[|\hat{p}_{i}-p_{i}|\geq\kappa_{1}\bigg{(}\sqrt{\frac{\log|\mathsf{C}_{t_{i}}|}{|\mathsf{C}_{t_{i}}|}}\bigg{)}]\leq\frac{1}{n^{6}}$.
Additionally, the random variable $\hat{p}_{i}$ takes its value in the range
$[0,1]$ since it is an empirical average. This also implies that
$\mathbb{E}[\hat{p}_{i}]=p_{i}\in[0,1]$. Thus, we have:

$|\mathbb{E}[\widetilde{p}_{i}]-\mathbb{E}[\hat{p}_{i}]|\leq|\frac{1-p_{i}}{n^{6}}|+|\frac{p_{i}}{n^{6}}|$

which gives us the desired result. ∎

Now, define $j_{i}:=|C_{t_{i}}|$ for each $i\in[k]$. Define the function
$g(\widetilde{p}_{1},\widetilde{p}_{2},..\widetilde{p}_{k}):=\frac{\sum_{i=1}^{k}j_{i}\widetilde{p}_{i}}{\sum_{i=1}^{k}j_{i}}$
on the domain $\mathbb{R}^{k}$ Each random variable
$\frac{j_{i}\widetilde{p}_{i}}{\sum_{l=1}^{k}j_{l}}$ is within the interval
$[a_{i},b_{i}]$ such that $L_{i}=|b_{i}-a_{i}|=\theta(\frac{\sqrt{j_{i}\log
n}}{n})$. We know that
$\sum_{i=1}^{k}L^{2}_{i}=\sum_{i=1}^{k}\theta(\frac{j_{i}\log
n}{n^{2}})=\theta(\frac{\log n}{n})$.

Using the above property, we appeal to the generalized Hoeffding bound
(Theorem 4).With probability at most $\frac{1}{n^{6}}$, we have
$|g(\widetilde{p}_{1},\widetilde{p}_{2},..,\widetilde{p}_{k})-\mathbb{E}[g(\widetilde{p}_{1},\widetilde{p}_{2},..,\widetilde{p}_{k})]|\geq\theta\bigg{(}\frac{\log
n}{\sqrt{n}}\bigg{)}$. Using Claim 5, we know that
$|\mathbb{E}[g(\widetilde{p}_{1},\widetilde{p}_{2},..,\widetilde{p}_{k})]-\mathbb{E}[\frac{\sum_{i}j_{i}\hat{p}_{i}}{\sum_{i}j_{i}}]|\leq\frac{2}{n^{6}}$.
Using linearity of expectation, we know that
$\mathbb{E}[\frac{\sum_{i}j_{i}\hat{p}_{i}}{\sum_{i}j_{i}}]=\frac{\sum_{i}j_{i}p_{i}}{\sum_{i}j_{i}}=Q$.
Using the triangle inequality, the event
$|\widehat{Q}-Q|\leq\theta\bigg{(}\frac{\log n}{\sqrt{n}}\bigg{)}$ happens
with high probability.

∎

Proof of Claim 4:

First, we describe how to recover estimator $\widehat{h}_{v}^{f}$ for $h_{v}$
from $\widehat{Q}$ using the estimates $\\{\widehat{h}_{t_{i}}\\}_{i\in[k]}$.

Define $j_{i}:=|C_{t_{i}}|$ for each $i\in[k]$. We define a multivariate
function $F$ that operates on inputs $a\in\mathbb{R}$ and
$b=(b_{1},b_{2},\cdots b_{k})\in\mathbb{R}^{k}$.

$F(a,b):=\frac{\sum_{i=1}^{k}\frac{j_{i}b_{i}}{2b_{i}+a}}{\sum_{i}j_{i}}$

Alternatively, we write
$F(a,b)=\frac{\sum_{i=1}^{k}j_{i}f(a,b_{i})}{\sum_{i}j_{i}}$ where
$f(a,b_{i})=\frac{b_{i}}{2b_{i}+a}$, i.e., we write $f$ as a convex
combination of $k$ functions. For ease of notation, we call
$\alpha_{i}=\frac{j_{i}}{\sum_{a=1}^{k}j_{a}}$. Note that all $\alpha>0$ and
$\sum_{i}\alpha_{i}=1$.

Let $H=\\{h_{t_{1}},h_{t_{2}},\cdots h_{t_{k}}\\}$ and
$\widehat{H}=\\{\widehat{h}_{t_{1}},\widehat{h}_{t_{2}},\cdots\widehat{h}_{t_{k}}\\}$.
Observe that $Q=F(h_{v},H)$. Intuitively, we want to invert the value
$\widehat{Q}$ of the function $F$ using our estimates $H^{\prime}$ to obtain
an estimate $\widehat{h}_{v}$ that is close to $h_{v}$. We prove a claim below
that tells us how to do so.

######  Claim 6.

There exists a unique real number $\widehat{h}_{v}$ such that
$F(\widehat{h}_{v},\widehat{H})=\widehat{Q}$. Additionally, this real number
can be found using numerical methods from $\widehat{Q}$ and $\widehat{H}$.

###### Proof.

Fix the second argument of $F$ to be $\widehat{H}$, $F$ is now a univariate
function on the first argument. This function is monotone decreasing since
each univariate function $f(a,\widehat{h}_{t_{i}})$ is monotone decreasing and
$F(a,\widehat{H})$ is a convex combination of these functions. Thus, $F$ is
invertible. Further, simple numerical methods such as binary search can be
used to find $\widehat{h}_{v}$ upto arbitrary precision such that
$F(\widehat{h}_{v},\widehat{H})=\widehat{Q}$. ∎

The algorithm then makes the following final correction to the estimate :
$\widehat{h}_{v}^{f}\leftarrow\min\\{\widehat{h}_{v},\min_{i}\widehat{h}_{t_{i}}\\}$
\- there is a compelling reason to make such a correction - to ensure that the
vertex $v$ always has estimated height that is no larger than the estimated
height of one of its ancestors. Note that since we eventually show that the
error in estimating edge weight is only a fraction of the minimum edge weight,
such an event never happens in practice - however, we include this correction
for the sake of the analysis leading to the proof of that result.

First, we show a simplified analysis, for the case that
$\widehat{h}_{v}\leq\min_{i}\widehat{h}_{t_{i}}$. Here the final estimator is
$\widehat{h}_{v}^{f}=\widehat{h}_{v}$. We will later show a more involved
analysis for when our estimate does not satisfy these conditions.

For the sake of contradiction, assume that
$|\widehat{h}_{v}-h_{v}|\geq\Delta\frac{\log n}{\sqrt{n}}$, where $\Delta$ is
a sufficiently large constant. Since $|\widehat{Q}-Q|\leq\theta(\frac{\log
n}{\sqrt{n}})$, we get:

$\displaystyle|\sum_{i}\alpha_{i}\\{f(h_{v},h_{t_{i}})-f(\widehat{h}_{v},\widehat{h}_{t_{i}})\\}|$
$\displaystyle\leq\theta(\frac{\log n}{\sqrt{n}})$
$\displaystyle\implies|\sum_{i}\alpha_{i}\\{(f(h_{v},h_{t_{i}})-f(\widehat{h}_{v},h_{t_{i}}))+(f(\widehat{h}_{v},h_{t_{i}})-f(\widehat{h}_{v},\widehat{h}_{t_{i}}))\\}|$
$\displaystyle\leq\theta(\frac{\log n}{\sqrt{n}})$ (*)

Our approach is to show that each
$A_{i}:=|f(h_{v},h_{t_{i}})-f(\widehat{h}_{v},h_{t_{i}})|$ is sufficiently
larger (by at least some $\Omega(\frac{\log n}{\sqrt{n}})$ than any
$B_{i}:=|f(\widehat{h}_{v},h_{t_{i}})-f(\widehat{h}_{v},\widehat{h}_{t_{i}})|$.
Using the triangle inequality would finish the proof. To this purpose, recall
that $|\widehat{h}_{t_{i}}-h_{t_{i}}|\leq\theta(\sqrt{\frac{\log n}{n}})$.

Intuitively, we wish to show that the function $f(a,b_{i})$ changes rapidly
with change in the first input $a$ (large partial derivative in our interval
of interest) while it is relatively more stable with change in the second
input $b_{i}$ (small partial derivative in our interval of interest). To do
so, we prove some properties of the function $f(a,b_{i})$.

$\frac{\partial f(a,b_{i})}{\partial b_{i}}=\frac{a}{(2b_{i}+a)^{2}}$

$\frac{\partial f(a,b_{i})}{\partial a}=\frac{-b_{i}}{(2a_{i}+b)^{2}}$

We know that $h_{t_{i}}>h_{v}$ for all indices $i$. Additionally,
$h_{t_{i}}\geq\tau\frac{\log n}{\sqrt{n}}$ where $\tau$ is a large constant.
We argue that it is not possible to independently bound each quantity $A_{i}$
and $B_{i}$ \- to see why this is the case - observe that the partial
derivative with respect to $b_{i}$ can only be upper bounded by a constant
while the partial derivative with respect to $a$ can be as small as
$\theta(\frac{\log n}{\sqrt{n}})$. These bounds do not suffice to prove the
desired comparison between the quantities $A_{i}$ and $B_{i}$. Therefore, it
is important that we carefully compare these partial derivatives when
establishing that $A_{i}$ is significantly larger than $b_{i}$. More formally
: Using the intermediate value theorem on the (continuous) univariate function
$f(a,h_{t_{i}})$ (Second argument fixed to be $h_{t_{i}}$) in the interval
$[h_{v},h^{\prime}_{v}]$, we know there exists $x\in[h_{v},h^{\prime}_{v}]$
such that:

$\displaystyle A_{i}=|f(h_{v},h_{t_{i}})-f(\widehat{h}_{v},h_{t_{i}})|$
$\displaystyle=\left|\frac{\partial f(a,h_{t_{i}})}{\partial
a}\right|_{a=x}.|h_{v}-\widehat{h}_{v}|$
$\displaystyle=\left|\frac{h_{t_{i}}}{(2h_{t_{i}}+x)^{2}}\right|.|h_{v}-\widehat{h}_{v}|$

Similarly, using the intermediate value theorem on the univariate function
$f(\widehat{h}_{v},b)$ (first argument fixed to be $\widehat{h}_{v}$) in the
interval $[h_{t_{i}},\widehat{h}_{t_{i}}]$, we know there exists
$y\in[h_{t_{i}},\widehat{h}_{t_{i}}]$ such that:

$\displaystyle
B_{i}=|f(\widehat{h}_{v},h_{t_{i}})-f(\widehat{h}_{v},\widehat{h}_{t_{i}})|$
$\displaystyle=\left|\frac{\partial f(\widehat{h}_{v},b)}{\partial
b}\right|_{b=y}.|h_{t_{i}}-\widehat{h}_{t_{i}}|$
$\displaystyle=\left|\frac{\widehat{h}_{v}}{(2y+\widehat{h}_{v})^{2}}\right|.|h_{t_{i}}-\widehat{h}_{t_{i}}|$

Since $|\widehat{h}_{t_{i}}-h_{t_{i}}|\leq\theta(\sqrt{\frac{\log n}{n}})$ and
$h_{t_{i}}\geq\tau\frac{\log n}{\sqrt{n}}$, we know that
$2\widehat{h}_{t_{i}}\geq h_{t_{i}}\geq\widehat{h}_{t_{i}}/2$. We also know
that $\widehat{h}_{v}\leq\widehat{h}_{t_{i}}$ by our assumption and hence
$\widehat{h}_{v}\leq 2h_{t_{i}}$ which would imply that $x\leq 2h_{t_{i}}$.
Thus, we have
$\frac{h_{t_{i}}}{(2h_{t_{i}}+x)^{2}}\geq\frac{h_{t_{i}}}{16h^{2}_{t_{i}}}=\frac{1}{16h_{t_{i}}}$
and $\frac{\widehat{h}_{v}}{(2y+\widehat{h}_{v})^{2}}\leq\frac{2}{h_{t_{i}}}$.
Note that using the triangle inequality
$|A_{i}|-|B_{i}|\geq||A_{i}|-|B_{i}||$. Thus, as long as $\tau$ is large
enough, we conclude that $|A_{i}|-|B_{i}|\geq\tau/20\frac{\log n}{\sqrt{n}}$.
Substituting this into inequality *, we get a contradiction, leading us to
conclude that $|h^{\prime}_{v}-h_{v}|\leq\Delta\frac{\log n}{\sqrt{n}}$.

The final part of the proof is for the case where there exists some $i$ such
that $\widehat{h}_{v}>\widehat{h}_{t_{i}}$. In this event, recall that our
algorithm uses the smallest such height $U=\min_{i}\\{\widehat{h}_{t_{i}}\\}$
as the final estimate $\widehat{h}_{v}^{f}$ for $h_{v}$. We show that
$|U-h_{v}|\leq\Delta\frac{\log n}{\sqrt{n}}$ with high probability. First, we
note that $U>h_{v}$.Assume that $|U-h_{v}|>\Delta\frac{\log n}{\sqrt{n}}$, for
sake of contradiction. We will show similar bounds on the expressions $A_{i}$
and $B_{i}$ from the above proof. First, we lower bound $|A_{i}|$. Consider
the (continuous) univariate function $f(a,h_{t_{i}})$ on the intervals
$[h_{v},U]$ and $[U,\widehat{h}_{v}]$. Using the intermediate value theorem on
both intervals, there exists $x_{1}\in[h_{v},U]$ and
$x_{2}\in[U,\widehat{h}_{v}]$ such that:

$\displaystyle A_{i}:=|f(h_{v},h_{t_{i}})-f(\widehat{h}_{v},h_{t_{i}})|$
$\displaystyle=\left|\frac{\partial f(a,h_{t_{i}})}{\partial
a}\right|_{a=x_{1}}.|U-h_{v}|+\left|\frac{\partial f(a,h_{t_{i}})}{\partial
a}\right|_{a=x_{2}}.|\widehat{h}_{v}-U|$
$\displaystyle\geq\left|\frac{\partial f(a,h_{t_{i}})}{\partial
a}\right|_{a=x_{1}}.|U-h_{v}|$
$\displaystyle=\left|\frac{h_{t_{i}}}{(2h_{t_{i}}+x_{1})^{2}}\right|.|U-h_{v}|$

Thus, with similar reasoning as before, we have
$\frac{h_{t_{i}}}{(2h_{t_{i}}+x_{1})^{2}}\geq\frac{h_{t_{i}}}{16h^{2}_{t_{i}}}=\frac{1}{16h_{t_{i}}}$
since $x_{1}\leq\widehat{h}_{t_{i}}$ for all $i$.

Now, to upper bound $B_{i}$, we consider the (continuous) univariate function
$f(\widehat{h}_{v},b)$ on the interval $[h_{t_{i}},\widehat{h}_{t_{i}}]$, we
know there exists $y\in[h_{t_{i}},\widehat{h}_{t_{i}}]$ such that:

$\displaystyle
B_{i}:=|f(\widehat{h}_{v},h_{t_{i}})-f(\widehat{h}_{v},\widehat{h}_{t_{i}})|$
$\displaystyle=\left|\frac{\partial f(\widehat{h}_{v},b)}{\partial
b}\right|_{b=y}.|h_{t_{i}}-\widehat{h}_{t_{i}}|$
$\displaystyle=\left|\frac{\widehat{h}_{v}}{(2y+\widehat{h}_{v})^{2}}\right|.|h_{t_{i}}-\widehat{h}_{t_{i}}|$

Consider the univariate function $g(x)=\frac{x}{(2c+x)^{2}}$. Note that
$g(x)>0$ if $c,x>0$. Thus, $|g(x)|$ (for $c,x>0$) is maximized at the same
point as $g(x)$ which is at $x=2c$. Thus,
$\frac{\widehat{h}_{v}}{(2y+\widehat{h}_{v})^{2}}\leq\frac{2y}{16y^{2}}=\frac{1}{8y}\leq\frac{1}{4h_{t_{i}}}$.
Similar analysis as before leads us to a contradiction ( we can show that
$|A_{i}|\geq 2|B_{i}|$, which suffices to prove the result).

∎

##  Appendix C Proof of Theorem 3 (Lower Bound on Edge Weights)

Let us assign an arbitrary ordering on the set of all possible triples of
leaves $(r,s,t)$ from $1$ to $k$ where $k=\binom{n}{3}$. Let
$\mathbf{Q}_{j}^{(1)}$ (resp. $\mathbf{Q}_{j}^{(2)}$) denote the random
variable corresponding to the response on the $j^{th}$ query (i.e., triple)
from tree $T_{1}$ (resp. $T_{2}$). Let $\mathbf{Q}^{(1)}$ (resp.
$\mathbf{Q}^{(2)}$) denote the $\binom{n}{3}$-dimensional random variable
whose $j^{th}$ coordinate is $\mathbf{Q}_{j}^{(1)}$ (resp.
$\mathbf{Q}_{j}^{(2)}$). Both $\mathbf{Q}^{(1)}$ and $\mathbf{Q}^{(2)}$ follow
product distributions. To prove our theorem, it suffices to prove the
following

$\Delta(\mathbf{Q}^{(1)},\mathbf{Q}^{(2)})\leq 0.01.$

Here $\Delta(\cdot,\cdot)$ refers to the total variation distance. The above
inequality follows from Lemma 10 which we prove next.

######  Lemma 10.

For $\mathbf{Q}^{(1)}$ and $\mathbf{Q}^{(2)}$ as described above,
$\Delta(\mathbf{Q}^{(1)},\mathbf{Q}^{(2)})\leq 0.01$.

###### Proof.

We start by partitioning the set $[k]$ into five different sets defined below:

  1. 1.

Let $L^{\prime}=L\setminus\\{a,b,c\\}$. Define $\mathcal{A}_{1}\subseteq[k]$
to be the set of those indices which correspond to triples $(r,s,t)$ such that
$|\\{r,s,t\\}\cap L^{\prime}|\geq 2$.

  2. 2.

Define $\mathcal{A}_{2}\subseteq[k]$ to be the set of those indices which
correspond to triples $(r,b,c)$ where $r\in L^{\prime}$.

  3. 3.

Let $j^{\ast}$ be the index which corresponds to the triple $(a,b,c)$. Let
$\mathcal{A}_{3}=\\{j^{\ast}\\}$.

  4. 4.

Let $\mathcal{A}_{4}$ be the set of those indices which correspond to the
triples of the form $(a,b,x)$ for $x\in L^{\prime}$.

  5. 5.

Let $\mathcal{A}_{5}$ be the set of those indices which correspond to the
triples of the form $(a,c,x)$ for $x\in L^{\prime}$.

In order to analyze $\Delta(\mathbf{Q}^{(1)},\mathbf{Q}^{(2)})$, it is more
convenient to look at the notion of Hellinger distance (see Definition 3). We
start with the following easy claims.

######  Claim 7.

Let $j\in\mathcal{A}_{1}$. Then the random variables $\mathbf{Q}_{j}^{(1)}$
and $\mathbf{Q}_{j}^{(2)}$ are identical. Thus,
$H^{2}(\mathbf{Q}_{j}^{(1)},\mathbf{Q}_{j}^{(2)})=0$.

###### Proof.

Let $j$ correspond to the triple $(r,s,t)$. Note that the random variables
$\mathbf{Q}_{j}^{(1)}$ and $\mathbf{Q}_{j}^{(2)}$ are just dependent on the
pairwise distances between the leaves $r$, $s$ and $t$. It is easy to observe
that as long as two of these leaves are in $L^{\prime}$, their pairwise
distances are same both in trees $T_{1}$ and $T_{2}$. This proves the claim. ∎

######  Claim 8.

Let $j\in\mathcal{A}_{2}$. Then the random variables $\mathbf{Q}_{j}^{(1)}$
and $\mathbf{Q}_{j}^{(2)}$ are identical. Thus,
$H^{2}(\mathbf{Q}_{j}^{(1)},\mathbf{Q}_{j}^{(2)})=0$.

###### Proof.

Let $j$ correspond to the triple $(r,c,b)$. As in Claim 7, the pairwise
distances between the vertices $r$, $c$ and $b$ are the same in both $T_{1}$
and $T_{2}$. The claim now follows. ∎

Using Claim 8 and Claim 7, it follows tha ∎

######  Claim 9.

Let $\mathcal{A}_{3}=\\{j^{\ast}\\}$. Then,
$H^{2}(\mathbf{Q}_{j^{\ast}}^{(1)},\mathbf{Q}_{j^{\ast}}^{(2)})\leq\frac{4\rho^{2}}{n}$.

###### Proof.

Observe that both random variables $\mathbf{Q}_{j^{\ast}}^{(1)}$ and
$\mathbf{Q}_{j^{\ast}}^{(2)}$ are supported on the set
$\\{(a,b),(b,c),(a,c)\\}$. Let
$p_{1}:=\Pr[\mathbf{Q}_{j^{\ast}}^{(1)}=(a,b)]$,
$p_{2}:=\Pr[\mathbf{Q}_{j^{\ast}}^{(1)}=(b,c)]$ and
$p_{3}:=\Pr[\mathbf{Q}_{j^{\ast}}^{(1)}=(a,c)]$. Similarly, let
$q_{1}:=\Pr[\mathbf{Q}_{j^{\ast}}^{(2)}=(a,b)]$,
$q_{2}:=\Pr[\mathbf{Q}_{j^{\ast}}^{(2)}=(b,c)]$ and
$q_{3}:=\Pr[\mathbf{Q}_{j^{\ast}}^{(2)}=(a,c)]$.

Let $d_{1}(\cdot,\cdot)$ be the distance metric on tree $T_{1}$ and
$d_{2}(\cdot,\cdot)$ be the distance metric on tree $T_{2}$. Now, define
$\alpha:=d_{1}(a,b)=d_{2}(a,c)$ and
$\beta:=d_{1}(a,c)=d_{1}(b,c)=d_{2}(a,b)=d_{2}(b,c)$.

Observe that $\alpha\geq\frac{2}{3}$ since
$d_{1}(a,p)=d_{2}(a,p)=\frac{1}{3}$. Also,
$\beta-\alpha=\frac{2\rho}{\sqrt{n}}$.

$H^{2}(\mathbf{Q}_{j^{\ast}}^{(1)},\mathbf{Q}_{j^{\ast}}^{(2)})=\frac{1}{2}((\sqrt{p_{1}}-\sqrt{q_{1}})^{2}+(\sqrt{p_{2}}-\sqrt{q_{2}})^{2}+(\sqrt{p_{3}}-\sqrt{q_{3}})^{2})$

.

We rewrite the probabilities in terms of the distances $\alpha$ and $\beta$:

$p_{1}=q_{3}=\frac{2\beta}{2(\alpha+2\beta)};\
p_{2}=p_{3}=q_{1}=q_{2}=\frac{\alpha+\beta}{2(\alpha+2\beta)}$

Next, we upper bound the quantity: $\sqrt{p_{1}}-\sqrt{q_{1}}$.

$\displaystyle\sqrt{p_{1}}-\sqrt{q_{1}}$
$\displaystyle=\sqrt{\frac{2\beta}{2(\alpha+2\beta)}}-\sqrt{\frac{\alpha+\beta}{2(\alpha+2\beta)}}$
$\displaystyle=\frac{\sqrt{2\beta}-\sqrt{\alpha+\beta}}{\sqrt{2(\alpha+2\beta)}}$
$\displaystyle\leq\sqrt{\frac{4}{3}}(\sqrt{2\beta}-\sqrt{\alpha+\beta})\qquad\text{(
since $\alpha\geq\frac{2}{3}$)}$
$\displaystyle=\sqrt{\frac{4}{3}}\frac{\beta-\alpha}{(\sqrt{2\beta}+\sqrt{\alpha+\beta})}\qquad\text{(
multiplying and dividing by $(\sqrt{2\beta}+\sqrt{\alpha+\beta})$)}$
$\displaystyle\leq\frac{2\rho}{\sqrt{n}}\qquad\text{( since
$\alpha\geq\frac{2}{3}$)}$

We know $p_{2}=q_{2}$. The final term of interest is
$|\sqrt{p_{3}}-\sqrt{q_{3}}|$. Since $p_{1}=q_{3}$ and $p_{3}=q_{1}$, we get
the upper bound - $|\sqrt{p_{3}}-\sqrt{q_{3}}|\leq\frac{2\rho}{\sqrt{n}}$.

Putting together these inequalities, we get
$H^{2}(\mathbf{Q}_{j^{\ast}}^{(1)},\mathbf{Q}_{j^{\ast}}^{(2)})\leq\frac{1}{2}(\frac{8\rho^{2}}{n})$.
∎

######  Claim 10.

Let $j\in\mathcal{A}_{4}$. Then,
$H^{2}(\mathbf{Q}_{j}^{(1)},\mathbf{Q}_{j}^{(2)})\leq\frac{\rho^{2}}{4n}$.

###### Proof.

Let $j$ correspond to the triple $(a,b,x)$. The support space of both
$\mathbf{Q}_{j}^{(1)}$ and $\mathbf{Q}_{j}^{(2)}$ is
$\\{(a,b),(b,x),(a,x)\\}$. Let $p_{1}:=\Pr[\mathbf{Q}_{j}^{(1)}=(a,b)]$,
$p_{2}:=\Pr[\mathbf{Q}_{j}^{(1)}=(b,x)]$ and
$p_{3}:=\Pr[\mathbf{Q}_{j}^{(1)}=(a,x)]$. Similarly, let
$q_{1}:=\Pr[\mathbf{Q}_{j}^{(2)}=(a,b)]$,
$q_{2}:=\Pr[\mathbf{Q}_{j}^{(2)}=(b,x)]$ and
$q_{3}:=\Pr[\mathbf{Q}_{j}^{(2)}=(a,x)]$.

As in Claim 9, let $d_{1}(\cdot,\cdot)$ be the distance metric on tree $T_{1}$
and $d_{2}(\cdot,\cdot)$ be the distance metric on $T_{2}$. Let
$\alpha:=d_{1}(a,b)$ and $\beta:=d_{2}(a,b)$. We have
$d_{1}(a,x)=d_{1}(b,x)=d_{2}(a,x)=d_{2}(b,x)=2$, since the associated unique
path goes through the root for each of these pairs. Finally,
$\beta-\alpha=\frac{2\rho}{\sqrt{n}}$. Using the definition of Hellinger
distance, we have :

$H^{2}(\mathbf{Q}_{j}^{(1)},\mathbf{Q}_{j}^{(2)})=\frac{1}{2}((\sqrt{p_{1}}-\sqrt{q_{1}})^{2}+(\sqrt{p_{2}}-\sqrt{q_{2}})^{2}+(\sqrt{p_{3}}-\sqrt{q_{3}})^{2})$

. Thus, we have,

$p_{1}=\frac{4}{2(4+\alpha)};\ q_{1}=\frac{4}{2(4+\beta)};\
p_{2}=p_{3}=\frac{2+\alpha}{2(4+\alpha)};\
q_{2}=q_{3}=\frac{2+\beta}{2(4+\beta)}$

Next, we upper bound the quantity $\sqrt{p_{1}}-\sqrt{q_{1}}$ as follows:

$\displaystyle\sqrt{p_{1}}-\sqrt{q_{1}}$
$\displaystyle=\sqrt{2}\left(\frac{\sqrt{4+\beta}-\sqrt{4+\alpha}}{\sqrt{(4+\alpha)(4+\beta)}}\right)$
$\displaystyle\leq\frac{1}{2\sqrt{2}}(\sqrt{4+\beta}-\sqrt{4+\alpha})$
$\displaystyle\leq\frac{1}{2\sqrt{2}(\sqrt{4+\beta}+\sqrt{4+\alpha})}(\beta-\alpha)$
$\displaystyle\leq\frac{1}{4\sqrt{2}}\frac{\rho}{\sqrt{n}}$ (4)

Next, we upper bound $\sqrt{q_{2}}-\sqrt{p_{2}}$ as follows:

$\displaystyle\sqrt{q_{2}}-\sqrt{p_{2}}$
$\displaystyle=\frac{1}{\sqrt{2}}\frac{\sqrt{(2+\beta)(4+\alpha)}-\sqrt{(4+\beta)(2+\alpha)}}{\sqrt{(4+\alpha)(4+\beta)}}$
$\displaystyle\leq\frac{1}{4\sqrt{2}}(\sqrt{8+\alpha\beta+4\beta+2\alpha}-\sqrt{8+\alpha\beta+2\beta+4\alpha})$
$\displaystyle=\frac{1}{4\sqrt{2}(\sqrt{8+\alpha\beta+4\beta+2\alpha}+\sqrt{8+\alpha\beta+2\beta+4\alpha})}(2\beta-2\alpha)$
$\displaystyle\leq\frac{1}{8\sqrt{2}}\frac{\rho}{\sqrt{n}}$ (5)

By an identical analysis, we have
$\sqrt{q_{3}}-\sqrt{p_{3}}\leq\frac{1}{8\sqrt{2}}\frac{\rho}{\sqrt{n}}$.
Combining this with (4) and (5) gives us the claim. ∎

Using an analysis identical to Claim 10, we also get the following Claim.

######  Claim 11.

Let $j\in\mathcal{A}_{5}$. Then,
$H^{2}(\mathbf{Q}_{j}^{(1)},\mathbf{Q}_{j}^{(2)})\leq\frac{\rho^{2}}{4n}$.

Putting together these claims, we can use Lemma 12 to show that
$H(\mathbf{Q}^{(1)},\mathbf{Q}^{(2)})\leq\frac{0.01}{\sqrt{2}}$, and then use
Lemma 11 to conclude that $\Delta(\mathbf{Q}^{(1)},\mathbf{Q}^{(2)})\leq
0.01$.

##  Appendix D Concentration Bounds and Measures of Statistical Distance

We list here some standard concentration results, that will be used to
aggregate the results of stochastically independent queries

######  Theorem 4 (Generalized Hoeffding Bound).

Let $\mathbf{y}_{1},\mathbf{y}_{2},..,\mathbf{y}_{k}$ be $k$ independent
random variables, with each variable $\mathbf{y}_{i}$ having range
$[a_{i},b_{i}]$ and mean $y_{i}$ then:

$\Pr\big{[}\big{|}\sum_{i=1}^{k}y_{i}-\sum_{i=1}^{k}\mathbf{y}_{i}\big{|}\leq
t\big{]}\ \geq\ 1-e^{\frac{2t^{2}}{\sum_{i}(b_{i}-a_{i})^{2}}}$

We state below a special case of the generalized Hoeffding bound that we use
repeatedly in proofs, referring to it as the Hoeffding bound.

######  Theorem 5 (Hoeffding Bound).

Let $\mathbf{y}_{1},\mathbf{y}_{2},..,\mathbf{y}_{k}$ be $k$ iid random
variables between $0$ and $1$, each with mean $y$, then:

$\Pr\big{[}\big{|}y-\frac{\sum_{i=1}^{k}\mathbf{y}_{i}}{k}\big{|}\leq
4\sqrt{\frac{\log n}{k}}\big{]}\ \geq\ 1-\frac{1}{n^{6}}$

We also list some measures of statistical distance and connections between
them, that will be employed in our lower bounds proofs. We formally define
total variation distance and Hellinger distance for discrete distributions.

######  Definition 2 (Total Variation Distance).

Let $X$ and $Y$ be discrete distributions, having weight $p_{x_{i}}$ and
$p_{y_{j}}$ respectively on points $z_{1}$, $z_{2}\cdots$. Then, the total
variation distance between $X$ and $Y$, denoted by $\Delta(X,Y)$ is defined
as:

$\Delta(X,Y):=\frac{1}{2}\sum_{i=1}^{\infty}|p_{x_{i}}-p_{y_{i}}|$

An alternative, equivalent definition is as follows: Let the sample space of
the two distributions $X,Y$ be $\Omega$, then:

$\Delta(X,Y)=\sup_{A\in\Omega}|X(A)-Y(A)|$.

######  Definition 3 (Hellinger Distance).

Let $X$ and $Y$ be discrete distributions, having weight
$p_{x_{1}},p_{x_{2}},\cdots$ and $p_{y_{1}},p_{y_{2}},\cdots$ respectively on
points $z_{1}$, $z_{2}\cdots$. Then, the total variation distance between $X$
and $Y$, denoted by $H(X,Y)$ is defined as:

$H(X,Y):=\frac{1}{\sqrt{2}}\sqrt{\sum_{i=1}^{\infty}(\sqrt{p_{x_{i}}}-\sqrt{p_{y_{i}}})^{2}}$

We use the following two useful lemmas about Total Variation Distance
Hellinger Distance from Barak et. al. [7].

######  Lemma 11 ([36]).

For two distributions $X$ and $Y$:

$H^{2}(X,Y)\leq\Delta(X,Y)\leq\sqrt{2}H(X,Y)$

######  Lemma 12 ([7]).

Let $X_{1},X_{2}\cdots X_{n}$ and $Y_{1},Y_{2}\cdots Y_{n}$ be two families of
distributions. Then,

$H(X_{1}\oplus X_{2}\oplus\cdots X_{n},Y_{1}\oplus Y_{2}\oplus\cdots
Y_{n})\leq\sum_{i=1}^{n}H^{2}(X_{i},Y_{i})$

where $X\oplus Y$ denotes the product of two distributions $X$ and $Y$,
generated by taking independent samples of $X$ and $Y$.

##  Appendix E Figures

Figure 2: Sibling-Tree Pair between Non Sibling-Tree Pair

Figure 3: Lower Bound Instance Tree $T_{1}$
Figure 4: Lower Bound Instance Tree 2