We present a distribution on $(k,\varphi,\epsilon)$-clusterable instances with
small Dasgupta cost and another distribution on
$(k,\varphi,\epsilon)$-clusterable instances with large Dasgupta Cost. We show
that any algorithm which makes very few queries is unlikely to distinguish
reliably between the graphs sampled from these distributions. Towards defining
these distributions, we begin with some setup.

######  Definition 16.

Fix $n\in\mathbb{N}$ an even $d\geq 4$ and $0<\delta<1/100d$. The
configuration model parameterized by $n,\delta,d$ generates a random $d$
regular graph $G=(V,E)$ with $n$ vertices as follows. It first generates $d$
half edges on each vertex. These edges are generated in two rounds.

  1. 1.

In round 1, we generate $d-1$ half edges on each vertex. We connect all these
half edges by a random perfect matching and this finishes round 1.

  2. 2.

In round 2, we generate the last half edge on each vertex. Each half edge in
this round is marked red with probability $\delta d$. Again, we connect all
half edges generated in this round by a random perfect matching.

An edge formed in round 2 by pairing one red half edge with any other edge is
called a red edge. Let $G$ denote the final graph obtained. $G$ might have
self loops and parallel edges and is not necessarily simple. Note that our
definition of the configuration model departs from the standard definition in
the literature because of these special red edges.

######  Remark 3.

Note that our config model allows self loops and parallel edges. Despite this,
one can verify that the guarantees of our algorithm in the RandomSampleModel
(from Theorem 3) continue to hold.

We state now the following fact which claims that a random $d$-regular graph
is likely to be an expander.

######  Fact 2.

For $d\geq 3$, let $\varphi=\varphi(d)\in(0,1)$ be such that
$(2\varphi)\log_{2}(2\varphi)+(2-2\varphi)\log_{2}(2-2\varphi)>4/d$. Then with
probability at least $1-\left(\frac{1}{n}\right)^{d/3}$, a random $d$-regular
graph generated according to the configuration model has expansion at least
$\varphi$.

We now define our distributions over low and high Dasgupta cost instances
(which we denote as $D_{1}=D_{1}(n,d,\delta,k)$ and $D_{2}(n,d,\delta,k)$
respectively). Let $H_{1}=([k],E_{1})$ be a copy of the cycle on $k$ vertices
and $H_{2}=([k],E_{2})$ denote a $4$-regular expander with
$\phi(H_{2})\geq\Omega(1)$. For $v\in[k]$, let $N_{b}(v)$ denote the
neighborhood of $v$ in $H_{b}$ (for $b\in\\{1,2\\}$). We now describe in words
how we generate samples from the distribution $D_{1}$ (or $D_{2}$). Fix
$b\in{1,2}$. We will generate a $(k,\varphi,\epsilon)$-clusterable $d$-regular
graph $G\sim D_{b}$ as follows. First, we generate the $k$ clusters each with
size $n/k$ by sampling each cluster from the config model. Then, we ensure
that the contraction of a graph sampled from $D_{b}$ with respect to the
$k$-clustering $\mathcal{C}=(C_{1},C_{2},\ldots,C_{k})$ as follows. Note that
$H_{b}$ is a $2b$-regular graph. To enforce that the contractions of $G$ are
indeed consistent with $H_{b}$, for $(i,j)\in E(H_{b})$, we add
$\Theta(\epsilon dn/k)$ edges between $C_{i}$ and $C_{j}$ while preserving
$d$-regularity. This is done by taking a red edge $e=(a,b)$ with both
endpoints in $C_{i}$ and another red edge $f=(c,d)$ in $C_{j}$, deleting them
both and adding the edges $e^{\prime}=(a,c)$ and $f^{\prime}=(b,d)$ instead.
An edge in $C_{i}$ is red with probability $\Theta(\delta)$ and so the number
of red edges in $\Theta(\delta nd/k)$ with good probability. Our algorithm
ensures there are $\Theta(\delta nd/2bk)$ edges between $C_{i}$ and $C_{j}$
(whenever $(i,j)\in E(H_{b})$). Now, we present our algorithms which produce a
random instance from distributions $D_{1}$ and $D_{2}$.

Algorithm 7 $\textsc{SampleFromD1}(n,d,\delta,k)$

1: $b\leftarrow 1$

2: $deg\leftarrow 2$

3: $G\leftarrow\textsc{GenerateSample}(n,d,\delta,k,b,deg)$

4: return $G$.

Algorithm 8 $\textsc{SampleFromD2}(n,d,\delta,k)$

1: $b\leftarrow 2$

2: $deg\leftarrow 4$

3: $G\leftarrow\textsc{GenerateSample}(n,d,\delta,k,b,deg)$

4: return $G$.

Algorithm 9 $\textsc{GenerateSample}(n,d,\delta,k,b,deg)$
# ($b=1$ indicates $D_{1}$, $b=2$ indicates $D_{2}$)

1: $C_{1},C_{2},\ldots C_{k}\sim\textsc{ConfigModel}(n/k,d,6\delta)$.

2: if any $C_{i}$ contains fewer than $4\delta dn$ red edges then

3: return $\bot$.

4: end if

5: for $i=1\text{ to }k$ do

6: repeat $\frac{\delta dn}{deg\cdot k}$ times

7: # (Under $D_{1}$, $deg=2$ with $\delta dn/2k$ edges b/w adjacent clusters)

8: # (Under $D_{2}$, $deg=4$ with $\delta dn/4k$ edges b/w adjancent clusters)

9: for $j\in N_{b}(i),j>i$ do

10: Pick a random red edge in $e\in C_{i}$ and a random red edge $f\in C_{j}$.

11: Uncolor $e,f$

12: $\textsc{CrossEdges}(e,f)$.

13: end for

14: end for

15: Uncolor all red edges.

16: Pick $\sigma\in S_{n}$ and randomly permute $V$.

17: return $G$.

Algorithm 10 $\textsc{CrossEdges}(e,f)$

1: Let $e=(a,b),f=(c,d)$.

2: Replace $e,f$ with $e^{\prime}=(a,c)$ and $f^{\prime}=(b,d)$.

Note that the graphs sampled from $D_{1}$ (resp $D_{2}$) consist of $k$
clusters sampled from the configuration model. Graphs sampled from $D_{b}$
(for $b\in\\{1,2\\}$) are obtained in the following two steps. First, line 1
of Algorithm 9 replaces $i\in V(H_{b})$ by the cluster $C_{i}$. Next, for
$(i,j)\in E(H_{b})$ we have $\Theta(\delta dn/k)$ edges running between
$C_{i}$ and $C_{j}$ according to line 5 in Algorihtm 9 (with high
probability). In particular, this means that in graphs sampled from $D_{1}$,
the $k$ clusters sampled from the configuration model are arranged in a cycle
of size $k$ where every pair of successive clusters have $\Theta(\delta dn/k)$
edges running between them. On the other hand, in graphs sampled from $D_{2}$
these clusters are arranged according to the graph $H_{2}$ and corresponding
to two adjacent vertices in $H_{2}$, we have two connected clusters with
$\Theta(\delta dn/k)$ edges between them with high probability.

Having defined the distributions $D_{1}$ and $D_{2}$, we now state the main
lemma we prove in this section. Once properties of the distributions $D_{1}$
and $D_{2}$ are developed, Lemma 17 follows as an immediate corollary from
this lemma. We consider deterministic algorithms which make a total of $Q$
queries among which some $s\leq Q$ initial queries are cluster queries (and
ask for the identity of the cluster to which a vertex sampled uniformly at
random belongs). These $s$ vertices, whose clusters are revealed by the
clustering oracle, are called _tagged_.

######  Lemma 18.

Fix $d\geq 8,k\in\mathbb{N}$. Then there exists $\varphi=\varphi(d)$ such that
for all $\epsilon\ll\varphi^{2}$ such that any deterministic $Q$-query
algorithm $A$ which distinguishes between graphs drawn from
$D_{1}(n,d,\epsilon,k)$ and $D_{2}(n,d,\epsilon,k)$ with probability at least
$2/3$ requires at least $\Omega(\frac{1}{d}\cdot\sqrt{\frac{n}{k}})$ queries
in RandomSampleModel.

We first show that the procedures SampleFromD1 and SampleFromD2 produce graphs
which are $(k,\varphi,\epsilon)$-clusterable with good probability:

######  Claim 2.

Let $d\geq 8,k\in\mathbb{N}$. Then there exists
$\varphi^{\prime}=\varphi(d),\varphi=\varphi(d-1)$ such that for all
$\epsilon\ll\varphi^{2}$ such that the clusters $C_{1},C_{2},\ldots C_{k}$
obtained in Line 1 of Algorithm 9 on calling
$\textsc{SampleFromD1}(n,d,\epsilon,k)$ (resp
$\textsc{SampleFromD2}(n,d,\epsilon,k)$) satisfy the following with
probability at least $1-3k\cdot\left(\frac{2}{n}\right)^{d/3}$:

  * •

Each $C_{i}$ induces a $\varphi^{\prime}$ expander.

  * •

For every $i\in[k]$, the number of red half edges in each $C_{i}$ is between
$4\epsilon dn/k$ and $8\epsilon dn/k$ (and thus $G\neq\bot$).

Moreover, conditioned on this event, $G$ is
$(k,\varphi/2,\epsilon)$-clusterable.

###### Proof.

Let $\varphi=\varphi(d-1),\varphi^{\prime}=\varphi^{\prime}(d)$ be the lower
bounds on inner conductance of a graph sampled according to the configuration
model (as stated in Fact 2). Now, fix any $\epsilon\ll\varphi^{2}$. By Fact 2,
for all $i\in[k]$, $C_{i}\sim\textsc{ConfigModel}(n/k,d,6\epsilon)$, it
follows that each $C_{i}$ induces a graph with
$\phi(C_{i})\geq\varphi^{\prime}$ with probability at least
$1-\left(\frac{1}{n}\right)^{d/3}$. By a union bound over all the $k$
clusters, all $C_{i}$’s induce a graph with $\phi(C_{i})\geq\varphi^{\prime}$
with probability at least $1-k\cdot\left(\frac{1}{n}\right)^{d/3}$. Next, note
that Algorithm 9 returns $\bot$ only when some cluster $C_{i}$ contains very
few red half edges. Fix some $i\in[k]$. Thus, in expectation each $C_{i}$
contains $6\epsilon dn/k$ red half edges. Call a cluster $C_{i}$ bad if it
contains fewer than $4\epsilon dn/k$ or more than $8\epsilon dn/k$ red half
edges. By a Chernoff bound, for a fixed $i\in[k]$, $C_{i}$ is bad with
probability at most $2\exp(-\epsilon dn/3k)$. By a union bound over all the
$k$ clusters, the probability that any cluster is bad is at most
$2k\cdot\exp(-\epsilon dn/3k)$. Thus, both the above events occur with
probability at least

$1-k\cdot\left(\frac{1}{n}\right)^{d/3}-2k\cdot\exp(-\epsilon dn/3k)\geq
1-3k\cdot\left(\frac{1}{n}\right)^{d/3}.$

Note that conditioned on this event, for each $i\in[k]$, Algorithm 9 each
$C_{i}$ has $\epsilon dn/k$ edges leaving it. This means for every $i\in[k]$,
$\phi^{G}_{\text{out}}(C_{i})\leq\epsilon$. We now lower bound
$\phi^{G}_{\text{in}}(C_{i})$. To this end, consider the graph $G_{2}$
obtained as follows: for every $i\in[k]$, replace all the half edges that
arrived in the second round of the ConfigModel (Definition 16) by self loops.
Observe that

$\forall
i\in[k],\phi^{G_{2}}_{\text{in}}(C_{i})\leq\phi^{G}_{\text{in}}(C_{i}).$

Thus, it suffices to lower bound $\phi^{G_{2}}_{\text{in}}(C_{i})$. To this
end, we first consider the graph $G_{1}$ which is formed after round 1. In
$G_{1}$ each $C_{i}$ is distributed according to
$\textsc{ConfigModel}(n/k,d-1,0)$. This means, in $G_{1}$ each $C_{i}$ induces
a graph with expansion at least $\varphi^{\prime}$. For any $i\in[k]$, and for
any $S\subseteq C_{i}$, note that

$\phi^{G_{2}}_{C_{i}}(S)\geq\frac{E_{1}(S,\overline{(}S))}{d|S|}\geq\frac{\varphi\cdot(d-1)|S|}{d|S|}.$

This is at least $\varphi/2$ for $d\geq 8$. Thus, for any $i\in[k]$, we indeed
have $\phi^{G_{2}}_{\text{in}}(C_{i})\geq\varphi/2$. This means the final
graph $G$ obtained in Line 17 of Algorithm 9 is
$(k,\varphi/2,\epsilon)$-clusterable as desired. ∎

We first show that, with high probability, graphs sampled from $D_{1}$ have
small Dasgupta Cost.

######  Lemma 19.

Fix $d\geq 8,k\in\mathbb{N}$. Then there exists $\varphi=\varphi(d)$ such that
for all $\epsilon\ll\varphi^{2}$ such that a graph $G=(V,E)$ obtained by
calling $\textsc{GenerateSampleD1}(\epsilon)$ is
$(k,\varphi,\epsilon)$-clusterable and $\text{COST}_{G}(T^{*}_{G})\leq
O\left(\max\left(\frac{\epsilon\cdot dn^{2}\cdot\log
k}{k},\frac{dn^{2}}{k}\right)\right)$ with probability at least
$1-3k\cdot\left(\frac{1}{n}\right)^{d/3}$.

###### Proof.

Use Fact 2 and set $\varphi=\varphi(d)$ accordingly. Take any
$\epsilon\ll\varphi^{2}$. With probability at least
$1-3k\cdot\left(\frac{1}{n}\right)^{d/3}$, the graph $G$ obtained by
$\textsc{SampleFromD1}(n,d,\epsilon,k)$ is $(k,\varphi,\epsilon)$-clusterable.
Recall that the contraction of $G$ with respect to $C_{1},C_{2},\ldots C_{k}$
is the graph $H_{1}$ which is a copy of cycle on $k$ vertices. Thus, for all
$i\in[k]$, there are $\epsilon dn/k$ edges between $C_{i}$ and $C_{i+1}$ where
indices are taken modulo $k$. Let $T^{*}$ denote a tree with optimal Dasgupta
cost on $G$. In what follows, we now describe a cluster respecting tree
(Definition 15) $T$ on $G$. We denote the corresponding contracted subtree
(Definition 15) of $T$ as $T^{\prime}$. We note

$\text{COST}_{G}(T^{*})\leq\text{WCOST}_{G}(T^{\prime})+\sum
d|C_{i}|^{2}=\text{WCOST}_{G}(T^{\prime})+d\cdot(n/k)^{2}\cdot k,$ (53)

where the second term is a trivial upper bound on the sum of Dasgupta costs of
the clusters, and $\text{WCOST}_{G}(T^{\prime})$ refers to the weighted
Dasgupta Cost of $T^{\prime}$ on $G$ (Definition 10). We now describe how to
generate the tree $T^{\prime}$. The root cut separates $C_{1}\cup
C_{2}\cup\ldots C_{k/2}$ from the remaining vertices, which is achieved by
deleting $2\epsilon dn/k$ edges and thus this cut contributes a total of
$2\epsilon\frac{dn^{2}}{k}$ to $\text{WCOST}_{G}(T^{\prime})$. Subsequent
levels in the tree are obtained by recursively splitting these nodes into two
balanced sets. In particular, there are $2^{i}$ nodes in the tree at the
$i$-th level where each node $j\in[2^{i}]$ contains clusters $C_{(j-1)\cdot
2^{i}+1},\cdots,C_{j\cdot 2^{i}}$. Thus, the contribution to Dasgupta Cost
from this level is $\epsilon\frac{dn}{k}\cdot\frac{n}{2^{i}}\cdot
2^{i}=\epsilon\frac{dn^{2}}{k}$. This means

$\text{WCOST}_{G}(T^{\prime})\leq 2\frac{\epsilon dn^{2}}{k}+\frac{\epsilon
dn^{2}}{k}\log k\leq\frac{2\epsilon dn^{2}\log k}{k}.$

Together with Equation (53), this gives
$\text{COST}_{G}(T^{*})\leq\text{COST}_{G}(T)\leq
O\left(\max\left(\frac{\epsilon\cdot dn^{2}\cdot\log
k}{k},\frac{dn^{2}}{k}\right)\right)$. ∎

Next, we show that, with high probability, graphs sampled from $D_{2}$ have a
large Dasgupta Cost.

######  Lemma 20.

Fix $d\geq 8,k\in\mathbb{N}$. Then there exists $\varphi=\varphi(d)$ such that
for all $\epsilon\ll\varphi^{2}$ such that a graph $G=(V,E)$ obtained by
calling $\textsc{GenerateSampleD2}(\epsilon)$ is
$(k,\varphi,\epsilon)$-clusterable and
$\text{COST}_{G}(T^{*}_{G})\geq\Omega\left(\min(\epsilon\cdot
dn^{2},dn^{2}/k)\right)$ with probability at least
$1-3k\cdot\left(\frac{1}{n}\right)^{d/3}$.

###### Proof.

Use Fact 2 and set $\varphi=\varphi(d)$ accordingly. Take any
$\epsilon\ll\varphi^{2}$. With probability at least
$1-3k\left(\frac{1}{n}\right)^{d/3}$, the graph $G$ obtained by
$\textsc{SampleFromD2}(n,d,\epsilon,k)$ is $(k,\varphi,\epsilon)$-clusterable.
Recall that the contraction of $G$ with respect to $C_{1},C_{2},\ldots C_{k}$
is the graph $H_{2}$ which is a copy of some $4$-regular expander with
$\phi(H_{2})=\alpha\geq\Omega(1)$. Recall that according to Corollary 3, any
Dasgupta tree for $G$ (in particular a optimum Dasgupta tree) has cost at
least $\frac{\varphi}{20}\cdot
d\sum_{i\in[k]}|C_{i}|^{2}=\frac{\varphi}{20}\cdot dn^{2}/k$. Now, we show
that the cost of an optimum Dasgupta tree for $G$ is also at least
$\Omega(\epsilon dn^{2})$. Let $T$ denote a cluster respecting tree for $G$
which satisfies

$\text{COST}_{G}(T^{*})\geq\Omega(\varphi)\cdot\text{COST}_{G}(T)$

which we know exists as per Lemma 15. Also note that according to this lemma,
the contraction $T^{\prime}$ of this tree with respect to
$(C_{1},C_{2},\ldots,C_{k})$ is a binary tree with $k$ leaves (which
correspond to $V(H_{2})$). We show
$\text{COST}_{G}(T)\geq\Omega(\alpha\epsilon dn^{2})$ which in turn lower
bounds $\text{COST}_{G}(T^{*}_{G})$.

We do this by lower bounding $\text{COST}_{G}(T)$ by just the contribution to
this cost from some single cut induced by $T$ in $G$. Take some internal node
$x$ in the contraction $T^{\prime}$ of $T$ which corresponds to a set
$B_{x}\subseteq[k]$. Suppose the children of $x$ in $T^{\prime}$ are $y$ and
$z$. Then since $T$ is cluster respecting, it holds that $B_{y}\cup
B_{z}=B_{x}$ where $B_{x}$ contains the set of vertices of $H_{2}$ that are
leaves in $H_{2}$ descending from $x$ (and $B_{y}$ denotes the analogous set
of vertices in $H_{2}$ descending from $y$). Take a cut $(B,\overline{B})$
induced by the tree $T^{\prime}$ in the graph $H_{2}$. We denote the edges
crossing this cut as $E_{2}(B,\overline{B})$. We can lower bound
$\text{COST}_{G}(T)$ as

$\text{COST}_{G}(T)\geq|E_{2}(B,\overline{B})|\cdot\frac{\epsilon
dn}{4k}\cdot\min(|B|,|\overline{B}|)\cdot\frac{n}{k}.$ (54)

We now produce a good choice for $B$ which leads to the desired lower bound.
Since the contraction $T^{\prime}$ of $T$ is a binary tree, by Fact 1, there
exists an edge $(u,v)\in T^{\prime}$ which satisfies that on deleting the edge
$(u,v)$, the number of edges in the component of $T^{\prime}$ containing $u$
and the component containing $v$ is at most $2|V(T^{\prime})|/3$. Denote these
components as $T^{\prime}_{u}$ and $T^{\prime}_{v}$ and suppose
$|V(T^{\prime})|/3\leq|T^{\prime}_{u}|\leq|T^{\prime}_{v}|$. Thus,

$|T^{\prime}_{u}|\geq\frac{|V(T^{\prime})|}{3}\geq\frac{1}{3}\cdot\left(2|V(H_{2})|-1\right)\geq
0.6k.$

We let $B=T^{\prime}_{u}$. Since $T^{\prime}$ is a binary tree, we have
$|B|\geq 0.3k$. Now, take any edge $(x,y)\in E_{2}(B,\overline{B})$ and denote
the LCA of $(x,y)$ in $T^{\prime}$ by $w$. Note that the number of leaves in
$T^{\prime}$ which descend from $w$ is at least $|B|\geq 0.3k$. Now recall,
the leaves of $T^{\prime}$ are exactly the vertices of $H_{2}$. And since
$H_{2}$ is an $\alpha$-expander, we have

$|E_{2}(B,\overline{B})|\geq\alpha\cdot 4|B|.$

Substituting this in Equation (54), together with $|B|\geq 0.3k$, we get
$\text{COST}_{G}(T)\geq\frac{9}{25}\alpha\epsilon dn^{2}$ as desired. As noted
earlier, this gives

$\text{COST}_{G}(T^{*})\geq\Omega(\varphi)\cdot\text{COST}_{G}(T)\geq\Omega(\varphi\alpha\epsilon
dn^{2}).$

By Lemma 15, it holds that
$\text{COST}_{G}(T^{*})\geq\Omega(\varphi\cdot\alpha\cdot\epsilon dn^{2})$.
The claim follows by observing that As noted earlier, this gives

$\text{COST}_{G}(T^{*})\geq\Omega(\varphi)\cdot\text{COST}_{G}(T)\geq\Omega(\varphi\alpha\epsilon
dn^{2}).$

By Lemma 15, it holds that
$\text{COST}_{G}(T^{*})\geq\Omega(\varphi\cdot\alpha\cdot\epsilon dn^{2})$.
The claim follows by observing that $\alpha\geq\Omega(1)$ and
$\varphi\geq\Omega_{d}(1)$ (as noted in Fact 2). ∎

We now turn to the proof of Lemma 18. First, it will be convenient to
establish our lower bounds for the following augmented query model.

######  Definition 17.

(Augmented Query Model) When an algorithm issues an edge query $(v_{q},i_{q})$
requesting the $i_{q}$-th edge incident on $v_{q}$ it gets at unit cost access
to all the $d$ neighbors of $v_{q}$.

Take any $Q$-query determenistic algorithm $A$. Suppose it gets $s\leq Q$
tagged vertices at the beginning of its execution. One can express its
behavior as follows. At any stage, it has explored the adjacency of $q\leq Q$
vertices, $v_{1},v_{2},\ldots v_{q}$. It can choose to further explore the
adjacency list of some of the revealed (but unqueried) vertex $v^{\prime}$.
Note that $v^{\prime}$ is an arbitrary (but fixed) function of all the
vertices and edges seen so far. Thus, the output returned by $A$ (whether
$G\sim D_{1}$ or $G\sim D_{2}$) depends only on the adjacencies of
$v_{1},v_{2},\ldots v_{Q}$. We refer to the subgraph of $G$ explored by a
$Q$-query algorithm $A$ as the _transcript_ of $A$ on $G$ and this is denoted
as $\text{TRANSCRIPT}_{Q}(A,G)$. We define the following two distributions.

######  Definition 18.

(Distribution over transcripts under $D_{1}$ and $D_{2}$) Let $D_{1}$ and
$D_{2}$ be distributions on $(k,\varphi,\epsilon)$-clusterable graphs as
defined earlier. Let $A$ be any $Q$-query deterministic algorithm. Let
$\mathcal{G}_{Q}$ denote the set of all graphs with maximum degree at most $d$
on $Q$ vertices. We define the distribution $P_{1}^{A}$ as follows.

$\forall H\in\mathcal{G}_{Q},P_{1}^{A}(H)=Pr_{G\sim D_{1}}(A\text{ on input
$G$ obtains $H$ as transcript}).$

Similarly, define the distribution $P_{2}$ as:

$\forall H\in\mathcal{G}_{Q},P_{2}^{A}(H)=Pr_{G\sim D_{2}}(A\text{ on input
$G$ obtains $H$ as transcript}).$

We now prove the following claim which shows that the transcript obtained by a
low query algorithm $A$ on input $G$ drawn from either $D_{1}$ or $D_{2}$ is
likely to be cycle free. We build up on this and argue that conditioned on the
transcript being cycle free, the distributions over the transcripts
$P_{1}^{A},P_{2}^{A}$ obtained by a low query algorithm are statistically
close and cannot be told apart.

######  Claim 3.

Let $d\geq 8,k\in\mathbb{N}$. Then there exist $\varphi=\varphi(d)$ such that
for all $\epsilon\ll\varphi^{2}$ such that the transcript obtained by any
determenistic $Q$-query algorithm $A$ (where $Q\leq\frac{1}{100d}\sqrt{n/k}$)
on input a graph $G$ drawn from the following distribution

$D=\begin{cases}D_{1}(n,d,\epsilon,k)\text{with prob $1/2$}\\\
D_{2}(n,d,\epsilon,k)\text{otherwise}\end{cases}$

satisfies the following with probability
$1-O\left(\frac{Q^{2}d^{2}}{n/k}\right)$: all connected components of
$\text{TRANSCRIPT}_{Q}(A,G)$ are acyclic and contain at most one tagged
vertex.

###### Proof.

Use Fact 2 and set $\varphi=\varphi(d)$ accordingly. Take any
$\epsilon\ll\varphi^{2}$. By Claim 2 with probability at most $p\leq
3k\cdot\left(\frac{1}{n}\right)^{d/3}$, either $G=\bot$ or $G$ fails to be
$(k,\varphi,\epsilon)$-clusterable. We condition on avoiding these bad events.
We show this result under the augmented query model. Suppose the $Q$-query
algorithm $A$ gets $s\leq Q$ tagged vertices at the start of execution. We
will prove the claimed properties of the transcript for $G\sim D_{1}$ by
induction on $Q-s$ which is the number of queries still available to $A$. (The
argument for $G\sim D_{2}$ is similar and we skip it). First, we setup our
induction hypothesis. To this end, for $s\leq q\leq Q$, define the event

$\mathcal{E}_{q}=\text{ACYC}_{q}\land\text{TAG}_{q}.$

Here $\text{ACYC}_{q}$ is the event that the subgraph
$\text{TRANSCRIPT}_{q}(A,G)$ is cycle free and $\text{TAG}_{q}$ is the event
that all the components in $\text{TRANSCRIPT}_{q}(A,G)$ contain at most one
tagged vertex. Suppose for some $s\leq q\leq Q$, all previous events
$\mathcal{E}_{s},\mathcal{E}_{s+1},\ldots\mathcal{E}_{q-1}$ have occured. We
write

$\mathcal{E}_{\leq
q-1}=\mathcal{E}_{s}\land\mathcal{E}_{s+1}\land\ldots\land\mathcal{E}_{q-1}.$

We will show by induction on $s\leq q\leq Q$ that

$\Pr(\mathcal{E}_{q}|\mathcal{E}_{\leq q-1)}\geq 1-\frac{20qd^{2}}{n/k}.$

For the base case, consider $q=s$. Note that
$\Pr(\mathcal{E}_{s}|\mathcal{E}_{\leq s-1})=1$ holds with probability $1$
because the transcript so far consists only of the $s$ vertices and does not
have any edges. Now consider the case where $s<q\leq Q$. Two cases arise.

Case 1: The $q$-th query is a vertex query: In this case, by randomness of
$\sigma$ in Line 16, $A$ obtains a uniformly random vertex $u\in
V\setminus\text{TRANSCRIPT}_{q-1}(A,G)$. Thus, in this case,
$\text{TRANSCRIPT}_{q}(A,G)$ continues to satisfy the induction hypothesis.

Case 2: The $q$-th query is an adjacency query: In this case, $A$ asks for all
the neighbors of some vertex $v_{q}\in\text{TRANSCRIPT}_{q-1}(A,G)$. Note that
the number of vertices and edges in $\text{TRANSCRIPT}_{q-1}(A,G)$ is at most
$qd$ . We use principle of deferred decisions while revealing the neighborhood
of $v_{q}$. Let $i\in[k]$ be such that $v_{q}\in C_{i}$. Let $H$ denote the
set of vertices in $\text{TRANSCRIPT}_{q-1}(A,G)$ which belong to the cluster
$C_{i}$ (the same cluster which contains $v_{q}$). Note that the total number
of half edges incident to vertices in $C_{i}$ is $dn/k$. Letting $E_{q-1}$
denote the set of edges in $\text{TRANSCRIPT}_{q-1}$, we see that the number
of half edges paired so far is at most $2\cdot|E_{q-1}|=2qd$. Fix a vertex
$u\in\text{TRANSCRIPT}_{q-1}(A,G)$. Note that the number of unpaired half
edges incident on both $v_{q},u$ is at most $d$. Now, we bound the probability
that over the randomness of the instance, the vertex $v_{q}$ (which is also
random) forms an edge with vertex $u$. By deferred decisions, this is seen to
be

$Pr\left((v_{q},u)\in E(G)|\mathcal{E}_{\leq
q-1}\right)\leq\frac{d^{2}}{dn/k-2qd}\leq\frac{dq^{2}}{dn/2k}\leq\frac{2kd}{n}.$

Here the second last step follows because $q\leq Q\leq\sqrt{n}$. By a union
bound over all the $|H|\leq qd$ vertices in $\text{TRANSCRIPT}_{q-1}(A,G)\cap
C_{i}$, we get

$Pr\left(\exists u\in H\colon(v_{q},u)\in
E(G)\right)\leq\frac{2kd|H|}{n}\leq\frac{2kq\cdot d^{2}}{n}.$

Now consider the set $R$ of remaining vertices in the transcript (which do not
belong to $C_{i}$). Fix any vertex $u\in R$. An edge is formed between $v_{q}$
and $u$ only if

  * •

$v_{q}$ and $u$ both receive a red half edge (either of these events occur
with probability $6\epsilon d$).

  * •

Conditioned on the above event, these red edges get randomly paired to be
crossed in line 12 of Algorithm 9.

Note that the number of red edges remaining in any cluster before the crossing
step is at least $4\epsilon dn-\epsilon/2dn\geq 3\epsilon dn$. If either
$v_{q}$ or $u$ do not have any red edge incident on it, $v_{q}$ does not form
an edge with $u$ with probability $1$. Now, suppose both $v_{q}$ and $u$ have
a red edge. By principle of deferred decisions, conditioned on
$\mathcal{E}_{\leq q-1}$, in any given iteration in line 5 of Algorithm 9,
this happens with probability at most $6\epsilon d\cdot 6\epsilon
d\cdot\frac{1}{3\epsilon dn/k\cdot 3\epsilon dn/k}\leq\frac{4k^{2}}{n^{2}}$.
Across all the at most $3\epsilon dn/k$ iterations, by a union bound, we have

$Pr\left((v_{q},u)\in E(G)|\mathcal{E}_{\leq
q-1}\right)\leq\frac{4k^{2}}{n^{2}}\cdot\frac{3\epsilon
dn}{k}=\frac{12\epsilon d}{n/k}.$

By a union bound, the probability that there is an edge between $v_{q}$ and
some vertex in $R$ is at most

$\frac{12\epsilon d|R|}{n/k}\leq\frac{12\epsilon qd^{2}}{n/k}.$

In all, this means conditioned on $\text{TRANSCRIPT}_{q-1}(A,G)$ being acyclic
and having at most one tagged vertex in each component, the probability that
some neighbor of $v_{q}$ ends up in $\text{TRANSCRIPT}_{q-1}(A,G)$,

$Pr(\overline{\mathcal{E}_{q}}|\mathcal{E}_{\leq q-1})\leq\frac{14\epsilon
qd^{2}}{n/k}\leq\frac{20\epsilon qd^{2}}{n/k}.$

In particular, conditioned on $\mathcal{E}_{\leq q-1}$,
$\text{TRANSCRIPT}_{q}(A,G)$ satisfies the statement of the induction
hypothesis with probability at least $1-\frac{20\epsilon qd^{2}}{n/k}$.

Therefore, the final transcript fails to satisfy the statement of the
induction hypothesis with probability at most

$p^{\prime}=\sum_{q=1}^{Q}\frac{20\epsilon q\cdot
d^{2}}{n/k}\leq\frac{10Q^{2}\cdot d^{2}}{n/k}.$

In particular, with probability at least $1-(p+p^{\prime})\geq
1-O\left(\frac{Q^{2}\cdot d^{2}}{n/k}\right)$ all the components of
$\text{TRANSCRIPT}_{Q}(A,G)$ are acyclic and contain at most one tagged
vertex. ∎

Now, we show our indistinguishability result using which Lemma 18 immediately
follows.

######  Lemma 21.

Let $A$ be any $Q$-query deterministic algorithm where
$Q\leq\frac{1}{100d}\sqrt{n/k}$. Then, the total variation distance
$\|P_{1}^{A}-P_{2}^{A}\|_{TV}\leq\frac{1}{10}$.

###### Proof.

Let $G\sim D$ where $D$ is either $D_{1}$ or $D_{2}$ with probability $1/2$
each. By Claim 2, with probability $p_{1}\leq
3k\cdot\left(\frac{1}{n}\right)^{d/3}$, $G$ is the empty graph $\bot$ or $G$
fails to be $(k,\varphi,\epsilon)$-clusterable. We condition on avoiding these
bad events. From Claim 3, we know that with probability $p_{2}\leq
O\left(\frac{Q^{2}d^{2}}{n/k}\right)$, $\text{TRANSCRIPT}_{Q}(A,G)$ either
contains cycles or has a connected component with more than one tagged vertex.
Suppose none of these bad events occur. Since the $q$-th query of $A$ only
depends on $\text{TRANSCRIPT}_{q-1}(A,G)$, whenever $A$ issues a vertex query
(as say the $q$-th query), by the randomness of $\sigma$ in Line 16 of
Algorithm 9, $A$ obtains a uniformly random vertex $u\in
V\setminus\text{TRANSCRIPT}_{q-1}(A,G)$. It follows that for $q\leq Q$,
conditioned on the $v_{q}$ (the vertex in the $q$-th edge query issued by $A$)
having no neighbors in $\text{TRANSCRIPT}_{q-1}(A,G)$, the transcript is
distributed identically regardless of whether $G$ is sampled from $D_{1}$ or
$D_{2}$. Thus, it holds that

$\|P_{1}^{A}-P_{2}^{A}\|_{TV}\leq p_{1}+p_{2}\leq
O\left(\frac{Q^{2}d^{2}}{n/k}\right).$

For $Q\leq 1/d\cdot O(\sqrt{n/k})$, this is at most $1/10$ as desired. ∎

Now, we are ready to prove Lemma 18.

###### Proof.

(Of Lemma 18) We note that $A$ is a deterministic $Q$-query algorithm. It is
given as input a graph $G\sim D$ where $D=D_{1}$ or $D=D_{2}$ with probability
$1/2$ each. It is required to correctly output whether $D=D_{1}$ or $D=D_{2}$.
By Lemma 21 we note that the distribution $P_{1}^{A}$ on the transcripts
obtained by $A$ on $G\sim D_{1}$ is statistically $1/10$ close to the
distribution $P_{2}^{A}$. $A$ being deterministic, the output of $A$ (which
declares whether $D=D_{1}$ or $D=D_{2}$) is an arbitrary but fixed function of
$\text{TRANSCRIPT}_{Q}(A,G)$. Let $p_{1}=Pr_{G\sim D_{1}}(A\text{ outputs
}D_{1})$ and $p_{2}=Pr_{G\sim D_{2}}(A\text{ outputs }D_{1})$. By closeness of
$P_{1}^{A},P_{2}^{A}$, we have $|p_{1}-p_{2}|\leq 1/10$. Now, the probability
that $A$ gives an incorrect response is

$\displaystyle Pr_{G\sim D}(A\text{ is wrong})$
$\displaystyle=\frac{1}{2}Pr_{G\sim D_{1}}(A\text{ outputs
}D_{2})+\frac{1}{2}Pr_{G\sim D_{2}}(A\text{ outputs }D_{1})$
$\displaystyle=\frac{1}{2}(1-p_{1})+\frac{1}{2}p_{2}$
$\displaystyle=\frac{1}{2}+\frac{1}{2}(p_{2}-p_{1})$ $\displaystyle\geq 9/20$
$\displaystyle>1/3$

Thus, the algorithm $A$ is likely to make an error in distinguishing between
$D_{1}$ and $D_{2}$ with probability strictly larger than $1/3$.
Contradiction. ∎

And finally, we prove Lemma 17.

###### Proof.

(Of Lemma 17) Use $D_{1}$ and $D_{2}$ as the distributions proposed in Lemma
18. Any $Q$-query determenistic algorithm in the RandomSampleModel is a
$Q$-query deterministic algorithm for which receives $s\leq Q$ tagged samples.
By Lemma 18, any such algorithm cannot distinguish between $D_{1}$ and $D_{2}$
with probability at least $2/3$. The result follows. ∎

##  6 Approximating Dasgupta Cost in the Oracle Model With Cluster Queries

In this section, we present algorithms to approximate Dasgupta Cost of a
$(k,\varphi,\epsilon)$-clusterable graph where we are allowed to query the
cluster a vertex belongs to. In particular, we prove the following theorem.

See 5

The preceding theorem asserts a tighter approximation to Dasgupta Cost of $G$
and bypasses the $\widetilde{\Omega}(\sqrt{n})$ lower bound asserted in
Theorem 4 thanks to the stronger query model. The key to this speed up is a
different (and faster) approximation to the contracted graph
$H=G/\mathcal{C}$. After this step, we use recursive sparsest cut on $H$ as
before to obtain an approximation to $\text{COST}_{G}(T^{*}_{G})$. We now
present our new algorithm which approximates the weighted adjacency matrix of
the contracted graph $H$.

Algorithm 11 $\textsc{ApproxContractedGraphOM}(G,\mathcal{D})$ # Suppose
$\widehat{c_{1}}\leq\widehat{c_{2}}\leq\ldots\leq\widehat{c_{k}}$

1: for $1\leq i<j\leq k$ do

2: $s\leftarrow\frac{10^{11}k^{9}\log n\cdot\log k}{\eta\epsilon^{2}}$.

3: Pick $s$ random vertices from $V$ and call the set $S$.

4: Find $S_{i}=S\cap C_{i}$ using the clustering oracle.

5: Set $X_{ij}=0$.

6: for $u\in S_{i}$ do

7: Pick random $v\in N(u)$.

8: if $v\in C_{j}$ then

9: $X_{ij}=X_{ij}+1$

10: end if

11: end for

12: Set $\widetilde{W}(i,j)=\frac{X_{ij}}{|S_{i}|}\cdot
d\cdot\widehat{c_{i}}$.

13: end for

14: $\widetilde{H}\leftarrow\left([k],{[k]\choose 2},\widetilde{W}\right)$.

15: return $\widetilde{H}$

Now, we present the procedure EstimatedCostOM.

Algorithm 12 $\textsc{EstimatedCostOM}(G,\mathcal{D})$

1: $\widetilde{H}\leftarrow\textsc{ApproxContractedGraphOM}(G,\mathcal{D})$ #
Let $\widetilde{H}=\left([k],{[k]\choose 2},\widetilde{W}\right)$

2: $\widetilde{Q}:=\left([k],{[k]\choose
2},\widetilde{W},\widetilde{w}\right)$, where for every $i\in[k]$,
$\widetilde{w}(i)=\widehat{c_{i}}$

3: Let $\widetilde{T}=\textsc{WRSC}(\widetilde{Q})$ denote a hierarchical
clustering tree constructed on the graph $\widetilde{Q}$ using the recursive
sparsest cut algorithm subject to balanced constraints (introduced by [CC17]).

4: $\textsc{EST}_{\text{OM}}\leftarrow
3\cdot\text{WCOST}_{\widetilde{Q}}(\widetilde{T})+\frac{3\epsilon
dn^{2}}{100k\sqrt{\log k}}+d\cdot\sum_{i=1}^{k}\widehat{c_{i}}^{2}$

5: return $\textsc{EST}_{\text{OM}}$

Finally, we present the procedure $\textsc{InitializeOracleOM}(G)$ below.
Notice that this procedure calls $\textsc{EstimateClusterSize}(G,i,\delta)$
(Algorithm 16). In RandomSampleModel, we used the same procedure to estimate
set sizes. We note that this procedure can be used with OracleModel as well.

Algorithm 13 InitializeOracleOM($G$)

1: $\delta\leftarrow\frac{1}{100\cdot k}$

2: $\widehat{c_{i}}\leftarrow\textsc{EstimateClusterSize}(G,i,\delta)$, for
every $i\in[k]$ # Algorithm 16

3: $\mathcal{D}\leftarrow\\{\widehat{c_{i}}\\}_{i\in[k]}$

4: return $\mathcal{D}$

The following claim follows as an immediate corollary of Lemma 27.

######  Claim 4.

Let $k\geq 2$, $\varphi\in(0,1)$, and $\frac{\epsilon}{\varphi^{2}}$ be
smaller than a positive sufficiently small constant. Let $G=(V,E)$ be a
$d$-regular graph that admits a $(k,\varphi,\epsilon)$-clustering
$C_{1},\ldots,C_{k}$. Let
$\eta=\frac{\min_{i\in[k]}|C_{i}|}{\max_{i\in[k]}|C_{i}|}$. Let
$\delta=\frac{1}{100k}$. Then the procedure $\textsc{InitializeOracleOM}(G)$
(Algorithm 13) runs in time $O\left(\frac{\log n\cdot
k^{2}}{\eta\cdot\delta^{2}}\right)$ and with probability at least
$1-n^{-100\cdot k}$ for every $i\in[k]$ returns a value $\widehat{c_{i}}$ such
that $\widehat{c_{i}}\in(1\pm\delta)\cdot|C_{i}|$.

Next, we prove in Claim 5 that for all pairs of clusters $C_{i},C_{j}$, the
preceding routine estimates $|E(C_{i},C_{j})|$ to within good accuracy as long
as $|E(C_{i},C_{j})|\geq\frac{\epsilon}{100k^{4}\sqrt{\log k}}\cdot
d\cdot\min(|C_{i}|,|C_{j}|)$. We first make a definition.

######  Definition 19.

For a fixed $i\in[k]$, we let $|E_{out}(C_{i})|=\sum_{j\neq
i}|E(C_{i},C_{j})|$ denote the total number of edges that leave $C_{i}$. For a
pair of clusters $C_{i},C_{j}$, if
$|E(C_{i},C_{j})|\geq\frac{\epsilon}{100k^{4}\sqrt{\log k}}\cdot
d\cdot\min(|C_{i}|,|C_{j}|)$ we refer to as the pair $C_{i},C_{j}$ being
_visible_. A pair $C_{i},C_{j}$ which has fewer edges is called _invisible_.

######  Claim 5.

Let $k\geq 2$, $\varphi\in(0,1)$, and $\frac{\epsilon}{\varphi^{2}}$ be
smaller than a positive suffciently small constant. Let $G=(V,E)$ be a
$d$-regular graph that admits a $(k,\varphi,\epsilon)$-clustering
$\mathcal{C}=(C_{1},\ldots,C_{k})$. Condition on
$\textsc{InitializeOracleOM}(G)$ (Algorithm 13) succeeding (which happens with
probability at least $1-n^{-100}$). Then with probability at least
$1-2/n^{8}$, for all visible pairs $C_{i},C_{j}$ of clusters, the following
holds: The $\textsc{ApproxContractedGraphOM}(G,\mathcal{D})$ procedure
(Algorithm 11) obtains an estimate $\widetilde{W}(i,j)$ to $|E(C_{i},C_{j})|$
where $\left|\widetilde{W}(i,j)-|E(C_{i},C_{j})|\right|\leq
0.01|E(C_{i},C_{j})|$

###### Proof.

Fix a pair of visible clusters $C_{i}$ and $C_{j}$ with $|C_{i}|\leq|C_{j}|$.
By definition of a visible pair, we have $|E(C_{i},C_{j})|=\epsilon_{ij}\cdot
d|C_{i}|\geq\frac{\epsilon}{100k^{4}\sqrt{\log k}}\cdot d|C_{i}|$. Consider
the following two cases.

Case 1: $\textsc{InitializeOracleOM}(G)$ concludes
$\widehat{c_{i}}\leq\widehat{c_{j}}$.

Case 2: $\textsc{InitializeOracleOM}(G)$ concludes
$\widehat{c_{j}}>\widehat{c_{i}}$. Since we condition on
$\textsc{InitializeOracleOM}(G)$ succesfully estimating size of each cluster
to good accuracy, this means $|C_{i}|>0.9|C_{j}|$. Thus, it holds that
$|E(C_{i},C_{j})|\geq\frac{\epsilon}{100k^{4}\sqrt{\log k}}\cdot 0.9\cdot
d|C_{j}|\geq\frac{\epsilon}{200k^{4}\sqrt{\log k}}\cdot d|C_{j}|$.

We consider the case where $\textsc{InitializeOracleOM}(G)$ concludes
$\widehat{c_{i}}\leq\widehat{c_{j}}$. (The other case, where
$\textsc{InitializeOracleOM}(G)$ concludes the other way round is completely
analogous and so we skip this case.) From the preceding discussion
$C_{i},C_{j}$, we know

$|E(C_{i},C_{j})|\geq\frac{\epsilon}{200k^{4}\sqrt{\log k}}d|C_{i}|.$

We now show how Algorithm 11 obtains a good estimate to $|E(C_{i},C_{j})|$ for
this pair. Since, $\widehat{c_{i}}\leq\widehat{c_{j}}$, when the procedure
ApproxContractedGraphOM processes the pair $C_{i},C_{j}$, it finds the samples
which come from $C_{i}$ in Line 4. Write $|E(C_{i},C_{j})|=\epsilon_{ij}\cdot
d|C_{i}|\geq\frac{\epsilon}{200k^{4}\sqrt{\log k}}\cdot d|C_{i}|$

Conditioned on InitializeOracleOM being successful, we have

$\widehat{c_{i}}\geq 0.99|C_{i}|\geq
0.99\cdot\eta\max_{\ell\in[k]}|C_{\ell}|\geq\frac{\eta}{2k}n.$ (55)

Thus, on choosing $s=\frac{10^{11}k^{9}\log n\cdot\log k}{\eta\epsilon^{2}}$
uniform samples from $V$, by a Chernoff Bound, with probability at least
$1-n^{-100}$, we have

$|S_{i}|=s_{i}\geq\frac{10^{10}k^{8}\log n\cdot\log k}{\epsilon^{2}}.$

Note that all vertices in the set $S_{i}$ obtained in Line 4 are distributed
uniformly inside $C_{i}$. Further, since $G$ is $d$-regular, the edge $(u,v)$
obtained on taking a random $v\sim N(u)$ is also distributed as a uniformly
random edge in $G$. Therefore, the probability that $v\sim N(u)$ ends up in
$C_{j}$ is exactly $\epsilon_{ij}$. The random variable $X_{ij}$ in Line 9
tracks the number of seen edges which cross the cut $|E(C_{i},C_{j})|$. Let
$\widetilde{\epsilon}_{ij}=\frac{X_{ij}}{s_{i}}$ and
$\gamma=\frac{\epsilon}{20000k^{4}\sqrt{\log k}}$. Note that
$\mathbb{E}[\widetilde{\epsilon}_{ij}]=\epsilon_{ij}$. By an additive Chernoff
Bound,

$Pr(\left|\widetilde{\epsilon}_{ij}-\mathbb{E}[\widetilde{\epsilon}_{ij}]\right|\geq\gamma)\leq\exp(-\gamma^{2}s_{i})\leq\exp\left(-\frac{\epsilon^{2}}{4\cdot
10^{8}k^{8}\cdot\log k}\cdot\frac{10^{10}k^{8}\log n\cdot\log
k}{\epsilon^{2}}\right)\leq n^{-10}.$

Since, $\epsilon_{ij}\geq\frac{\epsilon}{200k^{4}\sqrt{\log k}}$, it holds
that $\widetilde{\epsilon}_{ij}\in(0.999\epsilon_{ij},1.001\epsilon_{ij})$.
Finally, Line 12 sets $\widetilde{W}(i,j)=\widetilde{\epsilon}_{ij}\cdot
d\cdot\widehat{c_{i}}$. Recalling, $\widehat{c_{i}}\in(1\pm 1/100k)|C_{i}|$,
it follows that

$\widetilde{W}(i,j)\in(0.99,1.01)\cdot|E(C_{i},C_{j})|$

holds with probability at least $1-n^{-10}-n^{-100}\geq 1-2n^{-10}$ for any
pair of visible clusters. Therefore, by a union bound over all pairs of
visible clusters $C_{i},C_{j}$ (of which there is at most $k^{2}$), with
probability at least $1-2/n^{8}$,

$\widetilde{W}(i,j)\in(0.99,1.01)\cdot|E(C_{i},C_{j})|$

holds. ∎

We show another claim which shows that for any invisible pair $C_{i},C_{j}$ of
clusters, $\widetilde{W}(i,j)$ is not too large with high probability.

######  Claim 6.

Let $k\geq 2$, $\varphi\in(0,1)$, and $\frac{\epsilon}{\varphi^{2}}$ be
smaller than a positive suffciently small constant. Let $G=(V,E)$ be a
$d$-regular graph that admits a $(k,\varphi,\epsilon)$-clustering
$\mathcal{C}=(C_{1},\ldots,C_{k})$. Condition on
$\textsc{InitializeOracleOM}(G)$ (Algorithm 4) succeeding (which happens with
probability at least $1-n^{-100}$). Then with probability at least
$1-2/n^{8}$, for all invisible pairs $C_{i},C_{j}$ of clusters, the following
holds: The $\textsc{ApproxContractedGraphOM}(G,\mathcal{D})$ procedure
(Algorithm 11) obtains an estimate $\widetilde{W}(i,j)$ to $|E(C_{i},C_{j})|$
where $\widetilde{W}(i,j)\leq\frac{\epsilon}{50k^{4}\sqrt{\log k}}\cdot
d\cdot\min(|C_{i}|,|C_{j}|)$.

###### Proof.

Fix a pair of invisible clusters $C_{i}$ and $C_{j}$ with
$|C_{i}|\leq|C_{j}|$. By definition of an invisible pair, we have
$|E(C_{i},C_{j})|=\epsilon_{ij}\cdot
d|C_{i}|<\frac{\epsilon}{100k^{4}\sqrt{\log k}}\cdot d|C_{i}|$. Two cases
arise.

Case 1: $\textsc{InitializeOracleOM}(G)$ concludes
$\widehat{c_{i}}\leq\widehat{c_{j}}$.

Case 2: $\textsc{InitializeOracleOM}(G)$ concludes
$\widehat{c_{j}}>\widehat{c_{i}}$. In this case, recall $|C_{i}|>0.9|C_{j}|$.
Therefore, it holds that $|E(C_{i},C_{j})|<\frac{\epsilon}{90k^{4}\sqrt{\log
k}}\cdot d|C_{i}|$.

We consider case 1 first where $\textsc{InitializeOracleOM}(G)$ concludes
$\widehat{c_{i}}\leq\widehat{c_{j}}$. (The other case, where
$\textsc{InitializeOracleOM}(G)$ concludes the other way is analogous). Write
$|E(C_{i},C_{j})|=\epsilon_{ij}\cdot
d|C_{i}|<\frac{\epsilon}{90k^{4}\sqrt{\log k}}\cdot d|C_{i}|$

The rest of the argument is very similar to the preceding proof. Like before,
choose $s=\frac{10^{11}k^{9}\log n\cdot\log k}{\eta\epsilon^{2}}$ uniform
samples from $V$, by a Chernoff Bound, with probability at least $1-n^{-100}$,
we have

$|S_{i}|=s_{i}\geq\frac{10^{10}k^{8}\log n\cdot\log k}{\epsilon^{2}}.$

Again just like before note that all vertices in the set $S_{i}$ obtained in
Line 4 are distributed uniformly inside $C_{i}$. Further, since $G$ is
$d$-regular, the edge $(u,v)$ obtained on taking a random $v\sim N(u)$ is also
distributed as a uniformly random edge in $G$. Therefore, the probability that
$v\sim N(u)$ ends up in $C_{j}$ is exactly $\epsilon_{ij}$. Line 9 tracks,
using the random variable $X_{ij}$, the number of seen edges which cross the
cut $|E(C_{i},C_{j})|$. Let $\widetilde{\epsilon}_{ij}=\frac{X_{ij}}{s_{i}}$
and $\gamma=\frac{\epsilon}{20000k^{4}\cdot\sqrt{\log k}}$. Note that
$\mathbb{E}[\widetilde{\epsilon}_{ij}]=\epsilon_{ij}$.

If $\epsilon_{ij}=\epsilon_{0}=\frac{\epsilon}{90k^{4}\cdot\sqrt{\log k}}$, a
Chernoff Bound gives
$Pr(\widetilde{\epsilon}_{ij}\geq\frac{\epsilon}{80k^{4}})\leq n^{-10}$. For
$\epsilon_{ij}<\epsilon_{0}$, a probability bound of at most $n^{-10}$ follows
by a coupling argument (Proposition 1). Finally, Line 12 sets
$\widetilde{W}(i,j)=\widetilde{\epsilon}_{ij}\cdot d\cdot\widehat{c_{i}}$.
Recalling, $\widehat{c_{i}}\in(1\pm 1/100k)|C_{i}|$, it follows that

$\widetilde{W}(i,j)\leq\frac{\epsilon}{80k^{4}\cdot\sqrt{\log k}}\cdot
d\cdot\left(|C_{i}|+\frac{|C_{i}|}{100k}\right)\leq\frac{\epsilon}{50k^{4}\cdot\sqrt{\log
k}}\cdot d\cdot|C_{i}|$

holds with probability at least $1-n^{-10}-n^{-100}\geq 1-2n^{-10}$ for any
pair of invisible clusters. Therefore, by a union bound over all pairs of
invisible clusters, it holds with probability at least $1-2n^{-8}$ that
$\widetilde{W}_{ij}\leq\frac{\epsilon}{50k^{4}\cdot\sqrt{\log k}}\cdot
d\cdot\min(|C_{i}|,|C_{j}|)$.

∎

We now recall some setup we used earlier to obtain good approximations to
Dasgupta Cost of an optimum tree on $G$. Let $Q=([k],\binom{[k]}{2},W,w)$
denote the vertex weighted contraction of $G$ with respect to the partition
$\mathcal{C}$ and let $T^{*}_{Q}$ denote an optimum weighted Dasgupta tree for
$Q$. Let $\widetilde{H}=\left([k],\binom{[k]}{2},\widetilde{W}\right)$ denote
the weighted graph returned by Algorithm 11 and let
$\widetilde{Q}=\left([k],\binom{[k]}{2},\widetilde{W},\widetilde{w}\right)$
where $\widetilde{w}(i)=\widehat{c_{i}}$. Let $\widetilde{T}$ denote the tree
constructed on $\widetilde{Q}$ by using the recursive sparsest cut algorithm.
As before, we estimate Dasgupta cost of $G$ as

$\textsc{EST}_{\text{OM}}=3\cdot\text{WCOST}_{\widetilde{Q}}(\widetilde{T})+\frac{3\epsilon
dn^{2}}{100k\sqrt{\log k}}+d\cdot\sum_{i=1}^{k}\widehat{c_{i}}^{2}.$

It is convenient to have the following lemma.

######  Lemma 22.

Let $Q,\widetilde{Q}$ be as defined above. Condition on InitializeOracleOM
being succesful in estimating all the set sizes (which happes with probability
at least $1-n^{-100}$). Let $\widetilde{T}=\textsc{WRSC}(\widetilde{Q})$
denote a hierarchical clustering tree constructed on the graph $\widetilde{Q}$
using the recursive sparsest cut algorithm. Then with probability at least
$1-1/n$ we have

$\frac{1}{3}\cdot\text{WCOST}_{Q}(T^{*}_{Q})-\frac{\epsilon}{100k\cdot\sqrt{\log
k}}dn^{2}\leq\text{WCOST}_{\widetilde{Q}}(\widetilde{T})\leq O\left(\sqrt{\log
k}\cdot\text{WCOST}_{Q}(T^{*}_{Q})+\frac{\epsilon}{k}dn^{2}\right).$

###### Proof.

We first show that with probability at least $1-4/n^{8}\geq 1-1/n$,
simultaneously for all $S\subseteq[k]$, it holds that

$0.99\cdot W(S,\overline{S})-\frac{\epsilon dn^{2}}{100k^{2}\cdot\sqrt{\log
k}}\leq 1.01\cdot W(S,\overline{S})+\frac{\epsilon
dn^{2}}{50k^{2}\cdot\sqrt{\log k}}.$

First, note that by Claim 5, with probability at least $1-2/n^{8}$,
simultaneuosly, for all visible pairs of clusters $C_{i},C_{j}$, we have

$\widetilde{W}(i,j)\in(0.99,1.01)\cdot|E(C_{i},C_{j})|.$

Also, by Claim 6, with probability at least $1-2/n^{8}$, simultaneously, for
all invisible pairs $C_{i},C_{j}$ of clusters we have
$\widetilde{W}(i,j)\leq\frac{\epsilon}{50k^{4}\sqrt{\log k}}\cdot
d\cdot\min(|C_{i}|,|C_{j}|)$.

From now on, we condition on these events. Now take any $S\subseteq[k]$ and
consider the cut $(S,\overline{S})$. Let VIS and INVIS denote the set of
visible and invisible pairs of respectievely. Now, note

$\displaystyle\widetilde{W}(S,\overline{S})$
$\displaystyle=\sum_{(i,j)\in\text{VIS}}\widetilde{W}(i,j)+\sum_{(i,j)\in\text{INVIS}}\widetilde{W}(i,j)$
$\displaystyle\leq 1.01\sum_{(i,j)\in\text{VIS}}W(i,j)+\frac{\epsilon
d}{50k^{4}\cdot\sqrt{\log
k}}\cdot\sum_{(i,j)\in\text{INVIS}}\min(|C_{i}|,|C_{j}|)$ By Claims 5 and 6
$\displaystyle\leq 1.01W(S,\overline{S})+\frac{\epsilon
dn}{50k^{2}\cdot\sqrt{\log k}}$ (56)

Also note,

$\displaystyle\widetilde{W}(S,\overline{S})$
$\displaystyle=\sum_{(i,j)\in\text{VIS}}\widetilde{W}(i,j)+\sum_{(i,j)\in\text{INVIS}}\widetilde{W}(i,j)$
$\displaystyle\geq 0.99\sum_{(i,j)\in\text{VIS}}W(i,j)$ By Claim 5
$\displaystyle\geq
0.99W(S,\overline{S})-0.99\cdot\sum_{(i,j)\in\text{INVIS}}W(i,j)$
$\displaystyle\geq 0.99W(S,\overline{S})-0.99\frac{\epsilon\cdot
d}{100k^{4}\cdot\sqrt{\log
k}}\cdot\sum_{(i,j)\in\text{INVIS}}\min(|C_{i}|,|C_{j}|)$ By Claim 6
$\displaystyle\geq 0.99W(S,\overline{S})-\frac{\epsilon\cdot
dn}{100k^{2}\sqrt{\log k}}$ (57)

Set $a=0.99,a^{\prime}=1.01,b=\frac{\epsilon\cdot dn}{50k^{2}\sqrt{\log
k}},b^{\prime}=2b$. Moreover, note that by Lemma 27 with probability at least
$1-n^{-100\cdot k}$ we have $\frac{1}{2}\cdot w(i)\leq\widetilde{w}(i)\leq
2\cdot w(i)$. Now, apply Lemma 11 with these parameters. With probability at
least $1-4/n^{8}\geq 1-1/n$, this gives

$\frac{1}{3}\cdot\text{WCOST}_{Q}(T^{*}_{Q})-\frac{\epsilon\cdot
dn^{2}}{100k\sqrt{\log k}}\leq\text{WCOST}_{\widetilde{Q}}(\widetilde{T})\leq
O\left(\sqrt{\log k}\cdot\text{WCOST}_{Q}(T^{*}_{Q})+\frac{\epsilon\cdot
dn^{2}}{k}\right).$

∎

Now, we are ready to prove Theorem 5.

###### Proof.

(Of Theorem 5)

Let $Q=G/\mathcal{C}$ be the contraction of $G$ with respect to the partition
$\mathcal{C}$ (Definition 4) and let $T^{*}_{Q}$ denote an optimum weighted
Dasgupta tree for $Q$. Let $\widetilde{H}=\left([k],{[k]\choose
2},\widetilde{W}\right)$ be the graph obtained by
$\textsc{ApproxContractedGraphOM}(G,\xi,\mathcal{D})$ (Algorithm 11), and let
$\widetilde{Q}=\left([k],{[k]\choose 2},\widetilde{W},\widetilde{w}\right)$,
where for every $i\in[k]$, $\widetilde{w}(i)=\widehat{c_{i}}$. Let
$\widetilde{T}=\textsc{RSC}(\widetilde{Q})$ denote a hierarchical clustering
tree constructed on the graph $\widetilde{Q}$ using the recursive sparsest cut
algorithm. Therefore, by Lemma 22 with probability at least $1-1/n$, we have

$\frac{1}{3}\cdot\text{WCOST}_{Q}(T^{*}_{Q})-\frac{\epsilon}{100k\sqrt{\log
k}}dn^{2}\leq\text{WCOST}_{\widetilde{Q}}(\widetilde{T})\leq O\left(\sqrt{\log
k}\cdot\text{WCOST}_{Q}(T^{*}_{Q})+\frac{\epsilon}{k}dn^{2}\right)$ (58)

Note that as per line (4) of Algorithm 12 we estimate the Dasgupta cost of $G$
by

$\textsc{EST}_{\text{OM}}=3\cdot\text{WCOST}_{\widetilde{Q}}(\widetilde{T})+\frac{3\epsilon
dn^{2}}{100k\sqrt{\log k}}+d\cdot\sum_{i=1}^{k}\widehat{c_{i}}^{2}\text{.}$
(59)

Set $a=1/3,a^{\prime}=1$ and set $b=\frac{\epsilon}{100k\sqrt{\log
k}}\leq\frac{a}{k\sqrt{\log k}}$. An application of Lemma 16 gives

$\text{COST}_{G}(T^{*}_{G})\leq\textsc{EST}_{\text{OM}}\leq
O\left(\frac{\sqrt{\log
k}}{\varphi}\right)\cdot\text{COST}_{G}(T^{*}_{G})\text{.}$

Running Time analysis: First, we consider the running time of
InitializeOracleOM. This procedure just estimates $|C_{i}|$ for each
$i\in[k]$. Choosing $\delta=1/100k$, we just call EstimateClusterSize
procedure size each call to which takes time $t=\frac{400\cdot\log n\cdot
k^{2}}{\eta\delta^{2}}$. Thus the overall time taken by InitializeOracleOM
procedure is $T_{\text{init}}=k\cdot t=O\left(\frac{k^{5}\cdot\log
n}{\eta}\right)$. Condition on InitializeOracleOM being successful (which is a
high probability event). Now, we upperbound the running time of
EstimatedCostOM procedure. The major contributors to running time for this
process are calls to ApproxContractedGraphOM ($k^{2}$ of those) and the call
to recursive sparsest cut procedure. Consider a pair of clusters
$C_{i},C_{j}$. Take a pair of clusters $C_{i},C_{j}$ considered in line 1 of
the ApproxContractedGraphOM procedure (where suppose
$\widehat{c_{i}}\leq\widehat{c_{j}}$). This iteration of the loop takes
$L_{ij}=O\left(\frac{k^{9}\cdot\log n\cdot\log
k}{\eta\cdot\epsilon^{2}}\right)$ samples in all and finds the samples which
come from $C_{i}$. Thereafter, it just returns the empirical number of
crossing $E(C_{i},C_{j})$ edges seen scaled appropriately. Thus, the total
time taken by ApproxContractedGraphOM procedure in all is at most $k^{2}\cdot
L_{ij}$ which is at most $\frac{k^{11}\cdot\log n}{\eta\cdot\epsilon^{2}}$.
The time taken by recursive sparsest cut is $k^{O(1)}$ which means the total
time taken by EstimatedCostOM routine is at most $\left(\frac{k\cdot\log
n}{\eta\cdot\epsilon}\right)^{O(1)}$. Finally, we bound the number of seed
queries/oracle queries issued by this algorithm. Note that according to line 2
of Algorithm 11, we have $s=\frac{10^{11}k^{9}\log n\cdot\log
k}{\eta\epsilon^{2}}$. These are all the vertices for which we ever issue
oracle queries which means number of oracle queries issued is at most
$\left(\frac{k\log n}{\eta\cdot\epsilon}\right)^{O(1)}$ as desired. ∎

For completeness, we prove Proposition 1.

######  Proposition 1.

Let $X_{1},X_{2}\ldots X_{s}\sim Ber(p)$ denote $s$ independent and identially
distiributed Bernoulli variables with parameter $p$. Let $Y_{1},Y_{2},\ldots
Y_{s}\sim Ber(q)$ denote another $s$ Bernoulli variables with rate $0\leq
q<p\leq 1$. Then for any $t\leq s$, it holds that $Pr(\sum Y_{i}>t)\leq
Pr(\sum X_{i}>t)$.

###### Proof.

The proof is a coupling argument. We consider a different experiment which
produces random variables $Z_{1},Z_{2},\ldots Z_{s}$ where for any $i\in[s]$
$Z_{i}$ has the same distribution as $Z_{i}$ and $Z_{1},Z_{2},\ldots Z_{s}$ is
a collection of independent random variables. For $i\in[s]$,

  * •

If $Y_{i}=1$, set $Z_{i}=1$.

  * •

If $Y_{i}=0$, set $Z_{i}=1$ with probability $\frac{p-q}{1-q}$.

Thus, each $Z_{i}\sim Ber(p)$ as desired. Moreover, by construction, for any
$t\leq s$, we have $Pr(\sum X_{i}>t)=Pr(\sum Z_{i}>t)\geq Pr(\sum Y_{i}>t)$ as
desired. ∎

## References

  * [AB15] Hassan Ashtiani and Shai Ben-David.  Representation learning for clustering: A statistical framework.  In Marina Meila and Tom Heskes, editors, Proceedings of the Thirty-First Conference on Uncertainty in Artificial Intelligence, UAI 2015, July 12-16, 2015, Amsterdam, The Netherlands, pages 82–91. AUAI Press, 2015.
  * [ABJ18] Nir Ailon, Anup Bhattacharya, and Ragesh Jaiswal.  Approximate correlation clustering using same-cluster queries.  In Proc. of LATIN, pages 14–27, 2018.
  * [ABJK18] Nir Ailon, Anup Bhattacharya, Ragesh Jaiswal, and Amit Kumar.  Approximate clustering with same-cluster queries.  In Proc. of ITCS, volume 94, pages 40:1–40:21, 2018.
  * [AKB16] Hassan Ashtiani, Shrinu Kushagra, and Shai Ben-David.  Clustering with same-cluster queries.  In Daniel D. Lee, Masashi Sugiyama, Ulrike von Luxburg, Isabelle Guyon, and Roman Garnett, editors, Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, December 5-10, 2016, Barcelona, Spain, pages 3216–3224, 2016.
  * [BBM02] Sugato Basu, Arindam Banerjee, and Raymond Mooney.  Semi-supervised clustering by seeding.  In In Proceedings of 19th International Conference on Machine Learning (ICML-2002. Citeseer, 2002.
  * [BCBLP20] Marco Bressan, Nicolò Cesa-Bianchi, Silvio Lattanzi, and Andrea Paudice.  Exact recovery of mangled clusters with same-cluster queries.  In Advances in Neural Information Processing Systems, volume 33, pages 9324–9334, 2020.
  * [BCLP21] Marco Bressan, Nicolò Cesa-Bianchi, Silvio Lattanzi, and Andrea Paudice.  Exact recovery of clusters in finite metric spaces using oracle queries.  In Proc. of COLT, volume 134, pages 775–803, 2021.
  * [CAKMTM18] Vincent Cohen-Addad, Varun Kanade, Frederik Mallmann-Trenn, and Claire Mathieu.  Hierarchical clustering: Objective functions and algorithms.  In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 378–397. SIAM, 2018.
  * [CC17] Moses Charikar and Vaggos Chatziafratis.  Approximate hierarchical clustering via sparsest cut and spreading metrics.  In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 841–854. SIAM, 2017.
  * [CKK+18] Ashish Chiplunkar, Michael Kapralov, Sanjeev Khanna, Aida Mousavifar, and Yuval Peres.  Testing graph clusterability: Algorithms and lower bounds.  In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 497–508. IEEE, 2018.
  * [CPS15] Artur Czumaj, Pan Peng, and Christian Sohler.  Testing cluster structure of graphs.  In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 723–732, 2015.
  * [CS07] Artur Czumaj and Christian Sohler.  Testing expansion in bounded-degree graphs.  In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), October 20-23, 2007, Providence, RI, USA, Proceedings, pages 570–578. IEEE Computer Society, 2007.
  * [Das16] Sanjoy Dasgupta.  A cost function for similarity-based hierarchical clustering.  In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 118–127, 2016.
  * [DBE99] Ayhan Demiriz, Kristin P Bennett, and Mark J Embrechts.  Semi-supervised clustering using genetic algorithms.  Artificial neural networks in engineering (ANNIE-99), pages 809–814, 1999.
  * [EZK18] Ehsan Emamjomeh-Zadeh and David Kempe.  Adaptive hierarchical clustering using ordinal queries.  In Proc. of ACM-SIAM SODA, pages 415–429. SIAM, 2018.
  * [FGSS18] Donatella Firmani, Sainyam Galhotra, Barna Saha, and Divesh Srivastava.  Robust entity resolution using a crowd oracle.  IEEE Data Eng. Bull., 41(2):91–103, 2018.
  * [GKL+21] Grzegorz Gluch, Michael Kapralov, Silvio Lattanzi, Aida Mousavifar, and Christian Sohler.  Spectral clustering oracles in sublinear time.  In Dániel Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 \- 13, 2021, 2021.
  * [GNK+15] Anja Gruenheid, Besmira Nushi, Tim Kraska, Wolfgang Gatterbauer, and Donald Kossmann.  Fault-tolerant entity resolution with the crowd.  CoRR, abs/1512.00537, 2015.
  * [GR02] Oded Goldreich and Dana Ron.  Property testing in bounded degree graphs.  Algorithmica, 32(2):302–343, 2002.
  * [GR11] Oded Goldreich and Dana Ron.  On testing expansion in bounded-degree graphs.  In Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation - In Collaboration with Lidor Avigad, Mihir Bellare, Zvika Brakerski, Shafi Goldwasser, Shai Halevi, Tali Kaufman, Leonid Levin, Noam Nisan, Dana Ron, Madhu Sudan, Luca Trevisan, Salil Vadhan, Avi Wigderson, David Zuckerman, pages 68–75. 2011.
  * [HMMP19] Wasim Huleihel, Arya Mazumdar, Muriel Médard, and Soumyabrata Pal.  Same-cluster querying for overlapping clusters.  In Advances in Neural Information Processing Systems 32, pages 10485–10495, 2019.
  * [KBDM09] Brian Kulis, Sugato Basu, Inderjit Dhillon, and Raymond Mooney.  Semi-supervised graph clustering: a kernel approach.  Machine learning, 74(1):1–22, 2009.
  * [KS08] Satyen Kale and C. Seshadhri.  An expansion tester for bounded degree graphs.  In Automata, Languages and Programming, 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings, Part I: Tack A: Algorithms, Automata, Complexity, and Games, pages 527–538, 2008.
  * [KV00] Jeong Han Kim and Van H. Vu.  Concentration of multivariate polynomials and its applications.  Comb., 20(3):417–434, 2000.
  * [LGT14] James R Lee, Shayan Oveis Gharan, and Luca Trevisan.  Multiway spectral partitioning and higher-order cheeger inequalities.  Journal of the ACM (JACM), 61(6):37, 2014.
  * [LT80] Richard J. Lipton and Robert Endre Tarjan.  Applications of a planar separator theorem.  SIAM J. Comput., 9(3), 1980.
  * [MP17] Arya Mazumdar and Soumyabrata Pal.  Semisupervised Clustering, AND-Queries and Locally Encodable Source Coding.  In Advances in Neural Information Processing Systems 30, pages 6489–6499, 2017.
  * [MS17a] Arya Mazumdar and Barna Saha.  Clustering with noisy queries.  In Advances in Neural Information Processing Systems 30, pages 5788–5799, 2017.
  * [MS17b] Arya Mazumdar and Barna Saha.  Query complexity of clustering with side information.  In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems 30, pages 4682–4693. Curran Associates, Inc., 2017.
  * [MS21] Bogdan-Adrian Manghiuc and He Sun.  Hierarchical clustering: O(1)-approximation for well-clustered graphs.  In NeurIPS, pages 9278–9289, 2021.
  * [NS10] Asaf Nachmias and Asaf Shapira.  Testing the expansion of a graph.  Inf. Comput., 208(4):309–314, 2010.
  * [Pen20] Pan Peng.  Robust clustering oracle and local reconstructor of cluster structure of graphs.  In Shuchi Chawla, editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 2953–2972. SIAM, 2020.
  * [SK02] Janne Sinkkonen and Samuel Kaski.  Clustering based on conditional distributions in an auxiliary space.  Neural Computation, 14(1):217–239, 2002.
  * [SS19] Barna Saha and Sanjay Subramanian.  Correlation clustering with same-cluster queries bounded by optimal cost.  CoRR, abs/1908.04976, 2019.
  * [VGM15] Vasilis Verroios and Hector Garcia-Molina.  Entity resolution with crowd errors.  In Proc. of IEEE ICDE, pages 219–230, 2015.
  * [VGMP17] Vasilis Verroios, Hector Garcia-Molina, and Yannis Papakonstantinou.  Waldo: An adaptive human interface for crowd entity resolution.  In Proc. of ACM SIGMOD, pages 1133–1148, 2017.
  * [VRG19] Fabio Vitale, Anand Rajagopalan, and Claudio Gentile.  Flattening a hierarchical clustering through active learning.  In Advances in Neural Information Processing Systems 32, pages 15263–15273, 2019.

##  Appendix A Proof of Theorem 8

The main idea in proving Theorem 3 lies in a procedure which provides query
access to (an approximate version) of the Laplacian of the _contracted graph_
(see Definition 4). This is achieved by the procedure ApproxContractedGraph
(Algorithm 2) which is presented in Section 4.2. We do this in sublinear time
by implementing a QuadraticOracle procedure which on input a vector
$z\in\mathbb{R}^{k}$ returns an approximation $\alpha_{z}$ to the quadratic
form $z^{T}\mathcal{L}_{H}z$ where $\alpha_{z}\in\left(\frac{1}{2}\cdot
z^{T}\mathcal{L}_{H}z-\xi dn,\frac{3}{\varphi^{2}}\cdot
z^{T}\mathcal{L}_{H}z+\xi dn\right)$. In turn, this is achieved by
implementing a weighted dot product oracle which we present in the next
section.

###  A.1 Weighted Dot Product Oracle

The main result of this section is Theorem 8.

See 8

######  Remark 4.

This result is similar to Theorem 2 in [GKL+21]. The difference being Theorem
2 in [GKL+21] approximates dot product between the embedding vectors
$\left\langle f_{x},f_{y}\right\rangle$. Here, we instead want to approximate
the weighted dot product $\left\langle f_{x},\Sigma_{[k]}f_{y}\right\rangle$.
Further, in the setup considered in [GKL+21], all the clusters $C_{i}$ have
sizes within a constant factor of each other; whereas in our setup, their
sizes could differ up to a $1/\eta$ factor. These differences lead to a
running time which is $\text{poly}(1/\eta)$ factor larger than the running
times obtained in Theorem 2 of [GKL+21].

We also need to set up some notation which is used in this section. Let $m\leq
n$ be integers. For any matrix $A\in\mathbb{R}^{n\times m}$ with singular
value decomposition (SVD) $A=Y\Gamma Z^{T}$ we assume $Y\in\mathbb{R}^{n\times
n}$ and $Z\in\mathbb{R}^{m\times n}$ are orthogonal matrices and
$\Gamma\in\mathbb{R}^{n\times n}$ is a diagonal matrix of singular values.
Since $Y$ and $Z$ are orthogonal matrices, their columns form an orthonormal
basis. For any integer $q\in[m]$ we denote $Y_{[q]}\in\mathbb{R}^{n\times q}$
as the first $q$ columns of $Y$ and $Y_{-[q]}$ to denote the matrix of the
remaining columns of $Y$. We also denote $Z^{T}_{[q]}\in\mathbb{R}^{q\times
n}$ as the first $q$ rows of $Z^{T}$ and $Z^{T}_{-[q]}$ to denote the matrix
of the remaining rows of $Z$. Finally we denote
$\Gamma^{T}_{[q]}\in\mathbb{R}^{q\times q}$ as the first $q$ rows and columns
of $\Gamma$ and we use $\Gamma_{-[q]}$ as the last $n-q$ rows and columns of
$\Gamma$. So for any $q\in[m]$ the span of $Y_{-[q]}$ is the orthogonal
complement of the span of $Y_{[q]}$, also the span of $Z_{-[q]}$ is the
orthogonal complement of the span of $Z_{[q]}$. Thus we can write
$A=Y_{[q]}\Gamma_{[q]}Z^{T}_{[q]}+Y_{-[q]}\Gamma_{-[q]}Z^{T}_{-[q]}$.

Algorithm 14 InitializeWeightedDotProductOracle($G,\xi$)

1: $t\leftarrow\frac{20\cdot\log n}{\varphi^{2}}$

2: $R_{\text{init}}\leftarrow
n^{1/2+O(\epsilon/\varphi^{2})}\cdot\left(\frac{k\cdot\log
n}{\xi\cdot\eta}\right)^{O(1)}$

3: $s\leftarrow n^{O(\epsilon/\varphi^{2})}\cdot\left(\frac{k\cdot\log
n}{\xi\cdot\eta}\right)^{O(1)}$

4: $I_{S}\leftarrow$ $s$ indices chosen independently and uniformly at random
with replacement from $\\{1,\ldots,n\\}$

5:
${\widehat{Q}}\leftarrow\textsc{EstimateTransitionMatrix}(G,I_{S},R_{\text{init}},t)$
# $\widehat{Q}$ has at most $R_{\text{init}}\cdot s$ non-zeros

6:
$\mathcal{G}\leftarrow$EstimateCollisionProbabilities$(G,I_{S},R_{\text{init}},t)$

7: Compute eigendecomposition
$\frac{n}{s}\cdot\mathcal{G}:=\widehat{W}\widehat{\Sigma}\widehat{W}^{T}$ of
$\frac{n}{s}\cdot\mathcal{G}$ # $\mathcal{G}\in\mathbb{R}^{s\times s}$

8:
$\Psi\leftarrow\frac{n}{s}\cdot\widehat{W}_{[k]}\widehat{\Sigma}_{[k]}^{-2}\widehat{W}_{[k]}^{T}$
# $\Psi\in\mathbb{R}^{s\times s}$

9: return $\mathcal{D}_{w}:=\\{\Psi,\widehat{Q}\\}$

Algorithm 15 $\textsc{WeightedDotProductOracle}(G,x,y,\xi,\mathcal{D})$ #
$\mathcal{D}_{w}:=\\{\Psi,\widehat{Q}\\}$

1: $R_{\text{query}}\leftarrow
n^{1/2+O(\epsilon/\varphi^{2})}\cdot\left(\frac{k\cdot\log
n}{\xi\cdot\eta}\right)^{O(1)}$

2:
${\widehat{m}_{x}\leftarrow\textsc{RunRandomWalks}(G,R_{\text{query}},t+1,x)}$
# unlike in [GKL+21], walk length $=t+1$

3:
${\widehat{m}_{y}\leftarrow\textsc{RunRandomWalks}(G,R_{\text{query}},t,y)}$

4: return $\left\langle
f_{x},\Sigma_{[k]}f_{y}\right\rangle_{\scriptscriptstyle
apx}:=(\widehat{m}_{x}^{T}\widehat{Q})\Psi(\widehat{Q}^{T}\widehat{m}_{y})$

We build up on a collection of tools from [GKL+21]. First, we use Lemma 23
which shows that $(k,\varphi,\epsilon)$-clusterable graphs, the outer products
of the columns of the $t$-step random walk transition matrix small spectral
norm. This holds because the matrix power dominate by the first $k$
eigenvectors and each of them have bounded infinity norm.

######  Lemma 23.

[GKL+21] Let $k\geq 2$ be an integer, $\varphi\in(0,1)$ and
$\epsilon\in(0,1)$. Let $G=(V,E)$ be a $d$-regular graph that admits a
$(k,\varphi,\epsilon)$-clustering $C_{1},\ldots C_{k}$. Let
$\eta=\frac{\min_{i\in[k]}|C_{i}|}{\max_{i\in[k]}|C_{i}|}$. Let $M$ be the
random walk transition matrix of $G$. Let $1>\xi>1/n^{5}$, $t\geq\frac{20\log
n}{\varphi^{2}}$. Let $c>1$ be a large enough constant and let $s\geq c\cdot
k^{4}\cdot n^{(400\epsilon/\varphi^{2})}\cdot\log n/(\eta^{2}\cdot\xi^{2})$.
Let $I_{S}=\\{i_{1},\ldots,i_{s}\\}$ be a multiset of $s$ indices chosen
independently and uniformly at random from $\\{1,\dots,n\\}$. Let $S$ be the
$n\times s$ matrix whose $j$-th column equals $\mathds{1}_{i_{j}}$. Suppose
that $M^{t}=U\Sigma^{t}U^{T}$ is the eigendecomposition of $M^{t}$ and
$\sqrt{\frac{n}{s}}\cdot
M^{t}S=\widetilde{U}\widetilde{\Sigma}\widetilde{W}^{T}$ is the SVD of
$\sqrt{\frac{n}{s}}\cdot M^{t}S$. If
$\frac{\epsilon}{\varphi^{2}}\leq\frac{1}{10^{5}}$ then with probability at
least $1-n^{-100\cdot k}$ we have

$\left|\left|U_{[k]}{\Sigma}_{[k]}^{-2t}U_{[k]}^{T}-\widetilde{U}_{[k]}\widetilde{\Sigma}_{[k]}^{-2}\widetilde{U}_{[k]}^{T}\right|\right|_{2}<\xi$

The following lemma from [GKL+21] is instrumental in analyzing collision
probabilities of random walks from every vertex $x\in V$ in a
$(k,\varphi,\epsilon)$-clusterable graph. In our setup however, the collision
probabilities increase by a factor of $1/\eta$ because of uneven size of
clusters.

######  Lemma 24.

[GKL+21] Let $k\geq 2$ be an integer, $\varphi\in(0,1)$ and
$\epsilon\in(0,1)$. Let $G=(V,E)$ be a $d$-regular and that admits a
$(k,\varphi,\epsilon)$-clustering $C_{1},\ldots,C_{k}$. Let
$\eta=\frac{\min_{i\in[k]}|C_{i}|}{\max_{i\in[k]}|C_{i}|}$. Let $M$ be the
random walk transition matrix of $G$. For any $t\geq\frac{20\log
n}{\varphi^{2}}$ and any $x\in V$ we have

$\|M^{t}\mathds{1}_{x}\|_{2}\leq O\left(\frac{k}{\sqrt{\eta}}\cdot
n^{-1/2+20\epsilon/\varphi^{2}}\right)\text{.}$

To prove the correctness of weighted dot product of spectral embedding of
vertices, we use the similar proof strategy to [GKL+21], which, albeit,
develops an estimator for the _unweighted_ dot product between spectral
embeddings i.e., $\left\langle f_{x},f_{y}\right\rangle$. In Lemma 25, we show
that the weighted dot product of spectral embeddings i.e., $\left\langle
f_{x},\Sigma_{[k]}f_{y}\right\rangle$ can be estimated by the appropriate
linear transformation of the random walk transition matrix. Since we seek
weighted dot products unlike [GKL+21], we run a $t$-step random walk from $x$,
and a $t+1$-step walk from $y$. The one-step longer walk helps us to inject
the matrix of eigenvalues in between the dot product of spectral embedding of
vertex $x$ and $y$.

######  Lemma 25.

Let $k\geq 2$ be an integer, $\varphi\in(0,1)$ and $\epsilon\in(0,1)$. Let
$G=(V,E)$ be a $d$-regular graph that admits a
$(k,\varphi,\epsilon)$-clustering $C_{1},\ldots C_{k}$. Let
$\eta=\frac{\min_{i\in[k]}|C_{i}|}{\max_{i\in[k]}|C_{i}|}$. Let $M$ be the
random walk transition matrix of $G$. Let $1/n^{5}<\xi<1$, $t\geq\frac{20\log
n}{\varphi^{2}}$. Let $c>1$ be a large enough constant and let $s\geq c\cdot
n^{480\epsilon/\varphi^{2}}\cdot\log n\cdot k^{8}/(\eta^{4}\cdot{\xi}^{2})$.
Let $I_{S}=\\{i_{1},\ldots,i_{s}\\}$ be a multiset of $s$ indices chosen
independently and uniformly at random from $\\{1,\dots,n\\}$. Let $S$ be the
$n\times s$ matrix whose $j$-th column equals $\mathds{1}_{i_{j}}$. Let
$M^{t}=U\Sigma^{t}U^{T}$ be the eigendecomposition of $M^{t}$ and
$\sqrt{\frac{n}{s}}\cdot
M^{t}S=\widetilde{U}\widetilde{\Sigma}\widetilde{W}^{T}$ be the SVD of
$\sqrt{\frac{n}{s}}\cdot M^{t}S$. If
$\frac{\epsilon}{\varphi^{2}}\leq\frac{1}{10^{5}}$ then with probability at
least $1-n^{-100\cdot k}$ we have

$\left|\mathds{1}_{x}^{T}U_{[k]}\Sigma_{[k]}{U}_{[k]}^{T}\mathds{1}_{y}-(M^{t+1}\mathds{1}_{x})^{T}(M^{t}S)\left(\frac{n}{s}\cdot\widetilde{W}_{[k]}\widetilde{\Sigma}^{-4}_{[k]}\widetilde{W}^{T}_{[k]}\right)(M^{t}S)^{T}(M^{t}\mathds{1}_{y})\right|\leq\frac{\xi}{n}\text{.}$

###### Proof.

Let $m_{x}=M^{t+1}\mathds{1}_{x}$ and $m_{y}=M^{t}\mathds{1}_{y}$. Let
$c^{\prime}>1$ be a large enough constant we will set later. Let
$\xi^{\prime}=\frac{\xi\cdot\eta}{c^{\prime}\cdot k^{2}\cdot
n^{40\epsilon/\varphi^{2}}}$. Let $c_{1}$ be the constant in front of $s$ in
Lemma 23. Thus for large enough $c$ we have $s\geq c\cdot
n^{480\epsilon/\varphi^{2}}\cdot\log n\cdot k^{8}/(\eta^{4}\cdot{\xi}^{2})\geq
c_{1}\cdot n^{400\epsilon/\varphi^{2}}\cdot\log n\cdot
k^{4}/(\eta^{2}\cdot{\xi^{\prime}}^{2})$, and therefore by Lemma 23 applied
with $\xi^{\prime}$, with probability at least $1-n^{-100\cdot k}$ we have

$\left|\left|U_{[k]}{\Sigma}_{[k]}^{-2t}U_{[k]}^{T}-\widetilde{U}_{[k]}\widetilde{\Sigma}_{[k]}^{-2}\widetilde{U}_{[k]}^{T}\right|\right|_{2}\leq\xi^{\prime}$

By Cauchy-Schwarz and submultiplicativity of the spectral norm we have

$\displaystyle\left|m_{x}^{T}U_{[k]}{\Sigma}_{[k]}^{-2t}U_{[k]}^{T}m_{y}-m_{x}^{T}\widetilde{U}_{[k]}\widetilde{\Sigma}_{[k]}^{-2}\widetilde{U}_{[k]}^{T}m_{y}\right|$
$\displaystyle\leq\left|\left|U_{[k]}{\Sigma}_{[k]}^{-2t}U_{[k]}^{T}-\widetilde{U}_{[k]}\widetilde{\Sigma}_{[k]}^{-2}\widetilde{U}_{[k]}^{T}\right|\right|_{2}\|m_{x}\|_{2}\|m_{y}\|_{2}$
$\displaystyle\leq\xi^{\prime}\|m_{x}\|_{2}\|m_{y}\|_{2}$ (60)

In the rest of the proof we will show
$m_{x}^{T}(U_{[k]}{\Sigma}_{[k]}^{-2t}U_{[k]}^{T})m_{y}=\mathds{1}_{x}^{T}U_{[k]}\Sigma_{[k]}U_{[k]}^{T}\mathds{1}_{y}$
(Step 1) and
$m_{x}^{T}\widetilde{U}_{[k]}\widetilde{\Sigma}^{-2}_{[k]}\widetilde{U}_{[k]}^{T}m_{y}=m_{x}^{T}(M^{t}S)(\widetilde{W}_{[k]}\widetilde{\Sigma}^{-4}_{[k]}\widetilde{W}^{T}_{[k]})(M^{t}S)^{T}m_{y}$
(Step 2), and finally obtain the result by combining these facts with (60) and
the upper bound on $\|m_{x}\|_{2}$ provided by Lemma 24.

##### Step $1$:

Note that $M^{t}=U\Sigma^{t}U^{T}$. Therefore we get
$M^{t+1}\mathds{1}_{x}=U\Sigma^{t+1}U^{T}\mathds{1}_{x}$, and
$M^{t}\mathds{1}_{y}=U\Sigma^{t}U^{T}\mathds{1}_{y}$. Thus we have

$m_{x}^{T}U_{[k]}{\Sigma}_{[k]}^{-2t}U_{[k]}^{T}m_{y}=\mathds{1}_{x}^{T}\left(\left(U\Sigma^{t+1}U^{T}\right)\left(U_{[k]}{\Sigma}_{[k]}^{-2t}U_{[k]}^{T}\right)\left(U\Sigma^{t}U^{T}\right)\right)\mathds{1}_{y}$
(61)

Note that $U^{T}U_{[k]}$ is a $n\times k$ matrix such that the top $k\times k$
matrix is $I_{k\times k}$ and the rest is zero. Also $U_{[k]}^{T}U$ is a
$k\times n$ matrix such that the left $k\times k$ matrix is $I_{k\times k}$
and the rest is zero. Therefore we have

$U{\Sigma}^{t+1}\left(U^{T}U_{[k]}\right){\Sigma}^{-2t}_{[k]}\left(U^{T}_{[k]}U\right){\Sigma}^{t}U^{T}=UHU^{T}\text{,}$

where $H$ is a $n\times n$ matrix such that the top left $k\times k$ matrix is
$\Sigma_{k\times k}$ and the rest is zero. Hence, we have

$UHU^{T}=U_{[k]}\Sigma_{[k]}U_{[k]}^{T}\text{.}$

Thus we have

$m_{x}^{T}(U_{[k]}{\Sigma}_{[k]}^{-2t}U_{[k]}^{T})m_{y}=\mathds{1}_{x}^{T}U_{[k]}\Sigma_{[k]}U_{[k]}^{T}\mathds{1}_{y}$
(62)

##### Step $2$:

We have $\sqrt{\frac{n}{s}}\cdot
M^{t}S=\widetilde{U}\widetilde{\Sigma}\widetilde{W}^{T}$ where
$\widetilde{U}\in\mathbb{R}^{n\times n}$,
$\widetilde{\Sigma}\in\mathbb{R}^{n\times n}$ and
$\widetilde{W}\in\mathbb{R}^{s\times n}$. Therefore,

$\displaystyle(m_{x})^{T}(M^{t}S)\left(\frac{n}{s}\cdot\widetilde{W}_{[k]}\widetilde{\Sigma}^{-4}_{[k]}\widetilde{W}^{T}_{[k]}\right)(M^{t}S)^{T}(m_{y})$
$\displaystyle=m_{x}^{T}\left(\sqrt{\frac{s}{n}}\cdot\widetilde{U}\widetilde{\Sigma}\widetilde{W}^{T}\right)\left(\frac{n}{s}\cdot\widetilde{W}_{[k]}\widetilde{\Sigma}^{-4}_{[k]}\widetilde{W}^{T}_{[k]}\right)\left(\sqrt{\frac{s}{n}}\cdot\widetilde{W}\widetilde{\Sigma}\widetilde{U}^{T}\right)m_{y}$
$\displaystyle=m_{x}^{T}\left(\widetilde{U}\widetilde{\Sigma}\widetilde{W}^{T}\right)\left(\widetilde{W}_{[k]}\widetilde{\Sigma}^{-4}_{[k]}\widetilde{W}^{T}_{[k]}\right)\left(\widetilde{W}\widetilde{\Sigma}\widetilde{U}^{T}\right)m_{y}$
(63)

Note that $\widetilde{W}^{T}\widetilde{W}_{[k]}$ is a $n\times k$ matrix such
that the top $k\times k$ matrix is $I_{k\times k}$ and the rest is zero. Also
$\widetilde{W}_{[k]}^{T}\widetilde{W}$ is a $k\times n$ matrix such that the
left $k\times k$ matrix is $I_{k\times k}$ and the rest is zero. Therefore we
have

$\widetilde{\Sigma}\left(\widetilde{W}^{T}\widetilde{W}_{[k]}\right)\widetilde{\Sigma}^{-4}_{[k]}\left(\widetilde{W}^{T}_{[k]}\widetilde{W}\right)\widetilde{\Sigma}=\widetilde{H}\text{,}$

where $\widetilde{H}$ is a $n\times n$ matrix such that the top left $k\times
k$ matrix is $\widetilde{\Sigma}^{-2}_{[k]}$ and the rest is zero. Hence, we
have

$(\widetilde{U}\widetilde{\Sigma}\widetilde{W}^{T})\left(\frac{n}{s}\cdot\widetilde{W}_{[k]}\widetilde{\Sigma}^{-4}_{[k]}\widetilde{W}^{T}_{[k]}\right)(\widetilde{W}\widetilde{\Sigma}\widetilde{U}^{T})=\widetilde{U}\widetilde{H}\widetilde{U}^{T}=\widetilde{U}_{[k]}\widetilde{\Sigma}^{-2}_{[k]}\widetilde{U}_{[k]}^{T}$
(64)

Putting (64) and (A.1) together we get

$m_{x}^{T}(M^{t}S)(\widetilde{W}_{[k]}\widetilde{\Sigma}^{-4}_{[k]}\widetilde{W}^{T}_{[k]})(M^{t}S)^{T}m_{y}=m_{x}^{T}\widetilde{U}_{[k]}\widetilde{\Sigma}^{-2}_{[k]}\widetilde{U}_{[k]}^{T}m_{y}$
(65)

##### Putting it together.

By (60), (62) and (65) we have

$\displaystyle\left|m_{x}^{T}(M^{t}S)\left(\frac{n}{s}\cdot\widetilde{W}_{[k]}\widetilde{\Sigma}^{-4}_{[k]}\widetilde{W}^{T}_{[k]}\right)(M^{t}S)^{T}m_{y}-\mathds{1}_{x}^{T}U_{[k]}{U}_{[k]}^{T}\mathds{1}_{y}\right|$
$\displaystyle=\left|m_{x}^{T}\widetilde{U}_{[k]}\widetilde{\Sigma}_{[k]}^{-2}\widetilde{U}_{[k]}^{T}m_{y}-m_{x}^{T}U_{[k]}{\Sigma}_{[k]}^{-2t}U_{[k]}^{T}m_{y}\right|$
By (62) and (65)
$\displaystyle\leq\xi^{\prime}\cdot\|m_{x}\|_{2}\|m_{y}\|_{2}$ By (60) (66)

By Lemma 24 for any vertex $x\in V$ we have

$\|m_{x}\|^{2}_{2}=\|M^{t}\mathds{1}_{x}\|^{2}_{2}\leq
O\left(\frac{k^{2}}{\eta}\cdot n^{-1+40\epsilon/\varphi^{2}}\right)\text{.}$
(67)

Therefore by choice of $c^{\prime}$ as a large enough constant and choosing
$\xi^{\prime}=\frac{\xi\cdot\eta}{c^{\prime}\cdot k^{2}\cdot
n^{40\epsilon/\varphi^{2}}}$ we have

$\left|m_{x}^{T}(M^{t}S)\left(\frac{n}{s}\cdot\widetilde{W}_{[k]}\widetilde{\Sigma}^{-4}_{[k]}\widetilde{W}^{T}_{[k]}\right)(M^{t}S)^{T}m_{y}-\mathds{1}_{x}^{T}U_{[k]}\Sigma_{[k]}{U}_{[k]}^{T}\mathds{1}_{y}\right|\leq
O\left(\xi^{\prime}\cdot\frac{k^{2}}{\eta}\cdot
n^{-1+40\epsilon/\varphi^{2}}\right)\leq\frac{\xi}{n}\text{.}$ (68)

∎

Fix $t\geq\frac{\log n}{\varphi^{2}}$. We will use the following result, which
is a corollary of a Kim-Vu like bound (Theorem 12) we show in Section B.

######  Corollary 4.

Let $k\geq 2$. Suppose $G$ is a $d$-regular graph which admits a
$(k,\varphi,\epsilon)$-clustering $C_{1},\ldots C_{k}$. Let
$\eta=\frac{\min_{i\in[k]}|C_{i}|}{\max_{i\in[k]}|C_{i}|}$. Let $M$ be the
random walk transition matrix of $G$. Let $0<\sigma_{err}\leq 1/n$. Let
$a,b\in V$. Suppose that we run $R$ random walks of length $t$ from $a$ and
$b$. For any $x\in V$, let $\widehat{m}_{a}(x)$ (resp. $\widehat{m}_{b}(x)$)
be a random variable which denotes the fraction out of the $R$ walks from $a$
(resp. $b$) which end in $x$. Then on choosing

$R\geq\left(k^{3}\cdot\displaystyle\frac{n^{-3/2+60(\epsilon/\varphi^{2})}}{\eta^{3/2}\cdot\sigma_{err}^{2}}\right)\cdot(100\cdot\log
n)^{4}$

with probability at least $1-n^{-99k}$, it holds that

$|\widehat{m}_{a}^{T}\widehat{m}_{b}-(M^{t}\mathds{1}_{a})^{T}(M^{t}\mathds{1}_{b})|\leq\sigma_{err}.$

Finally, Lemma 26 bounds the absolute deviation between $\left\langle
f_{x},\Sigma_{[k]}f_{y}\right\rangle_{\scriptscriptstyle apx}$ and our
estimator. We put the two together using triangle inequality to prove Theorem
8.

######  Lemma 26.

Let $G=(V,E)$ be a $d$-regular that admits a $(k,\varphi,\epsilon)$-clustering
$C_{1},\ldots C_{k}$. Let
$\eta=\frac{\min_{i\in[k]}|C_{i}|}{\max_{i\in[k]}|C_{i}|}$. Let
$0<\delta<1/2$, and $1/n^{5}<\xi<1$. Let $\mathcal{D}$ denote the data
structure constructed by Algorithm InitializeOracle($G,\delta,\xi$) (Algorithm
14). Let $x,y\in V$. Let $\left\langle
f_{x},\Sigma_{[k]}f_{y}\right\rangle_{\scriptscriptstyle apx}\in\mathbb{R}$
denote the value returned by
$\textsc{WeightedDotProductOracle}(G,x,y,\xi,\mathcal{D})$ (Algorithm 14). Let
$t\geq\frac{20\log n}{\varphi^{2}}$. Let $c>1$ be a large enough constant and
let $s\geq\frac{c\cdot n^{240\cdot\epsilon/\varphi^{2}}\cdot\log n\cdot
k^{4}}{\eta^{2}}$. Let $I_{S}=\\{i_{1},\ldots,i_{s}\\}$ be a multiset of $s$
indices chosen independently and uniformly at random from $\\{1,\dots,n\\}$.
Let $S$ be the $n\times s$ matrix whose $j$-th column equals
$\mathds{1}_{i_{j}}$. Let $M$ be the random walk transition matrix of $G$. Let
$\sqrt{\frac{n}{s}}\cdot
M^{t}S=\widetilde{U}\widetilde{\Sigma}\widetilde{W}^{T}$ be the SVD of
$\sqrt{\frac{n}{s}}\cdot M^{t}S$. If
$\frac{\epsilon}{\varphi^{2}}\leq\frac{1}{10^{5}}$, and Algorithm 14 succeeds,
then with probability at least $1-n^{-99k}$ we have

$\left|\left\langle f_{x},\Sigma_{[k]}f_{y}\right\rangle_{\scriptscriptstyle
apx}-(M^{t+1}\mathds{1}_{x})^{T}(M^{t}S)\left(\frac{n}{s}\cdot\widetilde{W}_{[k]}\widetilde{\Sigma}^{-4}_{[k]}\widetilde{W}^{T}_{[k]}\right)(M^{t}S)^{T}(M^{t}\mathds{1}_{y})\right|<\frac{\xi}{n}\text{.}$

######  Remark 5.

The result in Gluch et al. above, obtains a success probability of at least
$1-n^{-100}$. It can be improved to $1-n^{-99k}$ using Corollary 4.

We now prove Theorem 8.

###### Proof of Theorem 8.

Correctness: Let $s=\varTheta{(n^{480\epsilon/\varphi^{2}}\cdot\log n\cdot
k^{8}/(\eta^{4}\cdot\xi^{2}))}$. Recall that $I_{S}=\\{i_{1},\ldots,i_{s}\\}$
is the multiset of $s$ vertices each sampled uniformly at random (see line 4
of Algorithm 14). Let $S$ be the $n\times s$ matrix whose $j$-th column equals
$\mathds{1}_{i_{j}}$. Recall that $M$ is the random walk transition matrix of
$G$. Let $\sqrt{\frac{n}{s}}\cdot
M^{t}S=\widetilde{U}\widetilde{\Sigma}\widetilde{W}^{T}$ be the
eigendecomposition of $\sqrt{\frac{n}{s}}\cdot M^{t}S$. We define

$e_{1}=\left|(M^{t+1}\mathds{1}_{x})^{T}(M^{t}S)\left(\frac{n}{s}\cdot\widetilde{W}_{[k]}\widetilde{\Sigma}^{-4}_{[k]}\widetilde{W}^{T}_{[k]}\right)(M^{t}S)^{T}(M^{t}\mathds{1}_{y})-\mathds{1}_{x}^{T}U_{[k]}\Sigma_{[k]}{U}_{[k]}^{T}\mathds{1}_{y}\right|$

and

$e_{2}=\left|\left\langle
f_{x},\Sigma_{[k]}f_{y}\right\rangle_{\scriptscriptstyle
apx}-(M^{t+1}\mathds{1}_{x})^{T}(M^{t}S)\left(\frac{n}{s}\cdot\widetilde{W}_{[k]}\widetilde{\Sigma}^{-4}_{[k]}\widetilde{W}^{T}_{[k]}\right)(M^{t}S)^{T}(M^{t}\mathds{1}_{y})\right|$

By triangle inequality we have

$\left|\left\langle f_{x},\Sigma_{[k]}f_{y}\right\rangle_{\scriptscriptstyle
apx}-\langle f_{x},\Sigma_{[k]}f_{y}\rangle\right|=\left|\left\langle
f_{x},\Sigma_{[k]}f_{y}\right\rangle_{\scriptscriptstyle
apx}-\mathds{1}_{x}^{T}U_{[k]}\Sigma_{[k]}{U}_{[k]}^{T}\mathds{1}_{y}\right|\leq
e_{1}+e_{2}\text{.}$

Let $\xi^{\prime}=\xi/2$. Let $c$ be a constant in front of $s$ in Lemma 25
and $c^{\prime}$ be a constant in front of $s$ in Lemma 26. Recall, line 3 of
Algorithm 14 sets $s=\varTheta{(n^{480\epsilon/\varphi^{2}}\cdot\log n\cdot
k^{8}/(\eta^{4}\cdot\xi^{2}))}$. Since
$\frac{\epsilon}{\varphi^{2}}\leq\frac{1}{10^{5}}$ and $s\geq c\cdot
n^{480\epsilon/\varphi^{2}}\cdot\log n\cdot k^{8}/(\eta^{4}\cdot\xi^{\prime
2})$, by Lemma 25 with probability at least $1-n^{-100\cdot k}$ we have
$e_{1}\leq\frac{\xi^{\prime}}{n}=\frac{\xi}{2\cdot n}\text{.}$ Since
$s\geq\frac{c^{\prime}\cdot n^{240\epsilon/\varphi^{2}}\cdot\log n\cdot
k^{4}}{\eta^{2}}$, by Lemma 26, with probability at least $1-2\cdot
n^{-100\cdot k}$ we have $e_{2}\leq\frac{\xi}{2\cdot n}\text{.}$ Thus with
probability at least $1-3\cdot n^{-100\cdot k}$ we have

$\left|\left\langle f_{x},\Sigma_{[k]}f_{y}\right\rangle_{\scriptscriptstyle
apx}-\langle f_{x},\Sigma_{[k]}f_{y}\rangle\right|\leq
e_{1}+e_{2}\leq\frac{\xi}{2\cdot n}+\frac{\xi}{2\cdot
n}\leq\frac{\xi}{n}\text{.}$

Running time of InitializeOracle: The algorithm first samples a set $I_{S}$.
Then, as per line 5 of Algorithm 14, it estimates the empirical probability
distribution of $t$-step random walks starting from any vertex $x\in I_{S}$.
The EstimateTransitionMatrix procedure runs $R_{\text{init}}$ random walks of
length $t$ from each vertex $x\in I_{S}$. So it takes $O(\log n\cdot s\cdot
R_{\text{init}}\cdot t)$ time and requires $O(\log n\cdot s\cdot
R_{\text{init}})$ space to store endpoints of random walks. Then as per line 6
of Algorithm 14 it estimates matrix $\mathcal{G}$ such that the entry
corresponding to the $x^{\text{th}}$ row and $y^{\text{th}}$ column of
$\mathcal{G}$ is an estimation of pairwise collision probability of random
walks starting from $x,y\in I_{S}$. To compute $\mathcal{G}$ we call Algorithm
EstimateCollisionProbabilities($G,I_{S},R_{\text{init}},t$) (from [GKL+21])
for $O(\log n)$ times. This procedure takes $O(s\cdot R_{\text{init}}\cdot
t\cdot\log n)$ time and it requires $O(s^{2}\cdot\log n)$ space to store
matrix $\mathcal{G}$. Computing the SVD of $\mathcal{G}$ (done in line 7 of
Algorithm 14) takes time $O(s^{3})$. Thus overall Algorithm 14 runs in time
$O\left(\log n\cdot s\cdot R_{\text{init}}\cdot t+s^{3}\right)$. Thus, by
choice of $t=\varTheta\left(\frac{\log n}{\varphi^{2}}\right)$,
$R_{\text{init}}=\varTheta{(n^{1/2+O(\epsilon/\varphi^{2})}\cdot\log^{O(1)}n\cdot
k^{O(1)}/(\eta\cdot\xi)^{O(1)})}$ and
$s=\varTheta(n^{O(\epsilon/\varphi^{2})}\cdot(\log n)^{O(1)}\cdot
k^{O(1)}/{\xi}^{O(1)})$ as in Algorithm 14 we get that Algorithm 14 runs in
time $\log n\cdot s\cdot R_{\text{init}}\cdot t+s^{3}=(\frac{k\cdot\log
n}{\eta\cdot\xi\cdot\varphi})^{O(1)}\cdot n^{1/2+O(\epsilon/\varphi^{2})}$ and
returns a data structure of size $O\left(s^{2}+\log n\cdot s\cdot
R_{\text{init}}\right)=(\frac{k\cdot\log n}{\eta\cdot\xi})^{O(1)}\cdot
n^{1/2+O(\epsilon/\varphi^{2})}\text{.}$

Running time of WeightedDotProductOracle: Algorithm WeightedDotProductOracle
runs $R_{\text{query}}$ random walks of length $t,t+1$ from vertex $x$ and
vertex $y$, then it computes $(\widehat{m}_{x}^{T}\widehat{Q})$ and
$(\widehat{Q}^{T}\widehat{m}_{y})$. Since $\widehat{Q}\in\mathbb{R}^{n\times
s}$ has $s$ columns and since $\widehat{m}_{x}$ has at most $R_{\text{query}}$
non-zero entries, thus one can compute $\widehat{m}_{x}^{T}\cdot\widehat{Q}$
in time $R_{\text{query}}\cdot s$. Finally Algorithm 15 returns value
$(\widehat{m}_{x}^{T}\widehat{Q})\Psi(\widehat{Q}^{T}\widehat{m}_{y})$. Since
$(\widehat{m}_{x}^{T}\widehat{Q}),(\widehat{Q}^{T}\widehat{m}_{y})\in\mathbb{R}^{s}$
and $\Psi\in\mathbb{R}^{s\times s}$ one can compute
$(\widehat{m}_{x}^{T}\widehat{Q})\Psi(\widehat{Q}^{T}\widehat{m}_{y})$ in time
$O(s^{2})$. Thus overall Algorithm 15 takes $O\left(t\cdot
R_{\text{query}}+s\cdot R_{\text{query}}+s^{2}\right)$ time. Thus, by choice
of $t=O\left(\frac{\log n}{\varphi^{2}}\right)$ ,
$R_{\text{query}}=n^{1/2+O(\epsilon/\varphi^{2})}\cdot\left(\frac{k}{\eta\cdot\xi}\right)^{O(1)}$
and $s=n^{O(\epsilon/\varphi^{2})}\cdot(\frac{k\cdot\log
n}{\eta\cdot\xi})^{O(1)}$ we get that the Algorithm 15 runs in time
$(\frac{k\cdot\log n}{\eta\cdot\xi\cdot\varphi})^{O(1)}\cdot
n^{1/2+O(\epsilon/\varphi^{2})}$. ∎

###  A.2 Proof of Lemma 3 and Lemma 5

See 3

###### Proof.

Let $a=\mathds{1}_{A}^{T}\cdot(U_{[k]}\Sigma_{[k]}^{1/2})$ and
$b=(\Sigma_{[k]}^{1/2}U_{[k]}^{T})\mathds{1}_{B}$. This allows us to write the
first term on LHS of Equation (5) as $\langle a,b\rangle$. Analogously, define
$a^{\prime}=\frac{|A|}{|S_{A}|}\cdot\mathds{1}_{S_{A}}^{T}\cdot(U_{[k]}\Sigma_{[k]}^{1/2})$
and
$b^{\prime}=\frac{|B|}{|S_{B}|}\cdot(\Sigma_{[k]}^{1/2}U_{[k]}^{T})\mathds{1}_{S_{B}}$
so that the second term on LHS of Equation (5) can be written as $\langle
a^{\prime},b^{\prime}\rangle$. With this setup, we have the following:

$\displaystyle\left|\langle a,b\rangle-\langle
a^{\prime},b^{\prime}\rangle\right|=\left|\langle
a,b-b^{\prime}\rangle+\langle
a-a^{\prime},b^{\prime}\rangle\right|\leq\|a\|_{2}\|b-b^{\prime}\|_{2}+\|a-a^{\prime}\|_{2}\|b^{\prime}\|_{2}$
(69)

where the last inequality follows by triangle inequality and Cauchy-Schwarz.
Now by expanding out $a$ we get

$a=\sum_{x\in
A}\mathds{1}_{x}^{T}\left(U_{[k]}\Sigma_{[k]}^{1/2}\right)\text{.}$

We show this quantity is estimated coordinate wise very well by the vector
$a^{\prime}\in\mathbb{R}^{k}$ defined as follows:

$a^{\prime}=\frac{|A|}{|S_{A}|}\cdot\sum_{x\in
S_{A}}\mathds{1}_{x}^{T}\left(U_{[k]}\Sigma_{[k]}^{1/2}\right)\text{.}$

Note that for all $i\in[k]$ we have $\mathbb{E}[a^{\prime}(i)]=a(i)$. For any
$i\in[k]$ we first show that with high probability $|a(i)-a^{\prime}(i)|$ is
small, then by union bound we prove that $||a^{\prime}-a||$ is small. Note
that for every $i\in[k]$ we have $a(i)=\sum_{x\in A}\sqrt{\sigma_{i}}\cdot
u_{i}(x)$, where $u_{i}$ is the $i$-th eigenvector of $M$ and $\sigma_{i}$ is
the $i$-th eigenvalue of $M$. For every $x\in S_{A}$, let $Z_{x}$ be a random
variable defined as $Z_{x}=|A|\cdot\sqrt{\sigma_{i}}\cdot u_{i}(x)$. Thus, we
have $a^{\prime}(i)=\frac{1}{S_{A}}\cdot\sum_{x\in S_{A}}Z_{x}$, and
$a(i)=\frac{1}{S_{A}}\cdot\sum_{x\in S_{A}}\mathbb{E}[Z_{x}]$. Therefore, by
Hoeffding Bound (Fact 3), we have

$\text{Pr}\left[|a^{\prime}(i)-a(i)|\geq
t\right]\leq\exp\left(\frac{-2|S_{A}|\cdot t^{2}}{\left(2\cdot\max_{x\in
S_{A}}|Z_{x}|\right)^{2}}\right)$ (70)

Next we need to bound $\max_{x\in S_{A}}|Z_{x}|$. Note that for every
$i\in[k]$ and every $x\in V$ we have

$\displaystyle|Z_{x}|$
$\displaystyle=|A|\cdot\sqrt{\sigma_{i}}\cdot|u_{i}(x)|$
$\displaystyle\leq|A|\cdot||u_{i}||_{\infty}$ As
$\sigma_{i}=1-\frac{\lambda_{i}}{2}\leq 1$
$\displaystyle=|A|\cdot\frac{n^{20\epsilon/\varphi^{2}}}{\sqrt{\min_{i\in
k}|C_{i}|}}$ By Lemma 4 $\displaystyle\leq\frac{|A|\cdot
n^{20\epsilon/\varphi^{2}}}{\sqrt{\eta\cdot\frac{n}{k}}}$ As $\min_{i\in
k}|C_{i}|=\eta\cdot\max_{i\in k}|C_{i}|\geq\eta\cdot\frac{n}{k}$ (71)

Let $w_{A}=\frac{|A|\cdot
n^{20\epsilon/\varphi^{2}}}{\sqrt{\eta\cdot\frac{n}{k}}}$ and
$\beta=\frac{\xi\cdot\sqrt{\eta}}{2\cdot k\cdot n^{20\epsilon/\varphi^{2}}}$.
Therefore, by (70) and (A.2) we have

$\displaystyle\text{Pr}\left[|a^{\prime}(i)-a(i)|\geq\beta\cdot
w_{A}\right]\leq\exp\left(\frac{-2|S_{A}|\cdot(\beta\cdot w_{A})^{2}}{4\cdot
w_{A}^{2}}\right)=\exp\left(-|S_{A}|\beta^{2}/2\right)\leq n^{-200k}\text{,}$

where the last inequality holds by choice of $|S_{A}|\geq\frac{1600\cdot
k^{3}\cdot n^{40\epsilon/\varphi^{2}}\cdot\log n}{\xi^{2}\cdot\eta}\geq
400\cdot k\cdot\log n\cdot\frac{1}{\beta^{2}}$. Thus, by a union bound over
all $i\in[k]$, with probability at least $1-k\cdot n^{-200k}$ we have

$||a-a^{\prime}||_{2}=\sqrt{\sum_{i=1}^{k}(a^{\prime}(i)-a(i))^{2}}\leq\sqrt{k}\cdot\beta\cdot
w_{A}$ (72)

A similar analysis shows that with probability at least $1-k\cdot n^{-200k}$
we have

$||b-b^{\prime}||_{2}\leq\sqrt{k}\cdot\beta\cdot w_{B}\text{,}$ (73)

where, $w_{B}=\frac{|B|\cdot
n^{20\epsilon/\varphi^{2}}}{\sqrt{\eta\cdot\frac{n}{k}}}$. Also note that

$\displaystyle||a||_{2}$
$\displaystyle=\left|\left|\mathds{1}_{A}^{T}\left(U_{[k]}\Sigma_{[k]}^{1/2}\right)\right|\right|_{2}$
$\displaystyle\leq\left|\left|\mathds{1}_{A}^{T}\right|\right|_{2}\cdot\left|\left|U_{[k]}\right|\right|_{2}\cdot\left|\left|\Sigma_{[k]}^{1/2}\right|\right|_{2}$
$\displaystyle\leq\sqrt{|A|}\cdot\max_{i\in[k]}\sqrt{\sigma_{i}}$ As
$||U_{[k]}||_{2}=1$, and $\Sigma$ is diagonal $\displaystyle\leq\sqrt{n}$ As
$\sigma_{i}=1-\frac{\lambda_{i}}{2}\leq 1$ (74)

Similarly we have

$||b||_{2}\leq\sqrt{n}$ (75)

Thus by (69) we get

$\displaystyle\|a\|_{2}\|b-b^{\prime}\|_{2}+\|a-a^{\prime}\|_{2}\|b^{\prime}\|_{2}$
$\displaystyle\leq\sqrt{k\cdot n}\cdot\beta\cdot(w_{A}+w_{B})$ By (72), (73),
(A.2), (75) $\displaystyle\leq\xi\cdot n$ As $w_{A}+w_{B}\leq\frac{2\cdot
n\cdot n^{20\epsilon/\varphi^{2}}}{\sqrt{\eta\cdot\frac{n}{k}}}$ and
$\beta=\frac{\xi\cdot\sqrt{\eta}}{2\cdot k\cdot n^{20\epsilon/\varphi^{2}}}$

Therefore, with probability at least $1-2\cdot k\cdot n^{-200k}\geq
1-n^{-100k}$ we have

$\left|\mathds{1}_{A}^{T}\cdot(U_{[k]}\Sigma_{[k]}U_{[k]}^{T})\
\mathds{1}_{B}\
-\frac{|A|\cdot|B|}{|S_{A}|\cdot|S_{B}|}\cdot\mathds{1}_{S_{A}}^{T}(U_{[k]}\Sigma_{[k]}U_{[k]}^{T})\mathds{1}_{S_{B}}\right|\leq\xi\cdot
n$

∎

######  Fact 3.

(Hoeffding Bounds) Let $Z_{1},Z_{2},\cdots Z_{n}$ be iid random variables with
$Z_{i}\in[a,b]$ for all $i\in[n]$ where $-\infty\leq a\leq b\leq\infty$. Then

$\displaystyle\text{Pr}\left[\frac{1}{n}\cdot\sum|(Z_{i}-\mathbb{E}[Z_{i}])|\geq
t\right]\leq\exp(-2nt^{2}/(b-a)^{2}),\text{ and}$
$\displaystyle\text{Pr}\left[\frac{1}{n}\cdot\sum|(Z_{i}-\mathbb{E}[Z_{i}])|\leq
t\right]\leq\exp(-2nt^{2}/(b-a)^{2})$

Finally, we prove lemma 5. See 5

###### Proof.

Let $s=|S|$. For $x\in V$, and $r\in[s]$, let $Y_{x}^{r}$ be a random variable
which is $1$ if the $r$-th sampled vertex is $v$, and $0$ otherwise. Thus
$\mathbb{E}[Y_{x}^{r}]=\frac{1}{n}$. Observe that $|S_{i}|=|S\cap C_{i}|$ is a
random variable defined as $\sum_{r=1}^{s}\sum_{x\in C_{i}}Y_{x}^{r}$ where
its expectation is given by

$\mathbb{E}[|S\cap C_{i}|]=\sum_{r=1}^{s}\sum_{x\in C_{i}}Y_{x}^{r}\geq
s\cdot\frac{|C_{i}|}{n}\geq s\cdot\frac{\eta}{k}\text{,}$

where, the last inequality holds since
$\min_{j\in[k]}|C_{j}|=\eta\cdot\max_{j\in[k]}|C_{j}|\geq\eta\cdot\frac{n}{k}$.
Notice that the random variables $Y_{x}^{r}$ are negatively associated, since
for each $r$, $\sum_{x\in V}Y_{x}^{r}=1$. Therefore, by Chernoff bound,

$\text{Pr}\left[\left||S\cap C_{i}|-\frac{|C_{i}|}{n}\right|>\delta\cdot
s\cdot\frac{|C_{i}|}{n}\right]\leq
2\cdot\text{exp}\left(-\frac{\delta^{2}}{3}\cdot\frac{s\cdot\eta}{k}\right)\leq
n^{-120\cdot k}\text{,}$

where, the last inequality holds by choice of $s\geq\frac{400\cdot\log n\cdot
k^{2}}{\eta\cdot\delta^{2}}$. Therefore, by union bound,

$\text{Pr}\left[\exists i:\left||S\cap
C_{i}|-\frac{|C_{i}|}{n}\right|>\delta\cdot s\cdot\frac{|C_{i}|}{n}\right]\leq
2\cdot k\cdot n^{-120\cdot k}\leq n^{-100\cdot k}\text{.}$

∎

###  A.3 Estimate Cluster Sizes

In this section, we present routines to estimate cluster sizes in
RandomSampleModel and OracleModel.

Algorithm 16 $\textsc{EstimateClusterSize}(G,i,\delta)$
# (Assuming clustering oracle using RandomSampleModel or OracleModel)

1: $s\leftarrow\frac{400\cdot\log n\cdot k^{2}}{\eta\cdot\delta^{2}}$

2: $S\leftarrow$ (multi)set of $s$ i.i.d random vertices together with their
cluster label

3: $S_{i}\leftarrow S\cap C_{i}$ # (Can find $S_{i}$ using the clustering
oracle)

4: $\widehat{c_{i}}\leftarrow\frac{|S_{i}|}{s}\cdot n$

######  Lemma 27.

Let $k\geq 2$, $\varphi,\delta\in(0,1)$, and $\frac{\epsilon}{\varphi^{2}}$ be
smaller than a positive sufficiently small constant. Let $G=(V,E)$ be a
$d$-regular graph that admits a $(k,\varphi,\epsilon)$-clustering
$C_{1},\ldots,C_{k}$. Let
$\eta=\frac{\min_{i\in[k]}|C_{i}|}{\max_{i\in[k]}|C_{i}|}$. Then in the
RandomSampleModel or OracleModel procedure
$\textsc{EstimateClusterSize}(G,i,\delta)$ (Algorithm 16) runs in time
$O\left(\frac{\log n\cdot k^{2}}{\eta\cdot\delta^{2}}\right)$ and with
probability at least $1-n^{-100\cdot k}$ for every $i\in[k]$ returns a value
$\widehat{c_{i}}$ such that $\widehat{c_{i}}\in(1\pm\delta)\cdot|C_{i}|$.

###### Proof.

By Lemma 5. ∎

###  A.4 Proof of Lemma 6

See 6

###### Proof.

Note that as per line (5), (6) and (7) of Algorithm 1 we have

$\textsc{QuadraticOracle}(G,z,\xi,\mathcal{D})=d\cdot\left(\frac{\xi\cdot
n}{2}+\frac{n}{s}\cdot\sum_{i\in[k]}\sum_{x\in
S_{i}}z_{i}^{2}-\frac{n^{2}}{s^{2}}\cdot\sum_{i,j\in[k]}\sum_{x\in S_{i},y\in
S_{j}}z_{i}z_{j}\cdot\left\langle
f_{x},\Sigma_{[k]}f_{y}\right\rangle_{\scriptscriptstyle apx}\right)\text{,}$
(76)

where $\left\langle f_{x},\Sigma_{[k]}f_{y}\right\rangle_{\scriptscriptstyle
apx}=\textsc{WeightedDotProductOracle}(G,x,y,\xi^{\prime},\mathcal{D})$ and
$\xi^{\prime}=\frac{\xi}{8\cdot k^{2}}$ as per line (4). We define matrix
$K\in\mathbb{R}^{k\times k}$ as follows:

$\displaystyle K_{i,j}=\begin{cases}\frac{\xi\cdot d\cdot n}{2}+\frac{d\cdot
n\cdot|S_{i}|}{s}-\frac{d\cdot n^{2}}{s^{2}}\cdot\sum_{x,y\in
S_{i}}\left\langle f_{x},\Sigma_{[k]}f_{y}\right\rangle_{\scriptscriptstyle
apx}\text{ {} {} if }i=j\\\ \frac{-d\cdot n^{2}}{s^{2}}\cdot\sum_{x\in
S_{i},y\in S_{j}}\left\langle
f_{x},\Sigma_{[k]}f_{y}\right\rangle_{\scriptscriptstyle apx}\text{ {} {}
otherwise.}\end{cases}$ (77)

Note that by (76) and (77) for every $z\in\mathbb{R}^{k}$ we have

$\textsc{QuadraticOracle}(G,z,\xi,\mathcal{D})=z^{T}Kz\text{,}$

also, by (77) observe that $K$ is symmetric. Finally, we show that probability
at least $1-n^{-100\cdot k}$, $\|K^{\prime}\|_{F}^{2}\leq O(n^{4})$. By
Theorem 8 with probability at least $1-n^{-100\cdot k}$ for all $x,y\in V$ we
have

$|\left\langle f_{x},\Sigma_{[k]}f_{y}\right\rangle_{\scriptscriptstyle
apx}-\left\langle
f_{x},\Sigma_{[k]}f_{y}\right\rangle|\leq\frac{\xi^{\prime}}{n}$ (78)

Therefore, with probability at least $1-n^{-100\cdot k}$ for every $i,j\in[k]$
we have

$\displaystyle\left|\frac{d\cdot n^{2}}{s^{2}}\cdot\sum_{x\in S_{i},y\in
S_{j}}\left\langle f_{x},\Sigma_{[k]}f_{y}\right\rangle_{\scriptscriptstyle
apx}\right|$ $\displaystyle\leq\frac{d\cdot n^{2}}{s^{2}}\cdot\sum_{x\in
S_{i},y\in S_{j}}\left|\left\langle
f_{x},\Sigma_{[k]}f_{y}\right\rangle_{\scriptscriptstyle apx}\right|$ By
triangle inequality $\displaystyle\leq\frac{d\cdot
n^{2}}{s^{2}}\cdot\sum_{x\in S_{i},y\in S_{j}}\left|\left\langle
f_{x},\Sigma_{[k]}f_{y}\right\rangle\right|+\frac{\xi^{\prime}}{n}$ By Theorem
8 $\displaystyle\leq\frac{d\cdot n^{2}}{s^{2}}\cdot s^{2}\left(\max_{x,y\in
V}|\left\langle f_{x},\Sigma_{[k]}f_{y}\right\rangle|+\frac{1}{n}\right)$ As
$\xi^{\prime}\leq\xi\leq 1$ and $|S_{i}|,|S_{j}|\leq s$ $\displaystyle=d\cdot
n^{2}\cdot\max_{x,y\in
V}||f_{x}||_{2}\cdot||\Sigma_{[k]}||_{2}\cdot||f_{y}||_{2}+d\cdot n$
$\displaystyle\leq d\cdot n^{2}\cdot\max_{x\in V}||f_{x}||_{2}^{2}+d\cdot n$
As
$||\Sigma_{[k]}||_{2}=\max_{i\in[k]}\left(1-\frac{\lambda_{i}}{2}\right)\leq
1$ $\displaystyle\leq d\cdot n^{2}\cdot k+d\cdot n$ As
$||f_{x}||_{2}^{2}=\sum_{i=1}^{k}u_{i}^{2}(x)\leq k$ $\displaystyle\leq 2\cdot
d\cdot n^{2}\cdot k$ (79)

Thus by (77) and (A.4) for every $i,j\in[k]$ we have

$|K_{i,j}|\leq\frac{\xi\cdot d}{n}+\frac{d\cdot n\cdot|S_{i}|}{s}+2\cdot
d\cdot n^{2}\cdot k\leq 3\cdot d\cdot n^{2}\cdot k\text{,}$ (80)

where, the last inequality holds as $\xi\leq 1$, $|S_{i}|\leq s$. Therfore,
with probability at least $1-3\cdot n^{-100\cdot k}\geq 1-n^{-99\cdot k}$ we
have

$||K||_{F}\leq\sqrt{k^{2}\cdot\left(3\cdot d\cdot n^{2}\cdot k\right)^{2}}\leq
2\cdot d\cdot n^{2}\cdot k^{2}\leq 2\cdot n^{5}.$

∎

###  A.5 Proof of Claim 1

See 1

###### Proof.

We present such an instance $G$ explicitly. We pick a large enough integer
$m$. Let $X_{1}=\\{1,2,\cdots,m-2\epsilon m\\}$ denote the set of first
$m-2\epsilon m$ integers and use standard constructions to obtain an $d-1$
regular $\varphi\cdot d$-expander on vertices in $X_{1}$. Also, let
$Y_{1}=\\{m-2\epsilon m+1,m-2\epsilon m+2,\cdots m\\}$ denote another set of
$2\epsilon m$ integers and obtain another $d-1$ regular $\varphi\cdot d$
expander on $Y_{1}$. Put a matching of size $\epsilon\varphi dm$ between the
sets $X_{1}$ and $Y_{1}$. Also, put a matching on remaining degree $d-1$
vertices in $X_{1}$. Notice that $|E(X_{1},Y_{1})|=\epsilon\varphi dm$. Let
$C_{1}=X_{1}\cup Y_{1}$. Now we describe another set of vertices. This time we
consider three sets: $X_{2}=\\{1,2,\cdots,m-4\epsilon m\\}$,
$Y_{2}=\\{m-4\epsilon m+1,\cdots m-2\epsilon m\\}$ and $Z_{2}=\\{m-2\epsilon
m+1,\cdots,m\\}$. We again obtain a $d-1$ regular $\varphi\cdot d$ expander on
all of these sets. Next, add a matching of size $\epsilon\varphi dm$ between
$X_{2}$ and $Y_{2}$ and between $X_{2}$ and $Z_{2}$. We add a matching between
remaining degree $d-1$ vertices in $X_{2}$ and another matching between
remanining degree $d-1$ vertices in $Z_{2}$. Notice that
$|E(X_{2},Y_{2})|=\epsilon\varphi dm=|E(X_{2},Z_{2})|$. Next, let
$C_{2}=X_{2}\cup Y_{2}\cup Z_{2}$.

Finally, we add a matching between the remaining degree $d-1$ vertices in
$Y_{1}$ and $Y_{2}$. Overall this gives a $d$-regular graph on $2m$ vertices.
We let $B=C_{1}$ and thus $\overline{B}=C_{2}$. Notice that
$\varphi_{\text{out}}(C_{1})=\varphi_{\text{out}}(C_{2})=\epsilon$. Also, by
construction, note that
$\varphi_{\text{in}}(C_{1})=\varphi_{\text{in}}(C_{2})\geq\varphi$. Now
consider the following set $S=X_{1}\cup Z_{2}$. We see that

$|E(S,\overline{S})|=|E(X_{1},Y_{1})|+|E(X_{2},Z_{2})|=2\epsilon\varphi dm.$

Also $|S|=|X_{1}|+|Z_{2}|=m$. And therefore, it holds that
$\phi(G)\leq\phi(S)=2\epsilon\varphi$. ∎

##  Appendix B Proof of Corollary 4 : A Kim-Vu bound

In this section, we prove a Kim-Vu ([KV00]) like bound that was used in
Section A.1. This is our key tool in proving Corollary 4. We reproduce the
statement for convenience of the reader. See 4

Thus, the end goal in Corollary 4 is to obtain concentration bounds on the
collision probability of random walks from $a$ and $b$. We do this by showing
concentration bounds on the following degree $2$ (squarefree) _collision-
counting polynomial_ :

$Z=\sum_{\begin{subarray}{c}i,j\in[R]\\\ w\in V\end{subarray}}\prod
X_{i,w}Y_{j,w}.$

Here $X_{i,w}$ is an indicator random variable which takes the value $1$ when
the $i$th random walk from $a$ ends at $w$ and $Y_{j,w}$ is another indicator
variable which is $1$ when the $j$th random walk from $b$ ends at $w$.
Concentration bounds for such polynomials can be shown using an approach given
by Kim and Vu. This approach exploits a bijection between squarefree
polynomials $Z$ in $N$ indicator variables with maximum degree $h$ and
(weighted) hypergraphs $H_{Z}$ of maximum arity $h$ on $N$ vertices. The
distribution on any vertex of $H_{Z}$ is identical to the distribution on the
corresponding variable of the polynomial. This is setup so that concentration
bounds on the total weight of hyperedges induced by a random sample of
vertices in $H_{Z}$ implies a concentation bound on the value taken by the
polynomial $Z$. However, in the Kim-Vu setup, each vertex $v$ is included in
the sample as a result of a Bernoulli trial $Ber(p_{v})$ independent of other
vertices.

The collision-counting polynomial $Z$ defined above differs from this setup in
one key respect. We consider end point distributions of $t$-step random walks
from $a,b\in V$. Focus on one such walk from (say) $a$. Note that the number
of possible end points for this walk is $n$. In all we take $R$ samples from
the end point distribution of walks from $a$. As opposed to the standard Kim-
Vu setup, our end point distributions are not Bernoulli random variables (and
have support size $n$ in particular). Because of this, we need to adapt the
Kim-Vu machinery towards proving Corollary 4 above.

We begin our adaptation with some setup. Let $V$ denote a set of size $n$ and
take $R\in\mathbb{N}$. We consider the following weighted hypergraph
$H=(\mathcal{V},\mathcal{E},w)$. We index elements of $\mathcal{V}$ by a pair
$(i,w)\in[R]\times V$. In particular, the pair $(i,w)$ refers to vertex $w\in
V_{i}$ (which is a copy of $V$). The hypergraph has an edge set $\mathcal{E}$
where for any $e\in\mathcal{E}$, it holds that $e$ contains at most one vertex
from any $V_{i}$ (for any $i\in[R]$). That is, if for some $i$, it holds that
$(i,z)\in e$ then for any $z^{\prime}\neq z$ we have $(i,z^{\prime})\not\in
e$. Finally, for $e\in\mathcal{E}$, $w(e)$ denotes the weight of the edge $e$.
We also suppose that the maximum arity of any hyperedge is at most some small
constant $h$. That is,

$\max_{e\in\mathcal{E}}|e|\leq h.$

Now, consider the probability space $(\Omega,\mathcal{D})$ where
$\Omega=V^{R}$ and $\mathcal{D}=D_{1}\times D_{2}\cdots\times D_{R}$ is a
product measure on $\Omega$. Here the distribution $D_{i}$ is supported on
$V_{i}$ (which we recall is a copy of $V$). Now consider sampling
$\omega\sim_{\mathcal{D}}\Omega$. We would like to show Kim-Vu style
concentration bounds on the total weight of hyperedges induced by the sample
$\omega$. To state the concentration bound we seek, we need the following
definitions.

######  Definition 20.

Let $H=(\mathcal{V},\mathcal{E},w)$ denote a hypergraph with maximum arity at
most $h$ as defined above. We define a random variable $Y:\Omega\to\mathbb{R}$
as follows:

$Y=Y_{H}=\sum_{e\in\mathcal{E}}w(e)\prod_{(i,w)\in e}t_{i,w}$

Here, for each $i\in[R]$, we have a distribution $D_{i}$ is supported over
$V$. The events $(t_{i,w}=1)_{w\in V}$ are mutually exclusive and the event
$t_{i,w}=1$ occurs with probability $D_{i}(w)$. Note that $Y$ is a polynomial
in the indicator variables $(t_{i,w})_{(i,w)\in[R]\times V}$ and that
$deg(Y)\leq h$.

Next, following Kim-Vu, we define the notion of a truncated hypergraph.

######  Definition 21.

(Truncated subhypergraph and Truncated polynomial) For each
$A\subseteq\mathcal{V}(H)$, we define the hypergraph truncated to $A$ (denoted
$H_{A}$) as follows:

  * –

$\mathcal{V}(H_{A})=\mathcal{V}(H)\setminus A$.

  * –

$\mathcal{E}(H_{A})=\\{B\subseteq\mathcal{V}(H_{A}),B\cup
A\in\mathcal{E}(H)\\}$.

  * –

For $B\in\mathcal{E}(H_{A})$, $w(B)=w(B\cup A)$.

Also, we define the polynomial truncated to $A$ as

$Y_{H_{A}}=\sum_{e\in\mathcal{E}\text{~{}s.t.~{}}A\subseteq
e}w(e)\prod_{(i,w)\in e\setminus A}t_{i,w}.$

If $A$ is the singleton $\\{(i,z)\\},(i,z)\in[R]\times V$, then we denote the
hypergraph truncated to $H$ by $H_{(i,z)}$.

######  Definition 22.

For $A\subseteq\mathcal{V}(H)$, write $E_{A}=\mathbb{E}[Y_{H_{A}}]$. Now
define $E_{i}[H]=\max_{|A|=i}E_{A}$. Note that with this notation, note
$E_{0}[H]=\mathbb{E}[Y_{H}]$. We finally let $E_{H}=\max_{i\geq 0}E_{i}[H]$
and let $E^{\prime}_{H}=\max_{i\geq 1}E_{i}[H]$. When $H$ is clear from the
context, for $i\geq 0$, we will often use $E_{i}$ (instead of $E_{i}[H]$ by
dropping $H$) to make our notation simpler.

Now, we state the analog of main theorem from Kim-Vu adapted to the above
setup.

######  Theorem 12.

Let $H=(\mathcal{V},\mathcal{E},w)$ denote a hypergraph with maximum arity at
most $h$ where $\mathcal{V}=[R]\times V$. Write $\Omega=V^{R}$ and let
$(\Omega,D_{1}\times D_{2}\times\cdots\times D_{R})$ denote the associated
probability space. Let $Y_{H}=\sum_{e\in\mathcal{E}}\prod_{(i,w)\in e}t_{i,w}$
denote a polynomial random variable defined with respect to $H$ where for
every $i\in[R]$, we have a distribution $D_{i}$ supported over $V$. The events
$(t_{i,w}=1)_{w\in V}$ are mutually exclusive and the event $t_{i,w}=1$ occurs
with probability $D_{i}(w)$. Then, we have

$Pr(|Y_{H}-\mathbb{E}[Y_{H}]|\geq
a_{h}(E_{H}E^{\prime}_{H})^{1/2}\eta^{h})\leq O(\exp(-\eta+(h-1)\log(Rn)))$

for any $\eta>1$ and $a_{h}=8^{h}h!^{1/2}$.

######  Remark 6.

Note that without loss of generality, we may assume that for any $i\in[R]$ and
for all $z,z^{\prime}\in V$ it holds that no $e\in\mathcal{E}(H)$ contains
both $(i,z)$ and $(i,z^{\prime})$. This is because the probability that a
random $\omega\sim\mathcal{D}$ contains both $(i,z)$ and $(i,z^{\prime})$ is
zero.

We now show how Kim-Vu bounds can be used to prove Corollary 4.

####  B.0.1 Proof of Corollary 4

In this section, we show how to use the Kim-Vu like bound proved in Section B
to establish Corollary 4.

We will need some setup. Take a finite set $V$ with $|V|=n$ and take
$R\in\mathbb{N}$. We consider a probability space $\Omega=V^{2R}$ which is
equipped with the product measure $m_{a}^{R}\times m_{b}^{R}$. That is, we
have $2R$ disjoint copies of $V$. The first $R$ of these are equipped with
$m_{a}$ and the last $R$ are equipped with $m_{b}$. Here
$m_{a}=M^{t}\mathds{1}_{a}$ and $m_{b}=M^{t}\mathds{1}_{b}$ are end point
distributions of $t$-step random walks from $a$ and $b$ respectively. We
consider the following unweighted hypergraph $H=(\mathcal{V},\mathcal{E})$.
Here $\mathcal{V}=[2R]\times V$ is just the disjoint union of the $2R$ copies
of $V$. For any $(i,w)\in[R]\times V$ we connect it to $(j,w)$ where
$j\in\\{R+1,R+2,\cdots,2R\\}$. Thus all the copies of $V$ equipped with
$m_{a}$ are connected via perfect matchings to all copies of $V$ that are
equipped with $m_{b}$.

For $i\leq R$, let $X_{(i,w)}$ be an indicator random variable which is $1$
iff the sample from the $i$th copy of $V$ is $w$ (alternatively, in the
$i^{th}$ copy of $V$, a $t$-length walk started at $a$ ends at $w$).
Similarly, for $R<j\leq 2R$, define indicator variables $Y_{(j,w)}$ which are
associated with samples taken from $m_{b}$. Let $S$ denote the set of $2R$
vertices which get picked in this process. That is,

$S=\left\\{X_{(i,w)}:X_{(i,w)}=1\text{ where }i\in[R],w\in
V(G)\right\\}\cup\left\\{Y_{(j,w)}:Y_{(j,w)}=1\text{ where }R<j\leq 2R,w\in
V(G)\right\\}$

We now define the following polynomial in the indicator variables $X_{i,w}$
and $Y_{j,w}$

$Z_{H}=\sum_{e=\\{(i,w),(j,w)\\}\in\mathcal{E}(H)}\prod X_{i,w}Y_{j,w}.$

Following the notation in B, we have the following claims.

######  Claim 7.

Consider the preceding setup. The following all hold.

  * •

$E_{0}\leq R^{2}\max(\|m_{a}\|_{2}^{2},\|m_{b}\|_{2}^{2})$.

  * •

$E_{1}\leq R\max(\|m_{a}\|_{2},\|m_{b}\|_{2})$.

  * •

$E_{2}=1$.

  * •

$E_{r}=0$ for all $r\geq 3$.

###### Proof.

We prove the first item.

$\displaystyle E_{0}=\mathbb{E}[Z_{H}]$
$\displaystyle=\sum_{\begin{subarray}{c}i\in[R],j\in\\{R+1,\cdots,2R\\}\\\
w\in V\end{subarray}}\mathbb{E}[X_{i}(w)\cdot Y_{j}(w)]$
$\displaystyle=\sum_{\begin{subarray}{c}i\in[R],j\in\\{R+1,\cdots,2R\\}\\\
w\in V\end{subarray}}\mathbb{E}[X_{i}(w)]\cdot\mathbb{E}[Y_{j}(w)]$
$\displaystyle=R^{2}\langle m_{a},m_{b}\rangle$ $\displaystyle\leq
R^{2}\cdot\max(\|m_{a}\|_{2}^{2},\|m_{b}\|_{2}^{2}).$

Now, we consider the second item above. For ease of notation, write
$A=[R]\times V$ and $B=\\{R+1,\cdots,2R\\}\times V$. Write
$val_{1}=\max_{(j,w)\in B}\mathbb{E}[Z_{(j,w)}]$ and $val_{2}=\max_{(i,w)\in
A}\mathbb{E}[Z_{(i,w)}]$. Note that $E_{1}=\max(val_{1},val_{2})$. We
upperbound $val_{1}$ first, the upperbound on $val_{2}$ follows similarly.
Choose any $j,w\in B$. Note that

$\displaystyle\mathbb{E}[Z_{(j,w)}]$
$\displaystyle=\sum_{i\in[R]}\mathbb{E}[X_{(i,w)}]$
$\displaystyle=R\mathbb{E}[X_{(1,w)}]=Rm_{a}(w)\leq R\|m_{a}\|_{\infty}\leq
R\|m_{a}\|_{2}$

Similarly $val_{2}\leq R\|m_{b}\|_{2}$ which means $E_{1}\leq
R\max\left(\|m_{a}\|_{2},\|m_{b}\|_{2}\right)$.

For item 3, we pick $u,v\in A\cup B$. Note that $E_{\\{u,v\\}}=0$ when $u,v\in
A$ or $u,v\in B$. Moreover, for $(i,u)\in A$ and $(j,v)\in B$, if
$\\{u,v\\}\not\in\mathcal{E}(H)$ then also we have that $E_{\\{u,v\\}}=0$.
Finally when $(i,u)\in A$, $(j,v)\in B$ and $\\{u,v\\}\in\mathcal{E}(H)$ we
get that $E_{\\{u,v\\}}=1$ which also means $E_{2}=1$.

The last item is immediate as all edges have arity $2$. ∎

######  Claim 8.

Choose $R\geq\sqrt{n}$. Then the following holds $E_{H}\leq
R^{2}\cdot\max(\|m_{a}\|_{2}^{2},\|m_{b}\|_{2}^{2})$ (where $E_{H}$ is as
defined in Definition 22).

###### Proof.

This proof follows by using Claim 7 and the premise. Recall that
$E_{H}=\max_{i\geq 0}E_{i}=\max(E_{0},E_{1},E_{2})$. Note that
$\|m_{a}\|_{2}\geq\frac{1}{\sqrt{n}}$ since $m_{a}$ is a distribution
supported on a set of size $n$ (and the same holds for $m_{b}$). Thus, on
setting $R\geq\sqrt{n}$, it follows that both $R\cdot\|m_{a}\|_{2}\geq 1$ and
$R\cdot\|m_{b}\|_{2}\geq 1$. Since $E_{2}=1$, we see that both $E_{1}$ and
$E_{2}$ are at most

$\alpha=R\cdot\max(\|m_{a}\|_{2},\|m_{b}\|_{2}).$

Note that $\alpha\geq 1$. Thus, $\alpha^{2}\geq\alpha$. Moreover, from Claim
7, it holds that $E_{0}\leq\alpha^{2}$. In all, this means that
$E_{H}=\max(E_{0},E_{1},E_{2})\leq\alpha^{2}\leq
R^{2}\cdot\max(\|m_{a}\|_{2}^{2},\|m_{b}\|_{2}^{2})$. ∎

######  Claim 9.

Choose $R\geq\sqrt{n}$. Then the following holds
$E^{\prime}_{H}\leq\max(R\|m_{a}\|_{2},R\|m_{b}\|_{2})$ (where
$E^{\prime}_{H}$ is as defined in Definition 22).

###### Proof.

The proof is identical to the one used for Claim 8. ∎

Let $p_{a,b}:=\mathds{1}_{a}^{T}M^{2t}\mathds{1}_{b}$ for any $a,b\in V$
denote the collision probability of $t$-step random walks from $a$ and $b$.
Now, we are ready to prove Corollary 4.

###### Proof.

(Of Corollary 4) Note that $p_{a,b}=\mathbb{E}[Z_{H}]/R^{2}=\langle
m_{a},m_{b}\rangle$. Write $\widehat{p}_{a,b}=Z_{H}/R^{2}$. Apply Theorem 12
with $h=2$ (and note that $8^{h}\cdot h!^{1/2}\leq 100$ when $h=2$). This
gives

$Pr(|Z_{H}-E_{H}|\geq(E_{H}E^{\prime}_{H})^{1/2}(100k\log n)^{2})\leq
n^{-100k}\cdot 2Rn.$

We note that on setting $\sigma_{err}\leq 1/n$, it holds that

$R\geq\left(k^{3}\cdot\displaystyle\frac{n^{-3/2+60(\epsilon/\varphi^{2})}}{\eta^{3/2}\cdot\sigma_{err}^{2}}\right)\cdot(100k\log
n)^{4}\geq\sqrt{n}.$

Thus, we can apply Claim 8 and conclude that $E_{H}\leq
R^{2}\max(\|m_{a}\|_{2}^{2},\|m_{b}\|_{2}^{2})$ from Claim 8. This gives

$Pr\left(|Z_{H}-E_{H}|>R\left(\max(\|m_{a}\|_{2},\|m_{b}\|_{2})\right)\cdot\sqrt{E^{\prime}_{H}}\cdot(100k\log
n)^{2}\right)\leq n^{-100k}\cdot 2Rn.$

Together with $Z_{H}=R^{2}\widehat{m}_{a,b}$, this means

$Pr\left(|p_{a,b}-\widehat{p}_{a,b}|>\frac{1}{R^{2}}\cdot\left(R\max(\|m_{a}\|_{2},\|m_{b}\|_{2})\right)\cdot\sqrt{E^{\prime}_{H}}\cdot(100k\log
n)^{2}\right)\leq n^{-100k}\cdot 2Rn.$

Again, since $R\geq\sqrt{n}$, we apply Claim 9 and obtain
$E^{\prime}_{H}\leq\max(R\|m_{a}\|_{2},R\|m_{b}\|_{2})$. Substituting this
bound on $E^{\prime}_{H}$, we get

$\displaystyle n^{-100k}\cdot 2Rn$ $\displaystyle\geq
Pr\left(|p_{a,b}-\widehat{p}_{a,b}|>\frac{\max(\|m_{a}\|_{2},\|m_{b}\|_{2})}{R}\cdot\sqrt{R\max(\|m_{a}\|_{2},\|m_{b}\|_{2})}\cdot(100k\log
n)^{2}\right)$
$\displaystyle=Pr\left(|p_{a,b}-\widehat{p}_{a,b}|>\frac{(\max(\|m_{a}\|_{2},\|m_{b}\|_{2}))^{3/2}}{\sqrt{R}}\cdot(100k\log
n)^{2}\right)$ $\displaystyle\geq
Pr\left(|p_{a,b}-\widehat{p}_{a,b}|>\frac{k^{3/2}\cdot n^{-3/4}\cdot
n^{30\epsilon/\varphi^{2}}\cdot\left(\frac{1}{\eta}\right)^{3/4}}{\sqrt{R}}\cdot(100k\log
n)^{2}\right)$

Here the last step follows using Lemma 24.

Plugging in $R\geq
k^{3}\cdot\displaystyle\frac{n^{-3/2+60(\epsilon/\varphi^{2})}}{\eta^{3/2}\cdot\sigma_{err}^{2}}\cdot(100k\log
n)^{4}$, from the premise, it again follows

$Pr\left(|p_{a,b}-\widehat{p}_{a,b}|\geq\sigma_{err}\right)\leq n^{-100k}\cdot
2Rn\leq n^{-99k}$

∎

####  B.0.2 The Computational Model

Denote $Y=Y_{H}$ and write

$\mathbb{E}[Y]=\sum_{\omega\in\Omega}Y(\omega)\mathcal{D}(\omega)=\sum_{\omega\in
V^{R}}Y(\omega)\prod_{i\in[R]}D_{i}(\omega_{i}).$

It is convenient to represent the outcome $\omega\in V^{R}$ of the above
random process using the following tree $T$ of depth $R$. The tree is defined
level by level. The tree helps us view the output $\omega$ of the above
sampling procedure one coordinate at a time as it is revealed. At the $i$th
level of the tree, we sample a vertex $\omega_{i}\sim V$ from the distribution
$D_{i}$. Thus, the set of leaves of $T$ is precisely the set $\Omega$. Let
$\omega^{i}$ denote the vector containing first $i$ coordinates of $\omega$.
The following notation will be used later.

######  Definition 23.

(Conditional expectation) For a node $\omega^{i}$ at level $i\in[R]$, we let

$\mathbb{E}[\omega^{i}]:=\mathbb{E}_{\widetilde{\omega}\sim\mathcal{D}}[Y|\widetilde{\omega}^{i}=\omega^{i}]=\sum_{\widetilde{\omega}:\widetilde{\omega}^{i}=\omega^{i}}Y(\widetilde{\omega})\prod_{j=i+1}^{R}D_{j}(\widetilde{\omega}_{j}).$

Also for vectors $v,w$ of length $i$ and $j$, let $(v,w)$ denote the vector of
length $i+j$ obtained by writing $v$ followed by $w$. One key benefit of using
the tree $T$ is that it can be used to track how the expected value fluctuates
on taking samples according to the distribution $D_{i}$ at the $i$th level
conditioned on the decisions so far. This is explored in the next section.

####  B.0.3 Small Fluctuations result in good concentration

Let us introduce some definitions.

######  Definition 24.

(Fluctuations and Absolute fluctuations) Fix a leaf $\omega\in T$. For
$i\in[R]$, $z\in V$, let

$\mu_{i,z}(\omega):=\mathbb{E}[(\omega^{i-1},z)]-\mathbb{E}[\omega^{i-1}]=\mathbb{E}_{\widetilde{\omega}\sim\mathcal{D}}[Y|\widetilde{\omega}^{i}=(\omega^{i-1},z)]-\mathbb{E}_{\widetilde{\omega}\sim\mathcal{D}}[Y|\widetilde{\omega}^{i-1}=\omega^{i-1}].$

denote the fluctuation in expected value of $Y$ having fixed the first $i-1$
coordinates according to $\omega^{i-1}$ and setting $\omega_{i}=z$. Following
Kim-Vu, we also define absolute fluctuations
$c_{i,z}(\omega)=|\mu_{i,z}(\omega)|$. For $i\in[R]$, and a leaf $\omega$ of
$T$, we also define $c_{i}(\omega)=\max_{z\in V}c_{i,z}(\omega)$. Also, it is
convenient to define $c(\omega)=\max_{i}\max_{z}|c_{i,z}(\omega)|$. Let
$c_{Y}=\max_{\omega\in\Omega}c(\omega)$.

For $\omega\in\Omega$, we define the following.

######  Definition 25.

(Two norm of the fluctuation) For a leaf $\omega\in\Omega$, for $i\in[R]$ let
us define

$V_{i}(\omega)=\sum_{z\in V}D_{i}(z)\mu_{i,z}(\omega)^{2}.$

We also define $V(\omega)=\sum_{i=1}^{R}V_{i}(\omega)$ and
$V_{Y}=\max_{\omega\in\Omega}V(\omega)$.

Now we adapt a key theorem from Kim-Vu which is a key tool in proving Theorem
12.

######  Theorem 13.

If $c^{\prime}\geq c_{Y}$ and $V^{\prime}\geq V_{Y}$ and
$0<\eta<V^{\prime}/(c^{\prime})^{2}$, then $Pr(|Y-\mathbb{E}[Y]|\geq\left(\eta
V^{\prime}\right)^{1/2})<2\exp(-\eta/4)$

###### Proof.

We first show that one can assume, w.log that $\mathbb{E}[Y]=0$. To see this,
take any constant $\alpha$ and note that all the values
$\\{\mu_{i,z}\\}_{i\in[R],z\in V}$ for the polynomial $Y$ are identical to
those for the polynomial $Y+\alpha$. Therefore, all the absolute fluctuations
$\\{c_{i,z}(\omega)\\}_{i\in[R],z\in V}$ and the two norm of fluctuations
$\\{V_{i}(\omega)\\}_{i\in[R]}$ are the same as well. In particular, this
holds for $\alpha=-\mathbb{E}[Y]$. So, we can indeed assume that
$\mathbb{E}[Y]=0$. Now following Kim-Vu, note that for any $x>0$,

$\displaystyle Pr(Y\geq(\eta V^{\prime})^{1/2})$ $\displaystyle=Pr(e^{xY}\geq
e^{x(\eta V^{\prime})^{1/2}})$
$\displaystyle\leq\frac{\mathbb{E}[e^{xY}]}{e^{x(\eta V^{\prime})^{1/2}}}$

Lemma 28 shows that for $x<1/c_{Y}$, we have $\mathbb{E}[e^{xY}]\leq
e^{x^{2}V_{Y}}$. We choose $x=\frac{1}{2}(\eta/V^{\prime})^{1/2}$ whereupon it
indeed holds that $x<1/c^{\prime}\leq 1/c_{Y}$. For this choice of $x$, Lemma
28 gives

$Pr(Y\geq(\eta V^{\prime})^{1/2})\leq e^{x^{2}V_{Y}}\cdot e^{-x(\eta
V^{\prime})^{1/2}}\leq e^{x^{2}V^{\prime}-x(\eta
V^{\prime})^{1/2}}=e^{-\eta/4}.$

By symmetry, we similarly obtain a bound for the lower tail which in all gives
$Pr(|Y|\geq(\eta V^{\prime})^{1/2})\leq 2\exp(-\eta/4)$. This finishes the
proof. ∎

Now, we state and prove Lemma 28 used in the previous proof.

######  Lemma 28.

If $0<x<1/c_{Y}$ and $\mathbb{E}[Y]=0$, then $\mathbb{E}[e^{xY}]\leq
e^{x^{2}V_{Y}}$.

###### Proof.

We adapt the proof of the same lemma given on page 5 of Kim-Vu [KV00]. We use
induction on $R$. The case $R=0$ is trivial. Suppose $R\geq 1$. Fix
$\omega,\omega^{\prime}\in\Omega$. Now, fix any $z\in V$. Note that we have

$\displaystyle\mu_{1,z}(\omega)$
$\displaystyle=\mathbb{E}[Y|\omega_{1}=z]-\mathbb{E}[Y]=\mu_{1,z}(\omega^{\prime})$

This means, $\mu_{1,z}$ is a constant function over $\Omega$ for any choice of
the first level vertex $z$. So, we drop $\omega$ and write $\mu_{1,z}$ in
place of $\mu_{1,z}(\omega)$ from now on. Armed with this notation, note

$V_{1}(\omega)=\sum_{z\in V}D_{1}(z)\mu_{1,z}^{2}=V_{1}(\omega^{\prime})$ (81)

also holds for all $\omega,\omega^{\prime}\in\Omega$. We denote this constant
value as $V_{1}$ (and again drop $\omega$ from now on).

Consider the function $Y-\mu_{1,z}$ assigned to the subtree rooted at the
child of root labeled by $z\in V$. Denote this tree as $T_{z}$. This subtree
has height $R-1$. Moreover, note that

$\mathbb{E}[Y-\mu_{1,z}|\omega_{1}=z]=\mathbb{E}[Y|\omega_{1}=z]-\mu_{1,z}=0.$
(82)

Now, we use induction hypothesis on the tree $T_{z}$. For any $z\in V$, this
gives

$\mathbb{E}[e^{x(Y-\mu_{1,z})}]\leq e^{x^{2}\cdot
V_{Y-\mu_{1,z}}}=e^{x^{2}(V_{Y}-V_{1})}.$

Therefore, by conditioning on the value of $\omega_{1}$, we get

$\displaystyle\mathbb{E}[e^{xY}]$ $\displaystyle=\sum_{z\in V}D_{1}(z)\cdot
e^{x\mu_{1,z}}\cdot\mathbb{E}[e^{x(Y-\mu_{1,z})}]$
$\displaystyle\leq\sum_{z\in V}D_{1}(z)\cdot e^{x\mu_{1,z}}\cdot
e^{x^{2}(V_{Y}-V_{1})}$

It remains to show that $\sum_{z\in V}D_{1}(z)e^{x\mu_{1,z}}\leq
e^{x^{2}V_{1}}$. Again following Kim-Vu, we take Taylor expansion of the LHS
above. This gives

$\displaystyle\sum_{z\in V}D_{1}(z)e^{x\mu_{1,z}}$ $\displaystyle=\sum_{z\in
V}D_{1}(z)\left(1+x\mu_{1,z}+x^{2}\mu_{1,z}^{2}/2+\cdots\right)$
$\displaystyle=1+x\sum_{z\in V}D_{1}(z)\cdot\mu_{1,z}+\sum_{i\geq
2}\frac{1}{i!}\sum_{z\in V}D_{1}(z)\cdot(x\mu_{1,z})^{i}$
$\displaystyle=1+x\sum_{z\in
V}D_{1}(z)\cdot\mathbb{E}[Y|\omega_{1}=z]+x^{2}\cdot\sum_{i\geq
2}\frac{1}{i!}\sum_{z\in V}D_{1}(z)\mu_{1,z}^{2}\cdot(x\mu_{1,z})^{i-2}$ (83)

We will bound the two terms in Equation (83) separately. Denote the two terms
as $T_{1}$ and $T_{2}$. For the first term $T_{1}$, note that, since we assume
without loss of generality that $\mathbb{E}[Y]=0$,

$T_{1}=\sum_{z\in V}D_{1}(z)\cdot\mathbb{E}[Y|\omega_{1}=z]=\mathbb{E}[Y]=0.$
(85)

We now consider the second term of Equation (83). It will be convenient to
define a distribution $\mathcal{P}$ supported on $V$ where
$\mathcal{P}(z)=\frac{D_{1}(z)\mu_{1,z}^{2}}{V_{1}}$. Note that this is a bona
fide distribution by Equation (81) which defines $V_{1}$ above.

$\displaystyle T_{2}$ $\displaystyle=x^{2}\cdot\sum_{i\geq
2}\frac{1}{i!}\sum_{z\in V}D_{1}(z)\mu_{1,z}^{2}\cdot(x\mu_{1,z})^{i-2}$
$\displaystyle=V_{1}x^{2}\cdot\sum_{i\geq 2}\frac{1}{i!}\sum_{z\in
V}\frac{D_{1}(z)\mu_{1,z}^{2}}{V_{1}}\cdot(x\mu_{1,z})^{i-2}$
$\displaystyle=V_{1}x^{2}\cdot\sum_{i\geq
2}\frac{1}{i!}\cdot\mathbb{E}_{z\sim\mathcal{P}}[(x\mu_{1,z})^{i-2}]$

Since $x<1/c_{Y}$, we note $|x\mu_{1,z}|\leq 1$ for any $z\in V$. Therefore,

$\sum_{i\geq
2}\frac{1}{i!}\mathbb{E}_{z\sim\mathcal{P}}[(x\mu_{1,z})^{i-2}]\leq\sum_{i\geq
2}1/i!\sum_{z\in V}\mathcal{P}(z)=\sum_{i\geq 2}1/i!<1.$ (86)

Putting Equations (85) and (86) together in Equation (83), we upper bound
$\sum_{z\in V}D_{1}(z)e^{x\mu_{1,z}}\leq 1+V_{1}x^{2}\leq e^{x^{2}V_{1}}$
which finishes the proof. ∎

The following theorem is the key tool in the proof of Main Theorem. It appears
as Theorem 2.2.2 in [KV00]. The proof is a direct adaptation and we reproduce
the proof given in Kim-Vu for completeness.

######  Theorem 14.

(Theorem 2.2.2 in [KV00]) Let $V$ and $c$ be positive numbers and let
$B=\\{\omega\in\Omega:c(\omega)>c\lor\ V(\omega)>V\\}$. If $0<\eta<V/c^{2}$
then

$Pr(|Y-\mathbb{E}[Y]|>(\eta V)^{1/2})\leq 2e^{-\eta/4}+Pr(B).$

###### Proof.

Call $B$ the set of bad leaves. Take $\omega\in B$ and consider the path from
root to $\omega$. Let $i$ denote the first level such that either
$V_{i}(\omega)>V$ or $c_{i}(\omega)>c$. If $i$ is such a level, we call the
node $\omega^{i-1}$ exceptional. Note that all leaves $\omega^{\prime}$ below
an exceptional node are bad. Now, define a new polynomial $Y^{\prime}$ as
follows. For a leaf $\omega^{\prime}\not\in B$, set
$Y^{\prime}(\omega)=Y(\omega)$. For any leaf $\omega^{\prime}$ below an
exceptional node $\omega^{i-1}$, we set
$Y^{\prime}(\omega)=\mathbb{E}[Y|\omega^{\prime{i-1}}=\omega^{i-1}]$. Since
the exceptional nodes are incomparable, the function $Y^{\prime}$ is well-
defined. Thus, in the new tree $V(\omega)\leq V$ and $c(\omega)\leq c$ for
every leaf $\omega$. So, Theorem 13 implies
$Pr(|Y^{\prime}-\mathbb{E}[Y^{\prime}]|\geq(\eta V)^{1/2})\leq
2\exp(-\eta/4)$. Finally, note that $\mathbb{E}[Y^{\prime}]=\mathbb{E}[Y]$ and
recall $Y^{\prime}(\omega)=Y(\omega)$ for all $\omega\not\in B$. This gives

$Pr(|Y-\mathbb{E}[Y]|>(\eta V)^{1/2})\leq 2e^{-\eta/4}+Pr(B)$

as desired. ∎

####  B.0.4 Proof of Theorem 12

We again adapt the proof given in [KV00]. To do this, we first borrow a
definition.

######  Definition 26.

(Shadow hypergraphs) Let $H=(\mathcal{V},\mathcal{E},w)$ denote a weighted
hypergraph as defined in Definition 20. The shadow $H^{*}$ of $H$ is a
weighted hypergraph on the same (ordered) set $\mathcal{V}$ of vertices where
the edge set of $H^{*}$ is defined as follows: Take any edge
$e=\\{a_{1},a_{2},\ldots a_{l}\\}\in\mathcal{E}(H)$ where $a_{1}<a_{2}<\ldots
a_{l}$ and produce $l$ new edges (which we call shadow edges) $e_{j}$ where
$e_{0}=\emptyset$ and for $1\leq j\leq l-1$, we set $e_{j}=\\{a_{1},\ldots
a_{j}\\}$. Finally, in $H^{*}$, we set the weight of edge $e_{j}$ to be
$w(e)\cdot\prod_{s=j+1}^{l}p_{a_{s}}$ where $p_{w}$ is the expectation of the
indicator $t_{w}$. If an edge in $H^{*}$ is shadow of multiple edges we keep
one copy of the edge and add the weights.

Also, we will need the following claims.

######  Claim 10.

For any $(i,z)\in\mathcal{V}(H)$, consider the truncated hypergraph
$H_{(i,z)}$ (Definition 21). We have, for any $j<h$,

$E_{j}[H_{(i,z)}]\leq E_{j+1}[H].$

(Recall from Definition 22 that $E_{j}[H]=\max_{|A|=j}\mathbb{E}[Y_{H_{A}}]$.)

###### Proof.

$E_{j}[H_{(i,z)}]=\max_{\begin{subarray}{c}A\subseteq\mathcal{V}(H)\setminus(i,z)\\\
|A|=j\end{subarray}}\mathbb{E}[Y_{H_{A\cup\\{i,z\\}}}]\leq\max_{\begin{subarray}{c}A\subseteq\mathcal{V}(H)\\\
|A|=j+1\end{subarray}}\mathbb{E}[Y_{H_{A}}]=E_{j+1}[H].$

∎

######  Claim 11.

For any $j<h$, we have $\mathbb{E}_{j}[H^{*}]\leq h\cdot\mathbb{E}_{j}[H]$.

###### Proof.

$\mathbb{E}_{j}[H^{*}]=\max_{\begin{subarray}{c}A\subseteq\mathcal{V}(H)\\\
|A|=j\end{subarray}}\mathbb{E}[Y_{H_{A}^{*}}]\ \leq
h\cdot\max_{\begin{subarray}{c}A\subseteq\mathcal{V}(H)\\\
|A|=j\end{subarray}}\mathbb{E}[Y_{H_{A}}]=h\mathbb{E}_{j}[H].$

Here, the first step follows from the definition of $E_{j}$ and $H^{*}$. The
second step follows because the maximum number of shadow edges of any edge in
$H$ is at most $h$ and by the property that all the indicators for all
variables in any edge are independent (see Remark 6). ∎

Our adaptation of the proof is pretty direct. The only difference is that we
have an $n$-ary tree instead of a binary tree as considered in Kim-Vu. We just
adapt our definitions of fluctuation and absolute fluctuation (see Definition
24). The proof is given only for completeness sake.

###### Proof.

(Of Theorem 12) For any $\eta>1$, a positive polynomial $Y$ and its support
hypergraph $H$, we show by induction on the arity $h$ of biggest hyperedge of
$H$ the following.

$Pr(|Y-\mathbb{E}[Y]|\geq
c_{h}(E_{H}E^{\prime}_{H})^{1/2}\eta^{h})<d_{h}\exp(-\eta/4+(h-1)\log{Rn}).$

Here, $d_{h}$ is recursively defined as follows: $d_{1}=2$ and
$d_{h}=(1+1/n)d_{h-1}+2/n^{h-1}$ and $c_{h}=2^{h-1}(h!)^{1/2}$.

Base Case: For base case, we take $h=1$. In this case, all edges have at most
one vertex. Thus, $Y=\sum_{(i,z)\in\mathcal{V}}w_{i,z}t_{i,z}+w_{0}$. Here,
$w_{i,z}$ is the weight of $t_{i,z}$ and $w_{0}$ is the weight of the
(possibly) empty edge. We want to show

$Pr(|Y-\mathbb{E}[Y]|\geq\eta\max(E_{0},E_{1})\cdot E_{1})\leq 2\exp(-\eta/4)$
(87)

Note that since we seek large deviation bounds on $|Y-\mathbb{E}[Y]|$, we may
assume that $w_{0}=0$. In this case,
$E_{1}=\max_{(i,z)\in\mathcal{V}}w_{i,z}$. Keeping with Kim-Vu, set

$V=\max(E_{0},E_{1})E_{1}\eta,\ \ c=E_{1}.$

We prove the deviation bounds we seek in this case using Theorem 14. We now
check if conditions of Theorem 14 apply. In this ($h=1$) case, note that for
fixed $i\in[R]$ and $z\in V$, $c_{i,z}(\omega)=w_{i,z}$ holds for all
$\omega\in\Omega$. We denote this value as $c_{i,z}$. Next, note that

$\sum_{i\in[R]}V_{i}=\sum_{\begin{subarray}{c}i\in[R]\\\ z\in
V\end{subarray}}D_{i}(z)c_{i,z}^{2}=\ \sum_{\begin{subarray}{c}i\in[R]\\\ z\in
V\end{subarray}}D_{i}(z)w_{i,z}^{2}\leq\max w_{i,z}\sum
D_{i}(z)w_{i,z}=E_{1}E_{0}<V.$

Moreover, by choice of $V$ and $c$ above, it follows
$V/c^{2}=V/E_{1}^{2}\geq\eta$. Thus, conditions of 14 indeed holds. Since,
$\eta>1$, this gives

$\displaystyle Pr(|Y-\mathbb{E}[Y]|\geq\eta V^{1/2})\leq
Pr(|Y-\mathbb{E}[Y]|\geq(\eta V)^{1/2})\leq 2e^{-\eta/4}$

which satisfies Equation (87) as desired.

Inductive Step: Now, we suppose the induction hypothesis holds for $h-1$ and
we prove it for a hypergraph $H$ with $\max_{e\in\mathcal{E}(H)}|e|=h$. Take a
leaf $\omega$ of $T$. For some $c$ and $V$ to be chosen later, we define the
following events:

  * –

$\mathcal{E}_{1}(\omega)$: The event that $c(\omega)>c$.

  * –

$\mathcal{E}_{2}(\omega)$: The event that $V(\omega)>V$.

Use a union bound and write $Pr(\mathcal{E}_{1}\lor\mathcal{E}_{2})\leq
Pr(\mathcal{E}_{1})+Pr(\mathcal{E}_{2}|\overline{\mathcal{E}_{1}})$. For the
first term above, note

$\displaystyle Pr(\mathcal{E}_{1})$ $\displaystyle=Pr(c(\omega)>c)=Pr(\exists
i\in[R],z\in V\ s.t.\ c_{i,z}(\omega)>c)$
$\displaystyle\leq\sum_{\begin{subarray}{c}i\in[R]\\\ z\in
V\end{subarray}}Pr(c_{i,z}(\omega)>c)$

Next, for the second term, note

$\displaystyle Pr(\mathcal{E}_{2}|\overline{\mathcal{E}_{1}})$
$\displaystyle=Pr(V(\omega)>V|\overline{\mathcal{E}_{1}})=Pr(\sum_{i\in[R]}V_{i}(\omega)>V|\overline{\mathcal{E}_{1}})$
$\displaystyle=Pr(\sum_{\begin{subarray}{c}i\in[R]\\\ z\in
V\end{subarray}}D_{i}(z)c_{i,z}(\omega)^{2}>V|\overline{\mathcal{E}_{1}})$
$\displaystyle\leq Pr(\sum_{\begin{subarray}{c}i\in[R]\\\ z\in
V\end{subarray}}D_{i}(z)c_{i,z}(\omega)>V/c)$

Here note that we dropped the conditioning in the last inequality. We can do
this because the event $\mathcal{E}_{2}|\overline{\mathcal{E}_{1}}$ is a
subevent of the event that $\omega\sim_{\mathcal{D}}\Omega$ satisfies
$\sum_{\begin{subarray}{c}i\in[R]\\\ z\in
V\end{subarray}}D_{i}(z)c_{i,z}(\omega)>V/c$.

Putting together the above discussion we get

$Pr(c(\omega)>c\lor V(\omega)>V)\leq\sum_{\begin{subarray}{c}i\in[R]\\\ z\in
V\end{subarray}}Pr(c_{i,z}(\omega)>c)+Pr(\sum_{\begin{subarray}{c}i\in[R]\\\
z\in V\end{subarray}}D_{i}(z)c_{i,z}(\omega)>V/c)$ (88)

Now, we will upper bound both of the probabilities above using Theorem 14 and
the induction hypothesis for hypergraphs with edges of maximum arity $h-1$.
Pick $\omega\sim_{\mathcal{D}}\Omega$. Consider the polynomial.

$C_{i,z}=\sum_{(i,z)\in e\in\mathcal{E}(H)}w(e)\prod_{s\in
e\setminus(i,z)}t_{s}^{(i,z)}.$

where for $s=(i^{\prime},z^{\prime})\in[R]\times V$, $t_{s}^{(i,z)}=t_{s}$ if
$i^{\prime}<i$ and $t_{s}^{(i,z)}=D_{i^{\prime}}(z^{\prime})$ if
$i^{\prime}>i$. Thus, this polynomial is defined with $t_{s}^{(i,z)}$ as its
variables where $s=(i^{\prime},z^{\prime})$ with $i^{\prime}<i$. For the
random $\omega$ picked, let $\omega^{i-1}$ denote the first $i-1$ coordinates
in $\omega$. Now, set the variables in the polynomial $C_{i,z}$ as follows.
For $i^{\prime}<i,s=(i^{\prime},z^{\prime})$ let

$t_{s}^{(i,z)}=\begin{cases}1&\text{ if }\omega_{i^{\prime}}=z^{\prime}\\\
0&\text{ otherwise }\end{cases}$

Then note that

$C_{i,z}(\\{t_{i^{\prime},z^{\prime}}^{(i,z)}\\}_{i^{\prime}<i})\in\\{c_{i,z}(\omega)-\mathbb{E}[\omega^{i-1}],c_{i,z}(\omega)+\mathbb{E}[\omega^{i-1}]\\}$

where the $\mathbb{E}[\omega^{i-1}]$ is a constant on fixing $\omega^{i-1}$.

Also, note that the supporing hypergraph of $C_{i,z}$ is the $(i,z)$-truncated
hypergraph of $H$ (see Definition 21). This corresponds to the truncated graph
$H_{(i,z)}$ which has arity $h-1$. So, we apply the induction hypothesis. This
gives

$Pr(|C_{i,z}-\mathbb{E}[C_{i,z}]|>c_{h-1}(\mathbb{E}[C_{i,z}]\mathbb{E}^{\prime}[C_{i,z}])^{1/2}\eta^{h-1})<\
d_{h-1}\exp(-\eta/4+(h-2)\log(Rn))$ (89)

Note that $\mathbb{E}[C_{i,z}],\mathbb{E}^{\prime}[C_{i,z}]$ are both at most
$\mathbb{E}^{\prime}[H]$ (which follows from Claim 10). This together with
Equation (89) gives

$Pr(C_{i,z}>2c_{h-1}\mathbb{E}^{\prime}[H]\eta^{h-1})<d_{h-1}\exp(-\eta/4+(h-2)\log{Rn})$
(90)

For the second term in Equation (88), define the following polynomial

$C=\sum_{\begin{subarray}{c}i\in[R]\\\ z\in
V\end{subarray}}D_{i}(z)C_{i,z}=\sum_{(i,z)\in[R]\times V}\
\sum_{\begin{subarray}{c}e\in\mathcal{E}(H)\\\
e\ni(i,z)\end{subarray}}\prod_{s\in e\setminus(i,z)}D_{i}(z)t_{s}^{(i,z)}.$

Note that the support hypergraph of this polynomial is the precisely the
shadow $H^{*}$ of $H$. Recall that all edges of $H^{*}$ have arity at most
$h-1$. Thus, we again use the induction hypothesis and obtain

$Pr(|C-\mathbb{E}[C]|>c_{h-1}\cdot(E_{H^{*}}E^{\prime}_{H^{*}})^{1/2}\eta^{h-1})<\
d_{h-1}\exp(-\eta/4+(h-2)\log(Rn))$ (91)

Using Claim 11, we get

$Pr(C>2c_{h-1}\cdot