# Non-Adaptive Edge Counting and Sampling via Bipartite Independent Set
Queries

Raghavendra Addanki111Most of the work done while a graduate student at the
University of Massachusetts Amherst.
Adobe Research
<EMAIL_ADDRESS>Andrew McGregor
University of Massachusetts Amherst
<EMAIL_ADDRESS>Cameron Musco
University of Massachusetts Amherst
<EMAIL_ADDRESS>
###### Abstract

We study the problem of estimating the number of edges in an $n$-vertex graph,
accessed via the _Bipartite Independent Set_ query model introduced by Beame
et al. (ITCS ’18). In this model, each query returns a Boolean, indicating the
existence of at least one edge between two specified sets of nodes. We present
a _non-adaptive_ algorithm that returns a $(1\pm\epsilon)$ relative error
approximation to the number of edges, with query complexity
$\widetilde{O}(\epsilon^{-5}\log^{5}n)$, where $\widetilde{O}(\cdot)$ hides
$\operatorname{poly}(\log\log n)$ dependencies. This is the first non-adaptive
algorithm in this setting achieving $\operatorname{poly}(1/\epsilon,\log n)$
query complexity. Prior work requires $\Omega(\log^{2}n)$ rounds of
adaptivity. We avoid this by taking a fundamentally different approach,
inspired by work on single-pass streaming algorithms. Moreover, for constant
$\epsilon$, our query complexity significantly improves on the best known
adaptive algorithm due to Bhattacharya et al. (STACS ’22), which requires
$O(\epsilon^{-2}\log^{11}n)$ queries. Building on our edge estimation result,
we give the first non-adaptive algorithm for outputting a nearly uniformly
sampled edge with query complexity $\widetilde{O}(\epsilon^{-6}\log^{6}n)$,
improving on the works of Dell et al. (SODA ’20) and Bhattacharya et al.
(STACS ’22), which require $\Omega(\log^{3}n)$ rounds of adaptivity. Finally,
as a consequence of our edge sampling algorithm, we obtain a
$\widetilde{O}(n\log^{8}n)$ query algorithm for connectivity, using two rounds
of adaptivity. This improves on a three-round algorithm of Assadi et al. (ESA
’21) and is tight; there is no non-adaptive algorithm for connectivity making
$o(n^{2})$ queries.

##  1 Introduction

In this work, we study sub-linear query algorithms for estimating the number
of edges in a simple, unweighted graph $G=(V,E)$, and for sampling uniformly
random edges. Access to $G$ is via a _Bipartite Independent Set (BIS)_ oracle
[BHPR+18]. A query to this oracle takes as input two disjoint subsets
$L,R\subseteq V$ and returns

$\mathcal{BIS}(L,R)=\begin{cases}\text{`1'}&\text{ if there is no edge between
$L$ and $R$}\\\ \text{`0'}&\text{ otherwise.}\end{cases}$

Local Query Models. Prior work on sub-linear query graph algorithms has
largely focused on _local_ queries, in particular, (i) vertex degree queries
(ii) neighbor queries (output the $i$th neighbor of a vertex) and (iii) edge
existence queries [Fei06, GR08, Ses]. In the literature, the first two types
of queries form the adjacency list query model, while all three types of
queries form the adjacency matrix query model. Under these models, a variety
of graph estimation problems have been well studied, including edge counting
and sampling [ER18, GR08, Ses, TT22], subgraph counting [ABG+18, BER21,
ERS20], vertex cover [Beh22, ORRR12], and beyond [Ron19].

For a graph with $n$ nodes and $m$ edges, given access only to degree queries,
Feige [Fei06] presented an algorithm for estimating $m$ up to $(2\pm\epsilon)$
relative error with query complexity
$O(\sqrt{n}\cdot\operatorname{poly}(1/\epsilon,\log n))$. This work also
showed that any $(2-o(1))$-approximation algorithm requires $\Omega(n)$
queries. In the adjacency list query model, Goldreich and Ron [GR08] gave a
$(1\pm\epsilon)$-approximation algorithm, with query complexity
$O(n/\sqrt{m}\cdot\operatorname{poly}(1/\epsilon,\log n))$. Recently, Eden and
Rosenbaum [ER18] gave algorithms for near-uniform edge sampling with the same
query complexity, and showed that this complexity is nearly tight.

Global Query Models. Motivated by the desire to obtain more query efficient
algorithms, Beame et al. [BHPR+18] studied edge estimation using _global_
queries that can make use of information across the graph, including the BIS
queries that we will focus on, and the related Independent Set (IS) queries.
IS queries were introduced in the literature on query efficient graph recovery
[AN19, AC08]. They answer whether or not there exist any edges in the induced
subgraph on a subset of nodes $S\subseteq V$. We refer the reader to the
exposition in [BHPR+18], which discusses applications of these global query
models in group testing [CS90, Dor43], computational geometry [AHP08, CJ15,
Fis03], fine-grained complexity [DL21, DLM20], and decision versus counting
complexity [DLM20, RT16, Sto83, Sto85].

In the IS query model, [BHPR+18, CLW20] give a
$O(\min\\{\sqrt{m},n/\sqrt{m}\\}\cdot\textup{poly}(\log n,1/\epsilon))$ query
algorithm for $(1\pm\epsilon)$ approximate edge counting. In the BIS model,
numerous authors [BHPR+18, DLM20, BBGM22] achieve
$(1\pm\epsilon)$-approximation for edge counting and near-uniform edge
sampling using just $\operatorname{poly}(1/\epsilon,\log n)$ queries. This is
exponentially smaller than the query complexities in the IS and local queries
models.

Extending the BIS query model to hypergraphs, Dell et al. [DLM20] introduce
the coloured independence oracle which detects the presence of a size $k$
hyperedge. They give algorithms for hyperedge estimation and sampling using
this generalized oracle. Many other variants of global queries have been
studied including Linear, OR and Cut queries [ACK21, CS21, RSW18]. These
queries have been applied to solving maximum matching [KK20, Nis21], minimum
cut [RSW18], triangle estimation [BBGM19, BBGM21, DLM20], connectivity
[ACK21], hitting sets [BGK+18], weighted edge estimation [BGMP19], problems
related to linear algebra [RWZ20], quantum algorithms [MS22], and full graph
recovery [AN19, AC08].

The Role of Adaptivity. Notably, for both local and global queries, most sub-
linear time graph algorithms are adaptive, i.e., a query may depend on the
answers to previous queries. In many cases, it is desirable for queries to be
_non-adaptive_. This allows them to be completed independently, and might
allow for the resulting algorithm to be easily implemented in massively
parallel computation frameworks [KSV10]. Non-adaptive algorithms also lead
naturally to single-pass, rather than multi-pass, streaming algorithms. In
fact, the BIS query model can be seen as a very restricted subset of the more
general Linear query model, in which each query outputs the inner product of
the edge indicator vector with a query vector. This model has long been
studied in the graph-streaming literature [AGM12, McG14], in part due to its
usefulness in giving single-pass algorithms. However, it has remained open
whether non-adaptive algorithms can be given in more restricted global query
models.

For these reasons, Assadi et al. [ACK21] and Chakrabarti and Stoeckl [CS21]
have recently sought to reduce query adaptivity under a variety of global
query models, including Linear, OR, Cut and BIS queries. These works study the
_single element recovery_ problem, which is a weaker variant of uniform edge
sampling, requiring that the algorithm return a single edge in $G$. Assadi et
al. also study the problem of checking connectivity, presenting a BIS query
algorithm making $\widetilde{O}(n)$ queries and using three rounds of
adaptivity. They give a two-round algorithm in the stronger OR query model,
and show that even in this model, there is no non-adaptive algorithm for
connectivity making $o(n^{2})$ queries.

We note that reducing query adaptivity is also a well-studied direction in the
closely related literature on group testing [DHH00, INR10]. IS and BIS oracles
can be thought of as tests if there is a single element in a group of edges,
where that group is required to be all edges incident on one node set (IS) or
between two disjoint sets (BIS). Attempts to minimize query adaptivity have
also been made for sparse recovery [IPW11, KP19, NSWZ18], sub-modular function
maximization [BS18, CQ19], property testing [CG18] and multi-armed bandit
learning [AAAK17].

###  1.1 Our Contributions

Our main result is the first _non-adaptive_ algorithm for edge estimation up
to $(1\pm\epsilon)$ relative error, using $\operatorname{poly}(1/\epsilon,\log
n)$ BIS queries. Formally, we show:

######  Theorem 1 (Theorem 11 restated).

Given a graph $G$ with $n$ nodes and $m$ edges, there is an algorithm that
makes $O(\epsilon^{-5}\log^{5}n\log^{6}(\log n))$ non-adaptive BIS queries to
$G$ and returns an estimate $\widehat{m}$ satisfying:
$m(1-\epsilon)\leq\widehat{m}\leq m(1+\epsilon),\textup{with probability at
least }3/5$.222Note that the success probability can be boosted in the
standard way, by running multiple independent instantiations of the algorithm
and taking their median estimate.

Prior methods for $(1\pm\epsilon)$ error edge estimation using BIS queries are
based on a binary search style approach [BHPR+18, DLM20, BBGM22], which is
inherently adaptive, and this leads to algorithms requiring
$\Omega(\log^{2}n)$ rounds of adaptivity. Beame et al. [BHPR+18] present a
non-adaptive algorithm giving a $O(\log^{2}n)$ approximation factor for
bipartite graphs, using $O(\log^{3}n)$ queries. However, no non-adaptive
results for general graphs or achieving $1\pm\epsilon$ relative error for
arbitrary $\epsilon>0$ were previously known. Even with adaptivity, the best
known algorithm due to [BBGM22] has a query complexity of
$O(\epsilon^{-2}\log^{11}n)$ and succeeds with probability $1-1/n^{2}$.
Therefore, our non-adaptive result improves upon the current best known
algorithms, for constant $\epsilon$.

Our second result builds on our edge estimation approach, giving the first
non-adaptive BIS query algorithm that returns a near-uniformly sampled edge.
Formally:

######  Theorem 2 (Theorem 38 restated).

Given a graph $G$ with $n$ nodes, $m$ edges, and edge set $E$, there is an
algorithm that makes $O(\epsilon^{-4}\log^{6}n\log(\epsilon^{-1}\log
n)+\epsilon^{-6}\log^{5}n\log^{6}(\log n)\log(\epsilon^{-1}\log n))$ non-
adaptive BIS queries which, with probability at least $1-\epsilon$, outputs an
edge from a probability distribution $P$ satisfying $(1-\epsilon)/{m}\leq
P(e)\leq(1+\epsilon)/{m}$ for every $e\in E$.

Prior results for near-uniform edge sampling required $\Omega(\log^{3}n)$
rounds of adaptivity [BBGM22, DLM20]. Additionally, even ignoring adaptivity,
our results improves on the best known query complexity of
$O(\epsilon^{-2}\log^{14}n)$, due to [BBGM22], for constant $\epsilon$.

By combining Theorem 2 with prior work on sublinear query graph connectivity,
via edge sampling, we obtain a connectivity algorithm using two rounds for
adaptivity:

######  Theorem 3 (Theorem 39 restated).

Given a graph $G$ with $n$ nodes, there is a $2$-round adaptive algorithm that
determines if $G$ is connected with probability at least $1-1/n$ using
$\tilde{O}(n\log^{8}n)$ BIS queries, where $\tilde{O}(\cdot)$ ignores the
$\log^{O(1)}\log n$ dependencies.

Theorem 3 improves on a three-round algorithm of Assadi et al. [ACK21] and is
tight: even in the stronger OR query model (which allows checking the presence
of an edge within an arbitrary subset of edges) no non-adaptive algorithm can
make $o(n^{2})$ queries. Assadi et al. gave a two-round algorithm in this
stronger OR query model. Thus, Theorem 3 closes the gap between BIS queries
and OR queries for this problem. We note that there is a separation from the
even stronger Linear query model, where non-adaptive algorithms for
connectivity and cut approximation are well-known [AGM12]. Understanding if
there remain interesting separations between the BIS and OR query models in
terms of adaptivity would be very interesting.

##  2 Technical Overview

In this section, we present an overview of our non-adaptive BIS query
algorithms for edge estimation (Theorem 1) and near-uniform edge sampling
(Theorem 2), along with our $2$-round algorithm for connectivity (Theorem 3).

###  2.1 Edge Estimation

A simple idea to estimate the number of edges in a graph via BIS queries is to
sample small random subsets of nodes and run BIS queries to check the presence
of an edge between them. The fraction of these queries that return ‘1’ (i.e.,
indicating the presence of no edge) can then be used to estimate the number of
edges. In particular, for a graph containing $m$ edges, if the random
subgraphs have $O(n/\sqrt{m})$ nodes in them, then we expect a ‘1’ answer with
constant probability. Beame et al. [BHPR+18] describe a non-adaptive algorithm
along these lines, which gives a $O(\log^{2}n)$ approximation for bipartite
graphs using $O(\log^{3}n)$ queries. Unfortunately, going beyond this coarse
approximation factor is difficult since many dependencies due to common
neighbors arise and this increases the variance of the estimators. Beame et
al. handle the issue by using the coarse estimates to subdivide the graph into
smaller sub-graphs, until these divided graphs only contain $O(\log^{O(1)}n)$
edges, at which point all their edges can be discovered with few queries. This
strategy yields a $(1\pm\epsilon)$ approximation, however, it is inherently
adaptive.

Our non-adaptive edge estimation algorithm takes a different approach. Suppose
we could sample each node with probability $p_{v}\approx\epsilon^{-2}d(v)/m$
and compute the degree of the sampled nodes then it is straightforward to show
$\sum_{v}\mathbb{I}[v\mbox{ sampled}]\cdot d(v)/p_{v}$ equals $2m$ in
expectation. Furthermore, an application of Bernstein bound implies that it is
a $(1\pm\epsilon)$ with sufficient probability. The challenge is showing that
this type of approach can be approximated in the BIS query model.

Subsampling Nodes. The first idea, drawn from work on streaming algorithms, is
to subsample the nodes of $G$ at different rates of the form $1/\gamma^{j}$
where $\gamma>1$ is constant and $j\in\\{0,1,\cdots,O(\log n)\\}$. At each
rate, we will “recover” all sampled nodes (along with a corresponding degree
estimate) whose degree is roughly $d(v)\approx{\epsilon^{2}m}/{\gamma^{j}}$.
In this way, each node will be recovered with probability roughly
${1}/{\gamma^{j}}\approx\epsilon^{-2}d(v)/m$, as desired. We describe this
subsampling procedure in Section 4.3, as part of our main algorithm Edge-
Estimator (Algorithm 3).

Recovering Heavy Nodes. The next challenge is to show that we can actually
recover the appropriate nodes and degree estimates at each sampling rate. If
we can approximate the degree of all nodes sampled at rate $1/\gamma^{j}$ up
to additive error $O\left({\epsilon^{3}\cdot m}/{\gamma^{j}}\right)$, we will
obtain a $(1\pm\epsilon)$ relative error approximation to the degree of any
node we hope to recover at that sampling rate, i.e., any node with degree
roughly ${\epsilon^{2}m}/{\gamma^{j}}$. Using these approximations, we can
determine which nodes should be recovered at that rate, and form our edge
estimate.

Degree Estimation via Neighborhood Size Estimation. To achieve such an
additive error approximation, we also use ideas from the sparse recovery and
streaming literature. In particular, we implement an approach reminiscent of
the Count-Min sketch algorithm [CM05]. The approach is described in detail in
Section 4.2, where we present Algorithm Estimate-Degree (Algorithm 2). First
observe that when sampling at rate $1/\gamma^{j}$, conditioned on any node $v$
being included in the sample, the expected total degree of the sampled nodes
other than $v$ is $O(m/\gamma^{j})$. If we further subdivide these nodes into
$\widetilde{O}(1/\epsilon^{3})$ random groups, the expected total degree of
all nodes other than $v$ in any group is
$\widetilde{O}\left({\epsilon^{3}\cdot m}/{\gamma^{j}}\right)$.

Now, if $v$ is placed in group $S$, we can approximately upper bound its
degree by the total _neighborhood size of $S$_. This upper bound holds
approximately as long as $v$ does not have too many neighbors in $S$, which it
won’t with good probability. The neighborhood size of $S$ is in turn upper
bounded by the degree of $v$ plus the total degree of other nodes in $S$, and
thus by $d(v)+\widetilde{O}\left({\epsilon^{3}\cdot m}/{\gamma^{j}}\right)$ in
expectation. So, in expectation, this approach gives an additive
$\widetilde{O}\left({\epsilon^{3}\cdot m}/{\gamma^{j}}\right)$ error
approximation to the degree of each sampled node $v$, with constant
probability. Repeating this procedure $O(\log n)$ times, and, as in the Count-
Min sketch, taking the minimum degree estimate for each node sampled at rate
$1/\gamma^{j}$, gives us high probability approximation for such nodes.

Neighborhood Size Estimation. The final step is to implement an algorithm that
can estimate the neighborhood size of the random subset of nodes $S$, to be
used in our degree estimation procedure. We do this in Section 4.1, where we
present Algorithm Neighborhood-Size (Algorithm 1). This algorithm takes as
input two disjoint subsets $L,R$ and returns a $(1\pm\epsilon)$-approximation
for the size of the neighborhood of $L$ in $R$. We highlight that this may be
very different than the _number of edges connecting $L$ to $R$_ – the
neighborhood size is the number of nodes in $R$ with at least one edge to $L$.
This difference is critical in removing the correlations discussed previously
due to common neighbors. Such correlations lead to the adaptive nature of
prior algorithms [BHPR+18, DLM20]. To estimate the size of the neighborhood of
$L$ in $R$, we sample the nodes in $R$ at different rates and ask BIS queries
on $L$ and the sampled subset of $R$. Intuitively, when the sampling rate is
the inverse of the size of the neighborhood, we will observe a ‘1’ response
with constant probability. We can detect this and thus estimate the
neighborhood size.

Non-adaptivity. The approach is inherently non-adaptive as all random sampling
of nodes and random subsets can be formed ahead of time, independently of any
query responses. The only catch is that to determine which nodes should be
recovered at each sampling rate, i.e., those nodes with degree
$d(v)\approx\epsilon^{-2}\cdot m/{\gamma^{j}}$, we need a coarse estimate to
the edge count $m$ in the first place. Fortunately, we can bootstrap such an
estimate starting with a very coarse $O(\log^{2}n)$-relative error approximate
estimation, due to Beame et al. [BHPR+18]. We then refine this estimate
iteratively using Algorithm Refine-Estimate (Algorithm 4). Each refinement
improves the approximation factor by $\epsilon$, and after
$O(\log_{1/\epsilon}\log n)$, refinements our estimate will result in a
$(1\pm\epsilon)$-approximation factor. The key observation here is that each
refine step does not require any additional BIS queries. Thus, our algorithm
remains non-adaptive.

###  2.2 Uniform Edge Sampling and Connectivity

In the full version, we prove Theorem 2 by designing and analyzing a non-
adaptive algorithm for returning a near-uniform sample among the edges of the
graph. Our approach builds heavily on our edge estimation algorithm. If we
knew the degree $d(v)$ of all vertices, then to sample a uniform edge, we
could sample a vertex $v\in V$ with probability $d(v)/\sum_{w\in V}d(w)$ and
return a uniform neighbor among the neighbors of $v$. We can observe that the
probability that an edge $(v,u)$ is sampled is $d(v)/\sum_{w\in V}d(w)\cdot
1/d(v)+d(u)/\sum_{w\in V}d(w)\cdot 1/d(u)=1/m$, i.e., this approach yields a
uniformly random edge sample.

Node Sampling. We implement the above approach approximately using BIS queries
in Algorithm Sampling. First note that recovered vertices in our edge
estimation algorithm are sampled with probabilities roughly proportional to
their degrees. We argue that we can select a random vertex from this set,
which overall is equal to any vertex $v$ with probability approximately
$d(v)/\sum_{w\in V}d(w)$. To do so, we leverage our degree estimates, and the
fact that our edge count estimator, which is the sum of scaled degrees of
recovered vertices, is well-concentrated.

Random Neighbor Sampling. It remains to show how to return a random neighbor
of the sampled vertex. To do so, in the full version, we describe an algorithm
that takes as input two disjoint subsets $L,R$ and returns a uniform neighbor
among the neighbors of $L$ in $R$. By showing an equivalence between the
substantially more powerful OR queries and BIS queries in this specific
setting, we argue that an existing algorithm for OR queries can be extended to
return a uniform neighbor using BIS queries. An OR query takes as input a
subset of pairs of vertices and returns ‘1’ iff there is an edge in the subset
queried. Building on this, in the full version, we present Algorithm Uniform-
Neighbor that takes as input the subset of nodes sampled at any rate
$1/\gamma^{j}$ as in our edge estimation algorithm, and approximately returns
a uniform neighbor for every vertex $v$ sampled in this set. As before, we
construct $\widetilde{O}(1/\epsilon^{4})$ random partitions of the sampled
nodes. For every vertex $v$ in a random subset $S$, we return a uniform
neighbor (obtained using the idea just described) of $S$ as the neighbor of
$v$. If $v$ has large degree compared to the total degree of nodes in the
partition, which it will if it is meant to be recovered at that sampling rate,
this output will most likely be a neighbor of $v$, and will be close to a
uniformly random one.

A Two-Round Algorithm for Connectivity. Our non-adaptive edge sampling
algorithm (Theorem 2) yields a two-round algorithm for graph connectivity
(Theorem 3), improving on a prior three-round algorithm of [ACK21]. In
particular, the algorithm of [ACK21] selects $O(\log^{2}n)$ random neighbors
per vertex, and contracts the connected components of this random graph into
_supernodes_. This random sampling step can be performed using one round of
$\widetilde{O}(n)$ BIS queries. They prove that in the contracted graph on the
supernodes, there are at most $O(n\log n)$ edges. Using this fact, they then
show how to identify whether all the supernodes are connected using
$\widetilde{O}(n)$ BIS queries and two additional rounds of adaptivity.

We follow the same basic approach: using a first round of $\widetilde{O}(n)$
queries to randomly sample $O(\log^{2}n)$ neighbors per vertex and contract
the graph into supernodes. Once this is done, we observe that we have BIS
query access to the contracted graph simply by always grouping together the
set of nodes in each supernode. So, we can directly apply the non-adaptive
sampling algorithm of Theorem 2 to sample edges from the contracted graph. By
a coupon collecting argument, drawing $O(n\log^{2}n)$ near-uniform edge
samples (with replacement) from the contracted graph suffices to recover all
$O(n\log n)$ edges in the graph, and thus determine connectivity of the
contracted graph, and, in turn, the original graph.

##  3 Preliminaries

Let $G(V,E)$ denote the graph on vertex set $V$ with edges $E\subseteq V\times
V$. Let $|V|=n$ be the number of nodes and $|E|=m$ be the number of edges .
For any set of nodes $S\subseteq V$, let $E[S]\subseteq E$ denote the edges in
the induced subgraph on $S$. For any two disjoint sets of nodes $L,R\subseteq
V$, let $E[L,R]=\\{(u,v)\in E\mid u\in L,v\in R\\}$ denote the edges between
them. For any $v\in V$, let $\Gamma(v)=\\{u\mid(v,u)\in E\mbox{ for some $v\in
V$}\\}$ be its set of neighbours. Let $d(v)=|\Gamma(v)|$ be its degree. For
$S\subseteq V$, let $\Gamma(S)=\bigcup_{u\in S}\Gamma(u)$ and let
$d(S)=\sum_{u\in S}d(u)$.

######  Definition 4 (OR query).

An OR query takes as input a collection $E_{q}$ of pairs of vertices given by
$E_{q}=\\{(x_{1},y_{1}),(x_{2},y_{2}),\cdots(x_{k},y_{k})\mid x_{i},y_{i}\in
V\ \forall i\in[k]\\}$ and satisfies the following:

$\mathcal{OR}(E_{q})=\begin{cases}\text{`1'}\text{ if }E_{q}\cap E=\phi\\\
\text{`0'}\text{ otherwise.}\end{cases}$

######  Lemma 5 (Bernstein’s inequality).

Let $X_{1},X_{2},\ldots X_{n}$ be independent random variables. Suppose
$|X_{i}|\leq M\ \forall i\in[n].$ Then:

$\Pr\left[\left|\sum_{i}X_{i}-\operatorname*{{\bf{E}}}[X_{i}]\right|\geq
t\right]\leq\exp{\left(-\frac{t^{2}}{2\sum_{i}\operatorname*{{\bf{E}}}[(X_{i}-\operatorname*{{\bf{E}}}[X_{i}])^{2}]+\frac{2}{3}Mt}\right)}$

######  Fact 6.

$\left(1+\frac{x}{n}\right)^{n}\geq e^{x}\left(1-\frac{x^{2}}{n}\right)\geq
e^{x}\ \textup{ for }|x|\leq n,\ n\geq 1.$

##  4 Non-adaptive algorithm for edge estimation

In this section, we present our non-adaptive algorithm for edge estimation
using BIS queries. In Section 4.1, we describe an algorithm that takes as
input two disjoint subsets $L,R$ and returns an estimate of the size of the
neighborhood $|\Gamma(L)\cap R|$. Next, in Section 4.2, we use this algorithm
to give additive error approximations of degrees of all the vertices in a
given subset. Finally, in Section 4.3, using the approximate degree estimates,
we construct a $(1\pm\epsilon)$-approximate estimator for $m$ by sampling
nodes with probabilities roughly proportional to their degrees.

###  4.1 Estimating the size of neighborhood

Algorithm Neighborhood-Size takes as input two disjoint subsets $L,R\subseteq
V$ and returns a $(1\pm\epsilon)$-approximation of the size of neighborhood of
$L$ in $R$, i.e., $|\Gamma(L)\cap R|$ using
$\operatorname{poly}(1/\epsilon,\log n)$ BIS queries. We overview the analysis
of this algorithm here, before presenting the details in section 4.1.1.

The main idea is to sample subsets of vertices in $R$ (denoted
$\widehat{R}_{1},\widehat{R}_{2},\ldots$) with exponentially decreasing
probability values $1/2,1/4,1/8,\ldots$. When the sampling rate $1/2^{i}$
falls below ${1}/{|\Gamma(L)\cap R|}$, we expect $L$ to no longer have any
neighbors in $\widehat{R}_{i}$ with good probability. In particular, we can
return the inverse of the smallest probability $1/2^{i}$ for which
$\mathcal{BIS}(L,\widehat{R}_{i})=\text{`1'}$, as a coarse estimate for
$|\Gamma(L)\cap R|$.

To boost the accuracy of this estimate, we repeat the process
$T=O(\epsilon^{-2}\log(\delta^{-1}\cdot\log n))$ times, and at each sampling
rate count the number of times the BIS query
$\mathcal{BIS}(L,\widehat{R}_{i})$ returns ‘1’. This count is denoted
$\texttt{count}(i)$ in Algorithm 1, and its expectation can be written in
closed form as
$\operatorname*{{\bf{E}}}[\texttt{count}(i)]=T\cdot(1-1/2^{i})^{|\Gamma(L)\cap
R|}$. Suppose $2^{\widehat{i}}\leq|\Gamma(L)\cap R|<2^{\widehat{i}+1}$, then,
$\operatorname*{{\bf{E}}}[\texttt{count}(\widehat{i})]=\Theta(T)$. Via a
standard Chernoff bound, it will be approximated to $(1\pm\epsilon)$ error
with high probability by $\texttt{count}(\widehat{i})$. Thus, we can compute
an accurate estimate of the neighborhood size by inverting our estimate of
$\operatorname*{{\bf{E}}}[\texttt{count}(\widehat{i})]$, as
$\log_{(1-{1}/{2^{\widehat{i}}})}({\texttt{count}(\widehat{i})}/{T})$. We
identify the appropriate $\widehat{i}$ in line 12 of Algorithm 1, and compute
the corresponding estimate in lines 13-14. There is one edge case handled in
line 13: if $|\Gamma(L)\cap R|=1$ we will have $\widehat{i}=0$, and
$\texttt{count}(\widehat{i})=0$. The final error bound for Algorithm 1 is
stated below.

Algorithm 1 Neighborhood-Size: Estimating the neighborhood size of $L$ in $R$

1:Input: $L,R\subseteq V$, approximation error $\epsilon$, failure probability
$\delta$.

2:Output: ${\eta}_{\text{est}}(L)$ as an estimate of $|\Gamma(L)\cap R|$.

3:Initialize ${\eta}_{\text{est}}(L)\leftarrow 0$.

4:for $i=0,1,\ldots\log_{2}n$ do

5: $\texttt{count}(i)\leftarrow 0$.

6: for $t=1,2,\ldots T={2e^{8}\ln(\log n/\delta)}\cdot\epsilon^{-2}$ do

7: $\hat{R}_{i}^{t}\leftarrow\\{u\in R\mid u\text{ is included independently
with probability }1/2^{i}\\}$.

8: $\texttt{count}(i)=\texttt{count}(i)+\mathcal{BIS}(L,\hat{R}^{t}_{i})$

9: end for

10:end for

11:if $\texttt{count}(0)=T$ then

12: return ${\eta}_{\text{est}}(L)=0$.

13:else

14: Set
$\widehat{i}\leftarrow\max\left\\{i\mid\frac{\texttt{count}(i)}{T}<\frac{(1-\epsilon)}{2e^{2}}\right\\}$.

15: if $\widehat{i}=0$ then return ${\eta}_{\text{est}}(L)=1$.

16: else return
${\eta}_{\text{est}}(L)=\log_{(1-{1}/{2^{\widehat{i}}})}({\texttt{count}(\widehat{i})}/{T})$.

17: end if

18:end if

####  4.1.1 Approximation Guarantees of Algorithm Neighborhood-Size

For any $i\in\\{0,1,\ldots,\log_{2}n\\}$ let $\hat{R}_{i}$ denote a set
constructed by sampling vertices of $R$ with probability $1/2^{i}$. In
Algorithm 1, we construct $T=O(\epsilon^{-2}\log(\delta^{-1}\cdot\log n))$
such sets, each denoted by $\hat{R}^{t}_{i}\ \forall\ t\in[T]$. Let
$\texttt{count}(i)=\sum_{t=1}^{T}\mathcal{BIS}(L,\hat{R}^{t}_{i})$ denotes the
number of times the BIS query $\mathcal{BIS}(L,\hat{R}^{t}_{i})$ returns ‘1’.
For any $t\in[T]$, we define:

$p(i)=\Pr\left[\mathcal{BIS}(L,\hat{R}^{t}_{i})=\text{`1'}\right]=\Pr\left[\Gamma(L)\cap\widehat{R}^{t}_{i}=\phi\right]\textup{
and }\widehat{p}(i)=\frac{\texttt{count}(i)}{T}.$

Suppose $L$ satisfies:

$2^{i^{*}}\leq|\Gamma(L)\cap R|<2^{i^{*}+1}\textup{ for some
}i^{*}\in\\{0,1,\ldots,\log_{2}n\\}.$

######  Claim 7.

We have the following bounds:

$p(i^{*})\geq\frac{1}{2e^{2}},\quad p(i^{*}-2)>\frac{1}{2e^{8}},\textup{ and
}p(i^{*}-2)\leq\frac{1}{e^{4}}.$

###### Proof.

$\displaystyle
p(i)=\Pr\left[\Gamma(L)\cap\widehat{R}^{t}_{i}=\phi\right]=\Pr[u\not\in\hat{R}^{t}_{i}\
\forall u\in R\cap\Gamma(L)]$ $\displaystyle=\prod_{u\in
R\cap\Gamma(L)}\Pr[u\not\in\hat{R}^{t}_{i}]$
$\displaystyle=\left(1-\frac{1}{2^{i}}\right)^{|\Gamma(L)\cap R|}.$

We can lower bound $p(i^{*})$ by

$\displaystyle p(i^{*})=\left(1-\frac{1}{2^{i^{*}}}\right)^{|\Gamma(L)\cap
R|}\geq\left(1-\frac{1}{2^{i^{*}}}\right)^{2^{i^{*}+1}}$ $\displaystyle\geq
e^{-2}\left(1-\frac{2^{i^{*}+1}}{2^{2i^{*}}}\right)\textup{ (using
inequality}~{}\ref{fact:ineq1})$
$\displaystyle\geq\frac{1}{2e^{2}}\quad\textup{ for }i^{*}\geq 2.$
$\displaystyle p(i^{*})$ $\displaystyle\geq\frac{1}{8}\quad\textup{ for
}i^{*}=1.$

If $i=i^{*}-2$, we have:

$p(i)=\left(1-\frac{1}{2^{i}}\right)^{|\Gamma(L)\cap
R|}\leq\left(1-\frac{1}{2^{i}}\right)^{2^{i^{*}}}\leq
e^{-2^{i^{*}-i}}=\frac{1}{e^{4}}$ $\displaystyle
p(i)=\left(1-\frac{1}{2^{i}}\right)^{|\Gamma(L)\cap
R|}\geq\left(1-\frac{1}{2^{i^{*}-2}}\right)^{|\Gamma(L)\cap R|}$
$\displaystyle>\left(1-\frac{1}{2^{i^{*}-2}}\right)^{2^{i^{*}+1}}$
$\displaystyle\geq
e^{-8}\left(1-\frac{2^{i^{*}+1}}{2^{2i^{*}-4}}\right)\textup{ (using
inequality}~{}\ref{fact:ineq1})$ $\displaystyle\geq\frac{1}{2e^{8}}\textup{
for }i^{*}\geq 5.$

For $i^{*}\leq 4$, the inequality is satisfied. So, we have:
$p(i^{*}-2)>1/2e^{8}$.

∎

######  Claim 8.

For sufficiently small $\epsilon$, with probability at least $1-\delta$, we
have:

$\texttt{count}(i)\geq\frac{1-\epsilon}{2e^{2}}\cdot T\ \forall i\geq
i^{*}\mbox{ and }\texttt{count}(i^{*}-2)<\frac{1-\epsilon}{2e^{2}}\cdot T.$

###### Proof.

As $\texttt{count}(i)=\sum_{t=1}^{T}\mathcal{BIS}(L,\hat{R}^{t}_{i})$, we
have: $\operatorname*{{\bf{E}}}[\texttt{count}(i)]=T\cdot p(i)$. Using Claim
7, we have:

$T={2e^{8}\ln(\log n/\delta)}\cdot\epsilon^{-2}\geq\frac{4\ln(\log
n/\delta)\cdot\epsilon^{-2}}{p(i^{*}-2)}\geq\frac{4\ln(\log
n/\delta)\cdot\epsilon^{-2}}{p(i^{*})},\mbox{ as $p(i^{*})\geq p(i^{*}-2)$.}$

Suppose $i\in\\{i^{*},i^{*}-2\\}$. Then, we have:

$\displaystyle\Pr\left[|\widehat{p}(i)-p(i)|\geq\epsilon\cdot p(i)\right]$
$\displaystyle=\Pr\left[|T\cdot\widehat{p}(i)-T\cdot p(i)|\geq
T\cdot\epsilon\cdot p(i)\right]$
$\displaystyle=\Pr\left[|\texttt{count}(i)-\operatorname*{{\bf{E}}}[\texttt{count}(i)]|\geq\epsilon\operatorname*{{\bf{E}}}[\texttt{count}(i)]\right]$
$\displaystyle\leq
2\exp{\left(-\frac{\epsilon^{2}Tp(i)}{2}\right)}\leq\frac{\delta}{\log
n}\quad(\textup{Using Chernoff bound}).$

Using Claim 7, we get:

$\displaystyle\texttt{count}(i^{*})$ $\displaystyle\geq(1-\epsilon)\cdot
T\cdot p(i^{*})\geq\frac{(1-\epsilon)}{2e^{2}}\cdot T$
$\displaystyle\texttt{count}(i^{*}-2)$ $\displaystyle<(1+\epsilon)\cdot T\cdot
p(i)\leq\frac{(1+\epsilon)}{e^{4}}\cdot T$
$\displaystyle\Longrightarrow\texttt{count}(i^{*}-2)$
$\displaystyle<\frac{(1+\epsilon)}{e^{4}}\cdot
T\leq\frac{(1-\epsilon)}{2e^{2}}\cdot T,\textup{ when
}\epsilon\leq\frac{e^{2}/2-1}{e^{2}/2+1}.$

From the definition, we can observe that $p(i)\geq p(i^{*})\ \forall i\geq
i^{*}$. So, the concentration around expected values for $\texttt{count}(i)$
obtained using Chernoff bounds will hold for all $i\geq i^{*}$. Using union
bound on at most $\log n$ sampling levels, we have, with probability
$1-\delta$:

$\texttt{count}(i^{*}-2)<\frac{(1-\epsilon)}{2e^{2}}\cdot T\mbox{ and
}\texttt{count}(i)\geq\frac{(1-\epsilon)}{2e^{2}}\cdot T\ \forall i\geq
i^{*}.$

∎

######  Lemma 9.

Algorithm 1 uses $O({\epsilon^{-2}}{\log n\log(\delta^{-1}\cdot\log n)})$ BIS
queries and returns an estimate ${\eta}_{\text{est}}(L)$ of $|\Gamma(L)\cap
R|$ such that with probability at least $1-\delta$,

${(1-\epsilon)}\cdot{|\Gamma(L)\cap
R|}\leq{\eta}_{\text{est}}(L)\leq(1+\epsilon)\cdot|\Gamma(L)\cap R|\ .$

###### Proof.

If $|\Gamma(L)\cap R|=0$, then, $\texttt{count}(i)=T$ for every
$i\in\\{0,1,2,\cdots,\log n\\}$. So, $\widehat{i}=0$, as none of the values
$\texttt{count}(i)$, for any $i$ will be below the threshold value of
$(1-\epsilon)T/2e^{2}$. So, the estimate ${\eta}_{\text{est}}(L)=0$ returned
is exact.

Suppose $|\Gamma(L)\cap R|=1$. When we sample with probability $1/2^{i}$ when
$i=0$, we obtain $\widehat{R}^{t}_{i}=R$, for every $t\in[T]$. As
$\mathcal{BIS}(L,R)=\text{`1'}$, we have $\texttt{count}(i)=0$, and our
estimate ${\eta}_{\text{est}}(L)=1$ is exact. For the remainder of the proof,
we assume $i^{*}\geq 1$.

From Algorithm 1, we define
$\widehat{i}=\arg\max\\{i\mid\texttt{count}(i)<(1-\epsilon)T/2e^{2}\\}+1$.
From Claim 8, this implies: $\widehat{i}\geq i^{*}-2$. Therefore, with
probability at least $1-\delta$, we have:

$i^{*}-2\leq\widehat{i}\leq i^{*}-1.$

Now, we argue that ${\eta}_{\text{est}}(L)$ defined by:

${\eta}_{\text{est}}{(L)}:={\log_{\left(1-{1}/{2^{\widehat{i}}}\right)}\widehat{p}(\widehat{i})}\
\mbox{obtains a $(1\pm\epsilon)$ approximation for $|\Gamma(L)\cap R|$.}$
$\displaystyle(1-\epsilon)p(\widehat{i})$
$\displaystyle\leq\widehat{p}(\widehat{i})\leq(1+\epsilon)p(\widehat{i})$
$\displaystyle\log_{\left(1-{1}/{2^{\widehat{i}}}\right)}(1-\epsilon)\cdot
p(\widehat{i})$
$\displaystyle\leq\log_{\left(1-{1}/{2^{\widehat{i}}}\right)}\widehat{p}(\widehat{i})\leq\log_{\left(1-{1}/{2^{\widehat{i}}}\right)}(1+\epsilon)\cdot
p(\widehat{i})$ $\displaystyle|\Gamma(L)\cap
R|+\log_{\left(1-{1}/{2^{\widehat{i}}}\right)}(1-\epsilon)$
$\displaystyle\leq\log_{\left(1-{1}/{2^{\widehat{i}}}\right)}\widehat{p}(\widehat{i})\leq|\Gamma(L)\cap
R|+\log_{\left(1-{1}/{2^{\widehat{i}}}\right)}(1+\epsilon)$
$\displaystyle\Rightarrow|\Gamma(L)\cap R|-2^{\widehat{i}}\cdot\epsilon$
$\displaystyle\leq\log_{\left(1-{1}/{2^{\widehat{i}}}\right)}\widehat{p}(\widehat{i})\leq|\Gamma(L)\cap
R|+2^{\widehat{i}}\cdot\epsilon$ $\displaystyle\Rightarrow|\Gamma(L)\cap
R|-2^{i^{*}-2}\cdot\epsilon$
$\displaystyle\leq\log_{\left(1-{1}/{2^{\widehat{i}}}\right)}\widehat{p}(\widehat{i})\leq|\Gamma(L)\cap
R|+2^{i^{*}-1}\cdot\epsilon$
$\displaystyle\Rightarrow(1-\epsilon/4)\cdot|\Gamma(L)\cap R|$
$\displaystyle\leq\log_{\left(1-{1}/{2^{\widehat{i}}}\right)}\widehat{p}(\widehat{i})\leq(1+\epsilon/2)\cdot|\Gamma(L)\cap
R|.$

Therefore,
${\eta}_{\text{est}}(L):=\log_{\left(1-{1}/{2^{\widehat{i}}}\right)}\widehat{p}(\widehat{i})$
is a $(1\pm\epsilon)$-relative error approximation of $|\Gamma(L)\cap R|$.

The total number of BIS queries used by Algorithm 1 is $O(\log n\cdot
T)=O(\epsilon^{-2}\log n\log(\log n/\delta))$.

∎

###  4.2 Finding good approximation for degrees of vertices

We now describe how to use the Neighborhood-Size algorithm to estimate the
degrees of all vertices in a given subset $S\subseteq V$ up to additive error
depending on the total degree of $S$. Our approach is inspired by the count-
min sketch algorithm [CM05]. We randomly partition $S$ into subsets
$S^{1},S^{2},\ldots,S^{\lambda}$ where $\lambda=O(\epsilon^{-3}\log^{2}n)$.
The choice of the parameter $\lambda$ is based on the analysis in Section 4.3.
For each $S^{i}$, we estimate the size of the neighborhood of $S^{i}$ in
$V\setminus S^{i}$ using Neighborhood-Size. We then return this neighborhood
size estimate as the degree estimate for all vertices in $S^{i}$. For $v\in
S^{i}$, $|\Gamma(S^{i})\cap V\setminus S^{i}|$ is nearly an overestimate for
$d(v)$, as long as $v$ has few neighbors in $S^{i}$, which it will with high
probability. Additionally, it is not too large an overestimate – we can
observe that $|\Gamma(S^{i})\cap V\setminus S^{i}|-d(v)\leq d(S^{i}\setminus
v)$. I.e., the error in the overestimate is at most the total degree of the
other nodes in $S^{i}$. In expectation, this error is at most
$\frac{d(S)}{\lambda}=O\left(d(S)\cdot\frac{\epsilon^{3}}{\log^{2}n}\right)$
due to our random choice of $S^{i}$.

As in the count-min sketch algorithm, to obtain high probability estimates, we
repeat the process $T=O(\log n)$ times and assign the minimum among the
neighborhood estimates as the degree estimate of $d(v)$. The full approach is
given in Algorithm 2 (Estimate-Degree) and the error bound in the Lemma 10
below.

######  Lemma 10.

Suppose $S\subseteq V$. Then, Algorithm 2 uses
$O(\epsilon^{-5}\log^{3}n\log^{2}(\log n))$ BIS queries and with probability
$1-O(1/\log n)$, returns degree estimates $\hat{d}(v)$ for every vertex $v\in
S$ satisfying:

$d(v)(1-\epsilon)\leq\hat{d}(v)\leq d(v)+\frac{\epsilon^{3}}{\log^{2}n}\cdot
d(S).$

Algorithm 2 Estimate-Degree: Obtain additive approximate degree estimates

1:Input: $S$ is a subset of $V$, $\epsilon$ is approximation error.

2:Output: Degree estimates of vertices in $S$.

3:Scale $\epsilon\leftarrow\epsilon/3$ and initialize $\hat{d}(v)\leftarrow n$
for every $v\in S$.

4:for $t$ in $\\{1,2,\ldots,O(\log n)\\}$ do

5: Consider a random partitioning of $S$ into $S^{t1},S^{t2},\ldots
S^{t\lambda}$ where $\lambda=O(\epsilon^{-3}\log^{2}n)$.

6: for every partition $S^{ta}$ where $a\in[\lambda]$ do

7: ${\eta}_{\text{est}}(S^{ta})\leftarrow\textsc{Neighborhood-
Size}(S^{ta},V\setminus S^{ta},\epsilon,\delta)$, where
$\delta=O(1/\log^{4}n)$.

8: $\hat{d}(v)\leftarrow\min\\{\hat{d}(v),{\eta}_{\text{est}}(S^{ta})\\}\
\forall v\in S^{ta}$.

9: end for

10:end for

11:return $\hat{d}(v)$ for every $v\in S$.

####  4.2.1 Proof of Lemma 10

Consider a vertex $v\in S$. It is easy to observe that in any partition
$S^{ta}$ containing $v$, where $t\in[T]\textup{ and }a\in[\lambda]$, the
degree of $v$ outside the partition (denoted by $d(v,V\setminus S^{ta})$) is
upper bounded by the total size of the neighborhood of $S^{ta}$ (denoted by
$|\Gamma(S^{ta})\cap V\setminus S^{ta}|$) which is upper bounded by the total
degree of vertices present in the partition (denoted by $d(S^{ta})$). Similar
to the analysis of count-min sketch, a simple, yet important observation is
that the total degree of the partition except for vertex $v$, i.e.,
$d(S^{ta}\setminus\\{v\\})$ is less than $c\cdot d(S)/\lambda$ for some
constant $c$ and results in the additive approximation factor of
$O(d(S)/\lambda)$. Now, we present the proof of Lemma 10:

###### Proof.

Given $S\subseteq V$. Consider a vertex $v\in S^{ta}$ for some
$a\in\\{1,2\ldots,\lambda\\}$ and $t\in\\{1,2,\cdots,T\\}$. For each call to
neighborhood size estimation, we set the failure probability to be
$\delta=O(1/\log^{4}n)$. From Lemma 9, we have with probability $1-{\delta}$:

$(1-\epsilon)|\Gamma(S^{ta})\cap(V\setminus
S^{ta})|\leq{\eta}_{\text{est}}(S^{ta})\leq(1+\epsilon)|\Gamma(S^{ta})\cap(V\setminus
S^{ta})|$

We can observe that $d(v,V\setminus S^{ta})=|\Gamma(v)\cap(V\setminus
S^{ta})|\leq|\Gamma(S^{ta})\cap(V\setminus S^{ta})|$. Therefore:

$d(v,V\setminus S^{ta})\leq\frac{{\eta}_{\text{est}}(S^{ta})}{1-\epsilon}.$

Consider the following:

$\displaystyle\operatorname*{{\bf{E}}}[d(v,S^{ta})]=\operatorname*{{\bf{E}}}\left[\sum_{u\in
V}\mathbbm{1}\\{u\in\Gamma(v)\cap
S^{ta}\\}\right]=\frac{d(v)}{\lambda}=\frac{d(v)\epsilon^{3}}{c\log^{2}n}\leq\epsilon
d(v),\mbox{ as $c>1$}.$

From Markov’s inequality, with probability at least $1/2$, we have:
$d(v,S^{ta})\leq 2\epsilon d(v).$

Combining the above, with probability $1/2-\delta$, we have:

$\frac{{\eta}_{\text{est}}(S^{ta})}{1-\epsilon}\geq d(v,V\setminus
S^{ta})=d(v)-d(v,S^{ta})\geq d(v)(1-2\epsilon),$
$\Longrightarrow{\eta}_{\text{est}}(S^{ta})\geq(1-3\epsilon)d(v).$

$\displaystyle\operatorname*{{\bf{E}}}\left[d(S^{ta}\setminus\\{v\\})\right]=\operatorname*{{\bf{E}}}\left[\sum_{u\in
S\setminus\\{v\\}}d(u)\mathbbm{1}\\{u\in S^{ta}\\}\right]$
$\displaystyle=\sum_{u\in S\setminus\\{v\\}}d(u)\Pr[u\in S^{ta}]$
$\displaystyle=\sum_{u\in S\setminus\\{v\\}}d(u)\cdot\frac{1}{\lambda}$
$\displaystyle\leq d(S)\cdot\frac{\epsilon^{3}}{c\log^{2}n},\mbox{ for some
constant $c>1$}$ $\displaystyle\leq d(S)\cdot\frac{\epsilon^{3}}{\log^{2}n}.$

From Markov’s inequality, it follows that:

$\displaystyle\Pr\left[d(S^{ta}\setminus\\{v\\})\geq
d(S)\cdot\frac{2\epsilon^{3}}{\log^{2}n}\right]\leq\frac{\operatorname*{{\bf{E}}}[d(S^{ta}\setminus\\{v\\})]}{d(S)\cdot\frac{2\epsilon^{3}}{\log^{2}n}}=\frac{1}{2}.$

So, with probability at least ${1}/{2}$, we have:

$\displaystyle d(S^{ta})$ $\displaystyle=d(v)+d(S^{ta}\setminus\\{v\\})$
$\displaystyle\leq d(v)+{d(S)\cdot\frac{2\epsilon^{3}}{\log^{2}n}}$
$\displaystyle\Longrightarrow{\eta}_{\text{est}}(S^{ta})$
$\displaystyle\leq|\Gamma(S^{ta})\cap(V\setminus S^{ta})|\leq
d(S^{ta},V\setminus S^{ta})\leq d(S^{ta})$
$\displaystyle{\eta}_{\text{est}}(S^{ta})$ $\displaystyle\leq
d(v)+{d(S)\cdot\frac{2\epsilon^{3}}{\log^{2}n}}.$

Using union bound on all possible sets $S^{ta}$ for all $t\in[T]$ and
$a\in[\lambda]$, with probability at least $1-T\cdot\lambda\cdot\delta\geq
1-1/2\log n$, the neighborhood estimates are $(1\pm\epsilon)$-relative
approximations. By taking minimum of all the $T=O(\log n)$ estimates, we argue
that $\widehat{d}(v)$ is a good approximation of $d(v)$. We take minimum of
all the $T$ estimates containing $v$ and obtain the final degree estimate,
given by:

$\hat{d}(v)=\min_{t\in T}{\eta}_{\text{est}}(S^{ta}).$

We observe that:

$\displaystyle\Pr\left[\hat{d}(v)<(1-3\epsilon)d(v)\right]$
$\displaystyle=\Pr\left[\left\\{\min_{t\in
T}{\eta}_{\text{est}}(S^{ta})\right\\}<(1-3\epsilon)d(v)\right]$
$\displaystyle=\prod_{t\in
T}\Pr\left[{\eta}_{\text{est}}(S^{ta})<(1-3\epsilon)d(v)\right]$
$\displaystyle\leq\left(\frac{1}{2}\right)^{T}\leq\frac{1}{2n^{4}},\mbox{and
}$
$\displaystyle\Pr\left[\hat{d}(v)>d(v)+{d(S)\cdot\frac{2\epsilon^{3}}{\log^{2}n}}\right]$
$\displaystyle=\Pr\left[\left\\{\min_{t\in
T}{\eta}_{\text{est}}(S^{ta})\right\\}>d(v)+{d(S)\cdot\frac{2\epsilon^{3}}{\log^{2}n}}\right]$
$\displaystyle=\prod_{t\in
T}\Pr\left[{\eta}_{\text{est}}(S^{ta})>d(v)+{d(S)\cdot\frac{2\epsilon^{3}}{\log^{2}n}}\right]$
$\displaystyle\leq\left(\frac{1}{2}\right)^{T}\leq\frac{1}{2n^{4}}.$

By taking a union bound on all the vertices in $S$ and the event that
neighborhood estimates are accurate, the total failure probability is at most
$1/2\log n+1/n^{3}\leq 1/\log n$. Therefore, for every vertex $v\in S^{ta}$,
we have with probability at least $1-1/\log n$:

$(1-3\epsilon)d(v)\leq{\eta}_{\text{est}}(S^{ta})\leq
d(v)+{d(S)\cdot\frac{2\epsilon^{3}}{\log^{2}n}}.$

Set $\epsilon=\epsilon/2^{1/3}$ to appropriately scale the value of $\epsilon$
for the final guarantees. Algorithm 2 uses $O(\epsilon^{-3}\log^{2}n\cdot T)$
many calls to the sub-routine Neighborhood-Size, i.e., Algorithm 1. From Lemma
9, we know that Algorithm 1 uses $O(\epsilon^{-2}\log n\log(\delta^{-1}\log
n))$ BIS queries, where we set $\delta=O(1/\log^{4}n)$. Therefore, the query
complexity of Algorithm 2 is $O(\epsilon^{-5}\log^{4}n\log(\log n))$.

∎

###  4.3 Edge Estimation

In this section, we describe the algorithm Edge-Estimator that obtains a
$(1\pm\epsilon)$-approximation for the number of edges $m$. The constants used
$c_{1},c_{2}$ satisfy $c_{1}\leq c_{2}/10$ and $c_{2}\geq 50$, and we do not
explicitly mention them for the sake of brevity. Missing details are presented
in the full version.

Our Approach. A naive strategy to estimate the number of edges (denoted by
$m$) is to sample roughly $\tilde{O}(\epsilon^{-2})$ nodes uniformly, and
estimate $m$ given the degrees of the sampled nodes. However, the variance of
such an estimator depends on the maximum degree, which could be as high as
$O(n)$. To fix this issue, we sample vertices at different rates. Our sampling
rates are given by the sequence $1/\gamma^{j}$ where $\gamma>1\textup{ is a
constant, }j\in\\{0,1,\cdots,\log n\\}$. We use the term $j^{th}$ level to
refer to the sampling rate $\gamma^{-j}$. It is easy to observe that when a
vertex $v$ is sampled at rate $\tilde{O}({\epsilon^{-2}d(v)}/{m})$, its
contribution is $\tilde{O}(\epsilon^{2}m)$. In other words, if
$d(v)\approx{\epsilon^{2}m}/{\gamma^{j}}$, for some sampling level $j$, we can
use it in our estimator. However, there are three main challenges in
implementing this approach which we detail below.

Approximate degrees. Algorithm Estimate-Degree returns degree estimates that
are _approximate_ with an additive approximation error of
$\tilde{O}\left({\epsilon^{3}m}/{\gamma^{j}}\right)$ at sampling level $j$. To
include a vertex $v$, we have to ensure that this error term is small and
given by $O(\epsilon d(v))$. When
$d(v)=\tilde{\Omega}({\epsilon^{2}m}/{\gamma^{j}})$, the returned degree
estimate $\widehat{d}(v)$ will be a $(1\pm\epsilon)$-approximation to the
actual degree $d(v)$. Observe that this corresponds to the threshold we
mentioned earlier. Therefore, our goal is to identify all vertices at every
level $j$ that pass the threshold of
$\tilde{\Omega}({\epsilon^{2}m}/{\gamma^{j}})$. When that happens, we say that
the vertex $v$ has been recovered at level $j$ and can be safely included in
our estimator.

Knowledge of $m$. As we do not know the value of $m$, we start with an
$O(\log^{2}n)$-relative error approximate estimate, obtained by the Algorithm
CoarseEstimator in Beame et al. [BHPR+18]. We repeatedly refine the
approximate estimate using Algorithm Refine-Estimate, until we get a
$(1\pm\epsilon)$-relative error approximation of $m$. Each _refinement_
improves the approximation factor from the previous stage by a multiplicative
factor of $\epsilon$. We note that each refinement does not require any
additional BIS queries and uses the approximate degree estimates obtained
previously.

Boundary Vertices. It is possible that some vertices have degrees close to the
threshold values at each sampling level. We denote such vertices
$V_{\textup{boundary}}$ and refer to them as _boundary vertices_. For such
boundary vertices, as we use approximate degree estimates, they might be
recovered at a level different from its true level (defined with respect to
exact degrees). Such a scenario could potentially affect the contribution of
the recovered vertex in our estimator by an additional multiplicative factor
dependent on $\gamma$ and the difference between recovered level and true
level. As a result, our estimator might not be a $(1\pm\epsilon)$-relative
error approximation anymore. We get around this limitation by dividing the
region between any two consecutive levels into $B$ buckets and shifting the
boundaries of all the levels by a random shift selected uniformly from the
first $B$ buckets. We account for this by changing the sampling rates to
$\gamma^{-\mu(j)}$ where $\mu(j)$ encodes the random shift.

With the random shift of the level boundaries, we ensure that every vertex
will lie close to the boundary with probability at most $\epsilon$. Moreover,
we argue that every boundary vertex is recovered at its true level or level
adjacent to its true level. Therefore, the total contribution of
$V_{\textup{boundary}}$ to our edge estimator is $O(\epsilon m)$.

####  4.3.1 Overview of Algorithm Edge-Estimator

Random Boundary Shift. Let $\epsilon$ denote the approximation parameter,
$B=2/\epsilon$ denote the total number of buckets between two consecutive
levels and $\gamma=1/(1-\epsilon)$ the probability of sampling parameter. The
region between two consecutive levels is divided into $B$ buckets with the
boundaries of buckets proportional to the values given by
$\\{[1/\gamma^{B},1/\gamma^{B-1}),\cdots,[1/\gamma^{2},1/\gamma),[1/\gamma,1)\\}$.
We select a random integer offset for shifting our levels, denoted by $s$,
which is selected uniformly at random from $[0,B)$. Now, the level boundaries
are located at values proportional to $\gamma^{-\mu(j)}$ where $\mu(j)=j\cdot
B-s$ and $0\leq j\leq L$. Observe that the number of sampling levels is given
by $L=\frac{1}{B}\cdot\log_{\gamma}n+1\leq\frac{1}{2}\log n+1$.

Algorithm 3 Edge-Estimator: Non-adaptive algorithm for estimating edges

1:Input: $V$ set of $n$ vertices and $\epsilon>0$ error parameter.

2:Output: Estimate $\widehat{m}$ of number of edges in $G$.

3:Scale $\epsilon\leftarrow\frac{\epsilon}{600\log_{1/\epsilon}\log n}$ and
initialize $\gamma\leftarrow{1}/{(1-\epsilon)}$ and
$B\leftarrow{2}/{\epsilon}$.

4:Let $s$ be an integer selected uniformly at random from the interval
$[0,B)$.

5:Let $\mu(j)\leftarrow-s+j\cdot B$ for every integer $j$ in the interval
$\left[0,\frac{1}{B}\cdot\log_{\gamma}n+1\right].$

6:Initialize $S_{0}\leftarrow V$ and construct $S_{1}$ by sampling vertices in
$S_{0}$ with probability $1/\gamma^{\mu(1)}$.

7:Construct $S_{2}\supseteq\ldots\supseteq S_{L}$ for
$L=\frac{1}{B}\cdot\log_{\gamma}n$ where each $S_{j}$ is obtained by sampling
vertices in $S_{j-1}\ \forall j\geq 2$, independently with probability
$1/\gamma^{B}$.

8:for $j=0,1,\ldots L$ do

9: Run Estimate-Degree ($S_{j}$) to obtain the estimates $\widehat{d}_{j}(v)$
for all $v\in S_{j}$ satisfying:  $(1-\epsilon)d(v)\leq\widehat{d}_{j}(v)\leq
d(v)+\frac{c_{1}\epsilon^{3}\cdot m}{\log n\cdot\gamma^{\mu(j)}}.$

10:end for

11:Let $\bar{m}_{0}$ be the $O(\log n)$-approximate estimate from the
Algorithm CoarseEstimator in Beame et al. [BHPR+18] on a random partition of
$V$.

12:Set $\bar{m}_{0}\leftarrow\max\\{2,16\log n\cdot\bar{m}_{0}\\}$, so that we
have $m\leq\bar{m}_{0}\leq(64\log^{2}n)\cdot m.$

13:for $t=1,2,\cdots,T=2\log_{1/\epsilon}\log n$ do

14: $\bar{m}_{t}$ is assigned the output of Refine-Estimate that takes as
input approximate degree values $\widehat{d}_{j}(v)\ \forall v\in S_{j}\
\forall j\in[L]$, the previous estimate $\bar{m}_{t-1}$ and the iteration $t$.

15:end for

16:return $\widehat{m}\leftarrow\bar{m}_{T}$.

In Algorithm Edge-Estimator, we construct sets $V=S_{0}\supseteq
S_{1}\supseteq\cdots\supseteq S_{L}$ where a set $S_{j}$ (for all $j\geq 2$)
is obtained by sampling vertices in $S_{j-1}$ with probability $1/\gamma^{B}$.
The set $S_{1}$ is obtained by sampling vertices in $V$ with probability
$1/\gamma^{-s+B}$. Our sampling scheme results in each vertex being included
in a set $S_{j}$ with probability $1/\gamma^{\mu(j)}$. We can easily show that
with constant probability, $d(S_{j})=O({m\log n}/{\gamma^{\mu(j)}})$, for all
$j$. Using Algorithm 2, we obtain approximate degree estimates of vertices in
$S_{j}$ for every sampling level $j\leq L$ with an approximation error of
$O\left({\epsilon^{3}}/\log^{2}n\cdot
d(S_{j})\right)=O\left({m\epsilon^{3}}/{\gamma^{\mu(j)}\log n}\right)$. By
starting with a bad estimate $\bar{m}_{0}$ for the total number of edges $m$
and initialized to a $O(\log^{2}n)$-approximate estimate, we refine it to
obtain an improved estimate $\bar{m}_{1}$. We repeat this process
$T=2\log_{1/\epsilon}\log n$ times, such that the estimate $\bar{m}_{t-1}$ is
used to construct an improved estimate $\bar{m}_{t}$. Finally, we return the
estimate $\bar{m}_{T}$ as our final estimate for $m$.

Algorithm 4 Refine-Estimate: Refines the current estimate of number of edges

1:Input: $\bar{m}$ satisfying $m\leq\bar{m}\leq m(1+\alpha)$, approximate
degree values $\widehat{d}_{j}(v)\ \forall v\in S_{j}\ \forall j\in[L]$
obtained using Algorithm 3, $\bar{m}_{0}$, and iteration $t$.

2:Output: Estimate $\widehat{m}$ satisfying $m\leq\widehat{m}\leq
m(1+\epsilon\cdot\alpha)$ of number of edges in $G$.

3:Initialize $\widehat{m}\leftarrow 0$.

4:Initialize $r(v)\leftarrow 0$ for all $v$ (indicator if $v$ has been
recovered yet).

5:for $j=0,1,\ldots L$ do

6: for $v\in S_{j}$ do

7: if $r(v)=0$ and
$\widehat{d}_{j}(v)\geq\frac{\bar{m}}{\gamma^{\mu(j)}}\cdot\frac{c_{2}\epsilon^{2}}{\log
n}$ then

8: $\widehat{m}\leftarrow\widehat{m}+{\gamma^{\mu(j)}}\cdot\widehat{d}(v)$

9: $\widehat{\ell}(v)\leftarrow j$ and $r(v)\leftarrow 1$.

10: end if

11: end for

12:end for

13:if $t<T=2\log_{1/\epsilon}\log n$ then

14: $\widehat{m}={\widehat{m}}/2+\left(\epsilon\log\log
n\right)^{t}\bar{m}_{0}$. $\triangleright$ We normalize $\widehat{m}$ so that
we have $\widehat{m}\geq m$.

15:else

16: $\widehat{m}=\widehat{m}/2$.

17:end if

18:return $\widehat{m}$.

Overview of Algorithm Refine-Estimate. Suppose we are given an initial
estimate $\bar{m}$ satisfying $m\leq\bar{m}\leq(1+\alpha)m$ for some unknown
approximation factor $\alpha$ satisfying $\epsilon\leq\alpha\leq\binom{n}{2}$.
We set the threshold value for recovering a vertex at a level $j$ as
$\frac{\bar{m}}{\gamma^{\mu(j)}}\cdot\frac{c_{2}\epsilon^{2}}{\log n}$ where
$c_{2}$ is a constant. So, when a vertex $v$ with degree estimate
$\widehat{d}_{j}(v)$ (obtained from Algorithm 3) satisfies
$\widehat{d}_{j}(v)\geq\frac{\bar{m}}{\gamma^{\mu(j)}}\cdot\frac{c_{2}\epsilon^{2}}{\log
n}$, we set the level of recovery $\widehat{\ell}(v)=j$ and recovered flag
$r(v)=1$. From construction, we can observe that once a vertex is recovered at
a particular level it is not available to be recovered at higher level later.
Our estimator is the summation of terms
$\gamma^{\mu(\widehat{\ell}(v))}\cdot\widehat{d}(v)$ for every $v$ satisfying
$r(v)=1$. We normalize $\widehat{m}$ to ensure that the final estimate
returned satisfies $m\leq\widehat{m}$ (see the full version for additional
details).

Using Bernstein’s inequality, we argue that in iteration $t$, we can improve
the approximation factor of the previous estimate $\bar{m}_{t-1}$ by a
multiplicative factor of $\epsilon$ in the new estimate $\bar{m}_{t}$. After
$T=O(\log_{1/\epsilon}\log n)$ iterations, the edge estimate will be a
$(1\pm\epsilon)$-relative error approximation satisfying:

######  Theorem 11.

Given a graph $G$ with $n$ nodes and $m$ edges, there is an algorithm that
makes $O(\epsilon^{-5}\log^{5}n\log^{6}(\log n))$ non-adaptive BIS queries to
$G$ and returns an estimate $\widehat{m}$ satisfying:
$m(1-\epsilon)\leq\widehat{m}\leq m(1+\epsilon),\textup{with probability at
least }3/5$.

####  4.3.2 Proof of Theorem 11

First, we show that our degree estimates are calculated accurately at every
level with constant probability of success.

######  Claim 12.

With probability $3/4$, for all levels $j\in\\{1,2,\cdots,L\\}$, we have:

$d(S_{j})\leq\frac{8m\cdot L}{\gamma^{\mu(j)}}.$

###### Proof.

As every vertex is included in $S_{j}$ with probability $1/\gamma^{\mu(j)}$,
we get:

$\operatorname*{{\bf{E}}}[d(S_{j})]=\frac{\sum_{v\in
V}d(v)}{\gamma^{\mu(j)}}=\frac{2m}{\gamma^{\mu(j)}}$

Therefore, by Markov’s Inequality, $\Pr[d(S_{j})\geq{8m\cdot
L}/{\gamma^{\mu(j)}}]\leq{1}/{(4L)}$. Taking a union bound over all the
levels, with probability at least 3/4,

$d(S_{j})\leq{8m\cdot L}/\gamma^{\mu(j)}\leq{8m\cdot\log
n}/\gamma^{\mu(j)}\textup{for every level }j\in[L].$

∎

Combining Claim 12 and Lemma 10, for sufficiently large $n$, we have:

######  Corollary 13.

The degree estimates returned by Algorithm 2 for each sampling level
$j\in[L]$, satisfy the following with probability at least $0.70$:

$(1-\epsilon)d(v)\leq\widehat{d}_{j}(v)\leq
d(v)+\frac{c_{1}\epsilon^{3}m}{\gamma^{\mu(j)}\log n}\ \quad\forall v\in
S_{j}.$

###### Proof.

From Lemma 10, we have that, for every $j\in[L]$, with probability at least
$1-O(1/\log n)$, the approximate degree estimates satisfy:

$(1-\epsilon)d(v)\leq\widehat{d}_{j}(v)\leq
d(v)+\frac{\epsilon^{3}}{\log^{2}n}\cdot d(S_{j})\ \quad\forall v\in S_{j}.$

From Claim 12, we know that $d(S_{j})\leq 8m\cdot\log n/\gamma^{\mu(j)}$, for
every level $j\in[L]$, with probability at least $3/4$. Combining both of
them, we have the claim about the approximate degree estimates.

Using union bound, we have that the total failure probability is at most
$1/4+O(L\cdot 1/\log n)\leq 0.30$, as $L=O(\log n)$. Hence, the corollary. ∎

For each vertex $v\in S$ for some subset $S\subseteq V$, we associate a level
$\ell(v)$ such that the _actual_ degree of $v$ is a large fraction of the
total degree of $S$, i.e., $\ell(v)$ is the minimum $j\in\\{0,1,\cdots,L\\}$
satisfying
$d(v)\geq\frac{\bar{m}}{\gamma^{\mu(j)}}\cdot\frac{c_{2}\epsilon^{2}}{\log
n}$. The value
$\frac{\bar{m}}{\gamma^{\mu(j)}}\cdot\frac{c_{2}\epsilon^{2}}{\log n}$ is
called threshold for level $\ell(v)$, and it depends on the estimate $\bar{m}$
for the number of edges $m$.

######  Definition 14 (Actual Level).

For every vertex $v\in V$, we associate a level $\ell(v)$ defined as

$\ell(v)=\arg\min_{j\in\\{0,1,\cdots,L\\}}d(v)\geq\frac{\bar{m}}{\gamma^{\mu(j)}}\cdot\frac{c_{2}\epsilon^{2}}{\log
n}.$

The vertices that lie close to the threshold of a level and within a
$\gamma$-multiplicative factor are called the boundary vertices and are
defined as below:

######  Definition 15 (Boundary vertices).

The vertices closer to the _boundary_ are denoted by the set:

$\displaystyle V_{\textup{boundary}}$ $\displaystyle=\\{v\mid
d(v)\in\left[\frac{\bar{m}\cdot c_{2}\epsilon^{2}}{\gamma^{\mu(\ell(v))}\log
n},\frac{\bar{m}\cdot c_{2}\epsilon^{2}}{\gamma^{\mu(\ell(v))-1}\log
n}\right)\textup{ or }d(v)\in\left(\frac{\bar{m}\cdot
c_{2}\epsilon^{2}}{\gamma^{\mu(\ell(v)-1)+1}\log n},\frac{\bar{m}\cdot
c_{2}\epsilon^{2}}{\gamma^{\mu(\ell(v)-1)}\log n}\right)\\}.$

######  Claim 16.

For any vertex $v\in V$, with probability $1-\epsilon$, there is some
$j\in\\{0,1,\cdots,L\\}$ such that:

$\frac{\bar{m}}{\gamma^{\mu(j)-1}}\cdot\frac{c_{2}\epsilon^{2}}{\log n}\leq
d(v)\leq\frac{\bar{m}}{\gamma^{\mu(j-1)+1}}\cdot\frac{c_{2}\epsilon^{2}}{\log
n}.$

In other words, $\Pr[v\in V_{\textup{boundary}}]\leq\epsilon$.

###### Proof.

For notational convenience, let $\sigma=\frac{\bar{m}\cdot
c_{2}\epsilon^{2}}{\log n}$. Note that for any $v\in V$ there is some $j$ such
that $\frac{\sigma}{\gamma^{\mu(j)}}\leq
d(v)<\frac{\sigma}{\gamma^{\mu(j-1)}}$. We claim that every such vertex will
not lie close to the edges of the interval
$\left[\frac{\sigma}{\gamma^{\mu(j)}},\frac{\sigma}{\gamma^{\mu(j-1)}}\right)$,
i.e.,
$d(v)\not\in\left[\frac{\sigma}{\gamma^{\mu(j)}},\frac{\sigma}{\gamma^{{\mu(j)}-1}}\right)$
and
$d(v)\not\in\left[\frac{\sigma}{\gamma^{\mu(j-1)+1}},\frac{\sigma}{\gamma^{\mu(j-1)}}\right)$.
We will show that both events occur with probability at most $1/B$, giving the
claim via a union bound.

For any $v$, there is a unique $i$ such that
$d(v)\in\left[\frac{\sigma}{\gamma^{i}},\frac{\sigma}{\gamma^{i-1}}\right)$.
Thus, the claim only fails to hold if $i=\mu(j)$ for some $j$ or
$i=\mu(j-1)+1$ for some $j$. For the first case, when $i=\mu(j)=j\cdot B-s$
for some $j$ is satisfied only if $s=j\cdot B-i$, which occurs with
probability $1/B$ since $s$ is selected uniformly at random from
$\\{0,1,\ldots,B-1\\}$. Similarly, $i=\mu(j-1)+1=(j-1)\cdot B+1-s$ only if
$s=(j-1)\cdot B+1-i$, which again occurs with probability $1/B$. Using union
bound, we have:

$\Pr\left[d(v)\in\left[\frac{\sigma}{\gamma^{\mu(j)}},\frac{\sigma}{\gamma^{{\mu(j)}-1}}\right)\textup{
or
}d(v)\in\left[\frac{\sigma}{\gamma^{\mu(j-1)+1}},\frac{\sigma}{\gamma^{\mu(j-1)}}\right)\right]\leq\frac{2}{B}=\epsilon.$

Hence, the claim. ∎

######  Definition 17 (Recovered Level).

A vertex $v$ is recovered at level $\widehat{\ell}(v)$ iff

$\widehat{\ell}(v)=\arg\min_{j\in[L]}\widehat{d}_{j}(v)\geq\frac{\bar{m}}{\gamma^{\mu(j)}}\cdot\frac{c_{2}\epsilon^{2}}{\log
n}.$

We associate the following sets with the set of recovered vertices:

$\mathcal{R}=\\{v\in V\mid
r(v)=1\\},\mathcal{R}_{\textup{bad}}=\\{v\in\mathcal{R}\mid\widehat{\ell}(v)\neq\ell(v)\\},\textup{
and }\mathcal{R}_{\textup{boundary}}=\mathcal{R}\cap V_{\textup{boundary}}.$

Here, $\mathcal{R}_{\textup{bad}}$ represents set of recovered vertices $v$ at
a level $\widehat{\ell}(v)$ different from $\ell(v)$. Recall that $\ell(v)$
represents the level at which the vertex $v$ is recovered if we knew the
degree $d(v)$ exactly.

Using the next claim, we argue that if $v$ is included in the set of sampled
vertices at level $\ell(v)$, i.e., $v\in S_{\ell(v)}$, then, it will be
recovered at that level, provided degree estimates satisfy Corollary 13.

######  Claim 18.

Suppose $v\in S_{\ell(v)}$ and $v\not\in V_{\textup{boundary}}$ satisfying:

$(1-\epsilon)d(v)\leq\widehat{d}_{\widehat{\ell}(v)}(v)\leq
d(v)+\frac{c_{1}\epsilon^{3}\cdot m}{\log
n\cdot\gamma^{\mu(\widehat{\ell}(v))}},\text{then, we have
}\widehat{\ell}(v)=\ell(v).$

###### Proof.

As $v\not\in V_{\textup{boundary}}$, and $v\in S_{\ell(v)}$, from the
definition of boundary vertices, we have:

$\displaystyle\frac{\bar{m}}{\gamma^{\mu(\ell(v))-1}}\cdot\frac{c_{2}\epsilon^{2}}{\log
n}\leq
d(v)\leq\frac{\bar{m}}{\gamma^{\mu(\ell(v)-1)+1}}\cdot\frac{c_{2}\epsilon^{2}}{\log
n}.$

This implies:

$\displaystyle\widehat{d}_{\ell(v)}(v)\geq(1-\epsilon)d(v)$
$\displaystyle\geq(1-\epsilon)\cdot\frac{\bar{m}}{\gamma^{\mu(\ell(v))-1}}\cdot\frac{c_{2}\epsilon^{2}}{\log
n}$
$\displaystyle=(1-\epsilon)\gamma\cdot\frac{\bar{m}}{\gamma^{\mu(\ell(v))}}\cdot\frac{c_{2}\epsilon^{2}}{\log
n}$
$\displaystyle=\frac{\bar{m}}{\gamma^{\mu(\ell(v))}}\cdot\frac{c_{2}\epsilon^{2}}{\log
n},$

as $\gamma={1}/{(1-\epsilon)}$, and so in Algorithm Refine-Estimate (Alg. 4),
$v$ will be recovered, and $\widehat{\ell}(v)=\ell(v)$ as long as it hasn’t
been recovered at a prior level.

At any prior level $j\leq\ell(v)-1$, from Lemma 10, we have:

$\displaystyle\widehat{d}_{j}(v)$ $\displaystyle\leq
d(v)+\frac{c_{1}\epsilon^{3}\cdot m}{\log n\cdot\gamma^{\mu(j)}}$
$\displaystyle\leq\frac{\bar{m}}{\gamma^{\mu(\ell(v)-1)+1}}\cdot\frac{c_{2}\epsilon^{2}}{\log
n}+\frac{c_{1}\epsilon^{3}\cdot m}{\log n\cdot\gamma^{\mu(j)}}$
$\displaystyle\leq\frac{\bar{m}}{\gamma^{\mu(j)}}\cdot\frac{c_{2}\epsilon^{2}}{\log
n}\cdot\left(\frac{1}{\gamma\cdot\gamma^{(\ell(v)-1-j)\cdot
B}}+\frac{c_{1}\epsilon}{c_{2}}\right)$
$\displaystyle\leq\frac{\bar{m}}{\gamma^{\mu(j)}}\cdot\frac{c_{2}\epsilon^{2}}{\log
n}\left(\frac{1}{\gamma}+\frac{c_{1}\epsilon}{c_{2}}\right)$
$\displaystyle=\frac{\bar{m}}{\gamma^{\mu(j)}}\cdot\frac{c_{2}\epsilon^{2}}{\log
n}\left(1-\epsilon+\frac{c_{1}\epsilon}{c_{2}}\right)$
$\displaystyle<\frac{\bar{m}}{\gamma^{\mu(j)}}\cdot\frac{c_{2}\epsilon^{2}}{\log
n},$

as long as we set $c_{1}<c_{2}$. Thus, $v$ will be rejected at any level
$j<\ell(v)$. ∎

The following corollary is immediate from the previous Claim 18, as every
vertex that is not at the boundary is recovered at the actual level.

######  Corollary 19.

If all the degree estimates of sampled vertices at every level are good
approximations, i.e., satisfy the Corollary 13, then,
$\mathcal{R}_{\textup{bad}}\subseteq\mathcal{R}_{\textup{boundary}}\subseteq
V_{\textup{boundary}}$.

For a vertex $v$ that lies in the boundary, i.e., $v\in
V_{\textup{boundary}}$, it is possible that $v$ is recovered at a level far
away from $\ell(v)$. Using the next claim, we argue that it will be recovered
in the adjacent levels if it has not been recovered at $\ell(v)$.

######  Claim 20.

Suppose $v\in S_{\ell(v)+1}$ and $v\in V_{\textup{boundary}}$ satisfying:

$(1-\epsilon)\leq\widehat{d}_{\widehat{\ell}(v)}(v)\leq
d(v)+\frac{c_{1}\epsilon^{3}\cdot m}{\log
n\cdot\gamma^{\mu(\widehat{\ell}(v))}},\text{ then, we have
}\widehat{\ell}(v)\in\\{\ell(v)+1,\ell(v),\ell(v)-1\\}.$

###### Proof.

For notational convenience, let $\sigma=\frac{\bar{m}\cdot
c_{2}\epsilon^{2}}{\log n}$. As $v\in S_{\ell(v)+1}$, we have $v\in
S_{\ell(v)-1}$ and $v\in S_{\ell(v)}$ from construction.

First, we observe that $\widehat{\ell}(v)\leq\ell(v)+1$, because,

$\widehat{d}_{\widehat{\ell}(v)}(v)\geq(1-\epsilon)d(v)\geq(1-\epsilon)\frac{\sigma}{\gamma^{\mu(\ell(v))}}\geq(1-\epsilon)\gamma^{B}\frac{\sigma}{\gamma^{\mu(\ell(v)+1)}}\geq\frac{\sigma}{\gamma^{\mu(\ell(v)+1)}}.$

The last inequality follows from
$(1-\epsilon)\gamma^{B}\geq(1-\epsilon)(1+\epsilon)^{B}\geq 3-3\epsilon\geq
1$, when $\epsilon\leq\frac{2}{3}$.

As $v\in V_{\textup{boundary}}$, we have the following cases:

  * (a)

$d(v)\in\left(\frac{\sigma}{\gamma^{\mu(\ell(v)-1)+1}},\frac{\sigma}{\gamma^{\mu(\ell(v)-1)}}\right)$.
We use proof by contradiction. Suppose $\widehat{\ell}(v)\leq\ell(v)-2$. Then:

$\displaystyle\widehat{d}_{\widehat{\ell}(v)}(v)$ $\displaystyle\leq
d(v)+\frac{c_{1}\epsilon^{3}\cdot m}{\log
n\cdot\gamma^{\mu(\widehat{\ell}(v))}}$
$\displaystyle<\frac{\bar{m}}{\gamma^{\mu(\ell(v)-1)}}\cdot\frac{c_{2}\epsilon^{2}}{\log
n}+\frac{c_{1}\epsilon^{3}\cdot m}{\log
n\cdot\gamma^{\mu(\widehat{\ell}(v))}}$
$\displaystyle=\frac{\bar{m}}{\gamma^{\mu(\widehat{\ell}(v))}}\cdot\frac{c_{2}\epsilon^{2}}{\log
n}\cdot\left(\frac{1}{\gamma^{(\ell(v)-1-\widehat{\ell}(v))\cdot
B}}+\frac{c_{1}\epsilon}{c_{2}}\right)$
$\displaystyle\leq\frac{\bar{m}}{\gamma^{\mu(\widehat{\ell}(v))}}\cdot\frac{c_{2}\epsilon^{2}}{\log
n}\left(\frac{1}{\gamma^{B}}+\frac{c_{1}\epsilon}{c_{2}}\right)$
$\displaystyle=\frac{\bar{m}}{\gamma^{\mu(\widehat{\ell}(v))}}\cdot\frac{c_{2}\epsilon^{2}}{\log
n}\left((1-\epsilon)^{B}+\frac{c_{1}\epsilon}{c_{2}}\right)$
$\displaystyle\leq\frac{\bar{m}}{\gamma^{\mu(\widehat{\ell}(v))}}\cdot\frac{c_{2}\epsilon^{2}}{\log
n}\left(e^{-2}+\frac{c_{1}\epsilon}{c_{2}}\right)\leq\frac{\bar{m}}{\gamma^{\mu(\widehat{\ell}(v))}}\cdot\frac{c_{2}\epsilon^{2}}{\log
n}.$

The last inequality follows because $c_{1}\leq c_{2}(1-e^{-2})$. Therefore,
$\widehat{\ell}(v)>\ell(v)-2$.

  * (b)

$d(v)\in\left[\frac{\sigma}{\gamma^{\mu(\ell(v))}},\frac{\sigma}{\gamma^{\mu(\ell(v))-1}}\right).$
Using a similar argument, we obtain that $\widehat{\ell}(v)\geq\ell(v)$.

For the sake of contradiction, let $\widehat{\ell}(v)\leq\ell(v)-1$. Then:

$\displaystyle\widehat{d}_{\widehat{\ell}(v)}(v)$ $\displaystyle\leq
d(v)+\frac{c_{1}\epsilon^{3}\cdot m}{\log
n\cdot\gamma^{\mu(\widehat{\ell}(v))}}$
$\displaystyle<\frac{\bar{m}}{\gamma^{\mu(\ell(v))-1}}\cdot\frac{c_{2}\epsilon^{2}}{\log
n}+\frac{c_{1}\epsilon^{3}\cdot m}{\log
n\cdot\gamma^{\mu(\widehat{\ell}(v))}}$
$\displaystyle=\frac{\bar{m}}{\gamma^{\mu(\widehat{\ell}(v))}}\cdot\frac{c_{2}\epsilon^{2}}{\log
n}\cdot\left(\frac{\gamma}{\gamma^{(\ell(v)-\widehat{\ell}(v))\cdot
B}}+\frac{c_{1}\epsilon}{c_{2}}\right)$
$\displaystyle\leq\frac{\bar{m}}{\gamma^{\mu(\widehat{\ell}(v))}}\cdot\frac{c_{2}\epsilon^{2}}{\log
n}\left(\frac{2}{\gamma^{B}}+\frac{c_{1}\epsilon}{c_{2}}\right)$
$\displaystyle=\frac{\bar{m}}{\gamma^{\mu(\widehat{\ell}(v))}}\cdot\frac{c_{2}\epsilon^{2}}{\log
n}\left(2(1-\epsilon)^{B}+\frac{c_{1}\epsilon}{c_{2}}\right)$
$\displaystyle\leq\frac{\bar{m}}{\gamma^{\mu(\widehat{\ell}(v))}}\cdot\frac{c_{2}\epsilon^{2}}{\log
n}\left(2e^{-2}+\frac{c_{1}\epsilon}{c_{2}}\right)\leq\frac{\bar{m}}{\gamma^{\mu(\widehat{\ell}(v))}}\cdot\frac{c_{2}\epsilon^{2}}{\log
n}.$

The last inequality follows because $c_{1}\leq c_{2}(1-2e^{-2})$. Therefore,
$\widehat{\ell}(v)>\ell(v)-1$.

Therefore, we have $\ell(v)-2<\widehat{\ell}(v)\leq\ell(v)+1$. ∎

######  Definition 21 (Random variables).

Let $\widehat{X}(v)$ be the random variable with
$\widehat{X}(v)=\gamma^{\mu(\widehat{\ell}(v))}\cdot\widehat{d}(v)$ if $v$ is
recovered at level $\widehat{\ell}(v)$ and $\widehat{X}(v)=0$ otherwise. We
define $X(v)$ similarly, assuming we run Algorithm 4 with exact degrees, i.e.,
$X(v)=\gamma^{\mu(\ell(v))}\cdot d(v)$ if $v$ is recovered at its actual level
$\ell(v)$ and $X(v)=0$ otherwise.

In the analysis that follows next, we will argue that for most of the vertices
in $\mathcal{R}$, except for those in $\mathcal{R}_{\textup{boundary}}$, the
$\widehat{X}(v)$ and $X(v)$ are close to each other, i.e., $1\pm\epsilon$
approximations of each other. Separately, we show that the contribution of
$\sum_{v\in\mathcal{R}_{\textup{boundary}}}\widehat{X}(v)$ is small. As $X(v)$
values do not contain any degree approximations, they are easier to handle and
we will show concentration for $\sum_{v\in\mathcal{R}}X(v)$. As a result, the
concentration will also hold for the actual estimate
$\sum_{v\in\mathcal{R}}\widehat{X}(v)$.

Throughout the remaining section, unless explicitly stated otherwise, we will
assume that the degrees are _good_ approximations. Formally stated, we define
$\mathcal{E}_{0}$ as the event indicating all the degree estimates at every
sampling level satisfy Corollary 13. Note that $\Pr[\mathcal{E}_{0}]\geq 0.70$
(from Corollary 13).

######  Claim 22.

With probability at least $1-1/11\log\log n$, we have:

$\sum_{v\in\mathcal{R}_{\textup{boundary}}}\widehat{X}(v)\leq 572\epsilon
m\log\log n\quad\text{ and }\sum_{v\in\mathcal{R}_{\textup{boundary}}}X(v)\leq
44\epsilon m\log\log n.$

###### Proof.

For the sake of brevity, we omit that all the expected values include
conditioning on the event $\mathcal{E}_{0}$.

Consider a vertex $v\in\mathcal{R}_{\textup{boundary}}$. We have that the
probability a vertex $v\in\mathcal{R}_{\textup{boundary}}$ is recovered at a
level $\widehat{\ell}(v)$ satisfying
$\widehat{\ell}(v)\in\\{\ell(v)+1,\ell(v),\ell(v)-1\\}$ (From Claim 20):

$\displaystyle\Pr[v\in\mathcal{R}_{\textup{boundary}}]$
$\displaystyle=\Pr[v\in V_{\textup{boundary}}]\cdot\Pr[v\in\mathcal{R}\mid
v\in V_{\textup{boundary}}]$
$\displaystyle=\sum_{\widehat{\ell}(v)\in\\{\ell(v)+1,\ell(v),\ell(v)-1\\}}\Pr[v\in
V_{\textup{boundary}}]\cdot\Pr[v\in S_{\widehat{\ell}(v)}].$

Therefore, we have:

$\displaystyle\operatorname*{{\bf{E}}}[\widehat{X}(v)]$
$\displaystyle=\sum_{\widehat{\ell}(v)\in\\{\ell(v)+1,\ell(v),\ell(v)-1\\}}\gamma^{\mu(\widehat{\ell}(v))}\widehat{d}_{\widehat{\ell}(v)}\Pr[v\in
V_{\textup{boundary}}]\cdot\Pr[v\in S_{\widehat{\ell}(v)}]$
$\displaystyle\leq\epsilon\cdot\sum_{\widehat{\ell}(v)\in\\{\ell(v)+1,\ell(v),\ell(v)-1\\}}\widehat{d}_{\widehat{\ell}(v)}$
$\displaystyle\leq
3\epsilon\cdot\left(d(v)+\frac{c_{1}\epsilon^{3}m}{\gamma^{\mu(\ell(v)-1)}\log
n}\right)\quad\mbox{(using Corollary~{}\ref{cor:degree_estimates})}$
$\displaystyle=3\epsilon\cdot\left(d(v)+\left(\frac{1}{1-\epsilon}\right)^{B}\cdot\frac{c_{1}\epsilon^{3}m}{\gamma^{\mu(\ell(v))}\log
n}\right)$ $\displaystyle\leq 3\epsilon\cdot\left(d(v)+5\epsilon
d(v)\right),\textup{ because
}d(v)\geq\frac{c_{2}\epsilon^{2}\bar{m}}{\gamma^{\mu(\ell(v))}\log
n}\geq\frac{c_{1}\epsilon^{2}m}{\gamma^{\mu(\ell(v))}\log n}$
$\displaystyle\leq 18\epsilon\cdot d(v)$
$\displaystyle\Rightarrow\operatorname*{{\bf{E}}}\left[\sum_{v\in\mathcal{R}_{\textup{boundary}}}\widehat{X}(v)\right]$
$\displaystyle\leq 18\epsilon\cdot\sum_{v\in V}d(v)\leq 36\epsilon m.$

Using Markov’s inequality, we have
$\sum_{v\in\mathcal{R}_{\textup{bad}}}\widehat{X}_{v}\leq 572\epsilon m\log
n$, with probability $\geq 1-1/22\log\log n$.

Similarly, we can bound the sum:

$\displaystyle\operatorname*{{\bf{E}}}\left[\sum_{v\in\mathcal{R}_{\textup{boundary}}}X(v)\right]\leq\sum_{v\in
V}\epsilon\cdot d(v)\leq 2\epsilon m.$

Using Markov’s inequality, we have, with probability $1-1/22\log\log n$,
$\sum_{v\in\mathcal{R}_{\textup{bad}}}X(v)\leq 44\epsilon m\log\log n$. Taking
a union bound for both the events, gives us the claim. ∎

######  Claim 23.

$\operatorname*{{\bf{E}}}[X(v)]=d(v)\ \forall v\in V$. Also,
$\operatorname*{{\bf{E}}}[\sum_{v\in V}X(v)]=2m$.

###### Proof.

By Claim 18, $X(v)$ is nonzero which requires that $v\in S_{\ell(v)}$. As $v$
is included in $S_{\ell(v)}$ with probability $1/\gamma^{\mu(\ell(v))}$.
Therefore, we have:

$\displaystyle\operatorname*{{\bf{E}}}[X(v)]=\gamma^{\mu(\ell(v))}\cdot
d(v)\cdot 1/\gamma^{\mu(\ell(v))}$ $\displaystyle=d(v)$
$\displaystyle\operatorname*{{\bf{E}}}\left[\sum_{v\in
V}X(v)\right]=\sum_{j\in[L]}\sum_{v\in V\cap
S_{j}}\operatorname*{{\bf{E}}}\left[X(v)\right]$ $\displaystyle=\sum_{v\in
V}d(v)=2m.$

∎

######  Claim 24.

$\left|\sum_{v\in\mathcal{R}\setminus\mathcal{R}_{\textup{boundary}}}\widehat{X}(v)-\sum_{v\in\mathcal{R}\setminus\mathcal{R}_{\textup{boundary}}}X(v)\right|\leq\epsilon\cdot\sum_{v\in\mathcal{R}\setminus\mathcal{R}_{\textup{boundary}}}X(v)$.

###### Proof.

Consider a vertex $v\in\mathcal{R}\setminus\mathcal{R}_{\textup{boundary}}$.
From Claim 18, we have $\widehat{\ell}(v)=\ell(v)$ provided $v\in
S_{\ell(v)}$. As we have already conditioned on the event $\mathcal{E}_{0}$,
from Corollary 13, we have:

$\displaystyle(1-\epsilon)d(v)$ $\displaystyle\leq\hat{d}_{\ell(v)}(v)\leq
d(v)+\frac{c_{1}\epsilon^{3}m}{\gamma^{\mu(\ell(v))}\log n}$
$\displaystyle(1-\epsilon)\gamma^{\mu(\ell(v))}d(v)$
$\displaystyle\leq\gamma^{\mu(\ell(v))}\hat{d}_{\ell(v)}(v)\leq\gamma^{\mu(\ell(v))}d(v)+\gamma^{\mu(\ell(v))}\cdot\frac{c_{1}\epsilon^{3}m}{\gamma^{\mu(\ell(v))}\log
n}$ $\displaystyle\Rightarrow(1-\epsilon)X(v)$
$\displaystyle\leq\hat{X}(v)\leq X(v)+\frac{c_{1}\epsilon^{3}m}{\log n}.$

As $\bar{m}\geq m$ and $c_{2}>c_{1}$, we have:

$d(v)\geq\frac{\bar{m}\cdot c_{2}\epsilon^{2}}{\gamma^{\mu(\ell(v))}\log
n}\geq\frac{m\cdot c_{2}\epsilon^{2}}{\gamma^{\mu(\ell(v))}\log n}$
$\Rightarrow\frac{m\cdot c_{1}\epsilon^{3}}{\log n}\leq\frac{{m}\cdot
c_{2}\epsilon^{3}}{\log n}\leq\gamma^{\mu(\ell(v))}\cdot\epsilon d(v)=\epsilon
X(v).$

Therefore,

$(1-\epsilon)X(v)\leq\hat{X}(v)\leq(1+\epsilon)X(v).$

Thus, if $\widehat{X}(v)$ is nonzero, $(1-\epsilon)\widehat{X}(v)\leq
X(v)\leq(1+\epsilon)\widehat{X}(v)$, which gives the claim after summing up
over all the terms. ∎

######  Claim 25.

The variables $X(v)\ \forall v\in V$ are independent and bounded given by

$X(v)\leq\frac{2\bar{m}\cdot c_{2}\epsilon^{2}}{\log n}$

###### Proof.

Since the vertices are included independently in the sets
$S_{0},\ldots,S_{L}$, the independence of $X(v)$ follows immediately.
Additionally, since $\ell(v)$ is the smallest $j\in\\{0,1,\ldots L\\}$ for
which
$d(v)\geq\frac{\bar{m}}{\gamma^{\mu(j)}}\cdot\frac{c_{2}\epsilon^{2}}{\log n}$
(See the definition of $\ell(v)$ in Claim 18), we obtain
$d(v)\leq\frac{\bar{m}}{\gamma^{\mu(\ell(v)-1)}}\cdot\frac{c_{2}\epsilon^{2}}{\log
n}$. Thus, if $X(v)$ is nonzero,

$\displaystyle X(v)=\gamma^{\mu(\ell(v))}\cdot
d(v)\leq\frac{\gamma^{B}\bar{m}\cdot c_{2}\epsilon^{2}}{\log
n}\leq\frac{1}{(1-\epsilon)^{B}}\cdot\frac{\bar{m}\cdot
c_{2}\epsilon^{2}}{\log n}\leq\frac{2\bar{m}\cdot c_{2}\epsilon^{2}}{\log n}.$

∎

Combining Claims 23 and 25 we obtain:

######  Claim 26.

With probability at least $1-1/n$,
$|\sum_{v}X(v)-2m|\leq\max\\{\epsilon,\epsilon\cdot\alpha\\}\cdot 2m$.

###### Proof.

By Claims 25 and 23, we have:

$\displaystyle\sum_{v\in V}\operatorname*{{\bf{E}}}[(X(v)-d(v))^{2}]$
$\displaystyle=\sum_{v}\operatorname*{{\bf{E}}}[X(v)^{2}]-2d(v)\operatorname*{{\bf{E}}}[X(v)]+d(v)^{2}$
$\displaystyle\leq\sum_{v}\operatorname*{{\bf{E}}}[X(v)^{2}]$
$\displaystyle\leq\frac{2\bar{m}\cdot c_{2}\epsilon^{2}}{\log
n}\cdot\sum_{v\in V}\operatorname*{{\bf{E}}}[X(v)]=\frac{2\bar{m}\cdot 2m\cdot
c_{2}\epsilon^{2}}{\log n}.$

If $\alpha>1$, then, $m\leq\bar{m}\leq m(1+\alpha)\leq 2m\alpha$. From
Bernstein’s inequality (Lemma 5), we have:

$\displaystyle\Pr\left[\left|\sum_{v}X(v)-2m\right|\geq\epsilon^{\prime}\alpha\cdot
m\right]$ $\displaystyle\leq\exp\left(-\frac{\epsilon^{\prime
2}\alpha^{2}\cdot m^{2}}{\frac{2\cdot 2\bar{m}\cdot 2m\cdot
c_{2}\epsilon^{2}}{\log n}+\frac{2}{3}\cdot\frac{2\bar{m}\cdot
c_{2}\epsilon^{2}}{\log n}\cdot{m\epsilon^{\prime}\alpha}}\right)$
$\displaystyle\leq\exp\left(-\frac{\epsilon^{\prime 2}\alpha^{2}\cdot
m^{2}\log n}{{2\cdot 4m\alpha\cdot 2m\cdot
c_{2}\epsilon^{2}}+\frac{2}{3}\cdot{4m\alpha\cdot
c_{2}\epsilon^{2}}\cdot{m\epsilon^{\prime}\alpha}}\right)$
$\displaystyle=\exp\left(-\frac{\epsilon^{\prime 2}\alpha^{2}\log
n}{{16c_{2}\epsilon^{2}\alpha}+\frac{8}{3}\cdot{c_{2}\epsilon^{2}}\cdot{\epsilon^{\prime}\alpha^{2}}}\right)\leq\frac{1}{n},\
\textup{because},$ $\displaystyle\frac{\epsilon^{\prime
2}\alpha^{2}}{{16c_{2}\epsilon^{2}\alpha}+\frac{8}{3}\cdot{c_{2}\epsilon^{2}}\cdot{\epsilon^{\prime}\alpha^{2}}}$
$\displaystyle\geq 1,\textup{as
}1\geq\epsilon^{\prime}\geq\epsilon\left(\frac{56c_{2}}{3}\right)^{1/2}.$

If $\alpha\in[\epsilon^{\prime},1]$, then, $\bar{m}\leq 2m$. From Bernstein’s
inequality (Lemma 5), we have:

$\displaystyle\Pr\left[\left|\sum_{v}X(v)-2m\right|\geq\epsilon^{\prime}\cdot
m\right]$ $\displaystyle\leq\exp\left(-\frac{\epsilon^{\prime 2}\cdot
m^{2}}{\frac{2\cdot 2\bar{m}\cdot 2m\cdot c_{2}\epsilon^{2}}{\log
n}+\frac{2}{3}\cdot\frac{2\bar{m}\cdot c_{2}\epsilon^{2}}{\log
n}\cdot{m\epsilon^{\prime}}}\right)$
$\displaystyle\leq\exp\left(-\frac{\epsilon^{\prime 2}\cdot m^{2}\log
n}{{2\cdot 4m\cdot 2m\cdot c_{2}\epsilon^{2}}+\frac{2}{3}\cdot{4m\cdot
c_{2}\epsilon^{2}}\cdot{m\epsilon^{\prime}}}\right)$
$\displaystyle\leq\exp\left(-\frac{\epsilon^{\prime 2}\log
n}{{64c_{2}\epsilon^{2}}+\frac{16}{3}\cdot{c_{2}\epsilon^{2}}}\right)\leq\frac{1}{n},\
\textup{because},$ $\displaystyle\frac{\epsilon^{\prime
2}}{{64c_{2}\epsilon^{2}}+\frac{16}{3}\cdot{c_{2}\epsilon^{2}}}$
$\displaystyle\geq 1\textup{, as
}1\geq\epsilon^{\prime}\geq\epsilon\left(\frac{208c_{2}}{3}\right)^{1/2}.$

Combining both the statements, and scaling $\epsilon$ gives us the lemma. ∎

Note that Claim 26 basically gives us what we want, after adjusting constants
on $\alpha$ and scaling up our estimate appropriately. We formalize this using
the below lemma:

######  Lemma 27.

Suppose the input $\bar{m}$ to Algorithm Refine-Estimate satisfies
$m\leq\bar{m}\leq m(1+\alpha)$ for some approximation factor
$\epsilon\leq\alpha\leq\frac{\binom{n}{2}}{m}$. Then, with probability
$1-1/11\log\log n-1/n$:

$2m(1-\epsilon\log\log n-\epsilon\cdot\alpha)\leq\sum_{v\in
V}\widehat{X}(v)\leq 2m(1+\epsilon\cdot\log\log n+\epsilon\cdot\alpha).$

###### Proof.

We note that for the vertices that are not recovered, i.e., $r(v)=0$, we have
$\widehat{X}(v)=0$, and therefore need to only consider vertices in
$\mathcal{R}$. From Claim 24, we have:

$\left|\sum_{v\in\mathcal{R}\setminus\mathcal{R}_{\textup{boundary}}}\widehat{X}(v)-\sum_{v\in\mathcal{R}\setminus\mathcal{R}_{\textup{boundary}}}X(v)\right|\leq\epsilon\cdot\sum_{v\in\mathcal{R}\setminus\mathcal{R}_{\textup{boundary}}}X(v)$

Combining it with
$\sum_{v\in\mathcal{R}_{\textup{boundary}}}\widehat{X}(v)\leq 572\epsilon
m\log\log n$ from Claim 22, we have:

$\displaystyle\sum_{v\in\mathcal{R}}\widehat{X}(v)$
$\displaystyle\leq(1+\epsilon)\sum_{v\in\mathcal{R}\setminus\mathcal{R}_{\textup{boundary}}}X(v)+\sum_{v\in\mathcal{R}_{\textup{boundary}}}\widehat{X}(v)$
$\displaystyle\leq(1+\epsilon)\sum_{v\in V}X(v)+572\epsilon m\log\log n$
$\displaystyle\leq 2m(1+\epsilon\cdot\alpha+\epsilon\cdot\log\log n),$

where the last step follows by scaling $\epsilon$ (with a constant)
appropriately. From Claim 22, we have
$\sum_{v\in\mathcal{R}_{\textup{boundary}}}X(v)\leq 44\epsilon m\log\log n$.
Therefore, we get:

$\sum_{v\in
V}X(v)\leq\sum_{v\in\mathcal{R}\setminus\mathcal{R}_{\textup{boundary}}}X(v)+44\epsilon
m\log\log n.$

Similarly, we have:

$\displaystyle\sum_{v\in\mathcal{R}}\widehat{X}(v)$
$\displaystyle\geq(1-\epsilon)\sum_{v\in\mathcal{R}\setminus\mathcal{R}_{\textup{boundary}}}X(v)+\sum_{v\in\mathcal{R}_{\textup{boundary}}}\widehat{X}(v)$
$\displaystyle\geq(1-\epsilon)\sum_{v\in\mathcal{R}\setminus\mathcal{R}_{\textup{boundary}}}X(v)$
$\displaystyle\geq(1-\epsilon)\cdot\sum_{v\in V}X(v)-(1-\epsilon)44\epsilon
m\log\log n$ $\displaystyle\geq 2m(1-\epsilon\log n-\epsilon\cdot\alpha)\geq
2m(1-\alpha\cdot\epsilon\log\log n).$

The last step follows by scaling $\epsilon$ appropriately. Using union bound,
we get the final probability claim. Hence, the lemma. ∎

In Algorithm Refine-Estimate, we start with an estimate $\bar{m}_{0}$ for the
number of edges, due to Beame et al.[BHPR+18]. The estimate for the number of
edges $\bar{m}_{0}$ satisfies $m\leq\bar{m}_{0}\leq m(1+\alpha_{0})$, for some
$\alpha_{0}$. As $m\leq\bar{m}_{0}\leq O(m\log^{2}n)$, the approximation
factor $\alpha_{0}$ could be as large as $O(\log^{2}n)$. In Lemma 27, we
showed that we can improve our estimator by $\epsilon\cdot(\alpha+\log\log n)$
multiplicative factor. We call this multiplicative improvement as
_refinement_. In the next theorem, we argue that our Algorithm 3 which
performs repeated refinements results in a $(1\pm\epsilon)$-approximation.

######  Theorem 28 (Theorem 11 restated).

Given a graph $G$ with $n$ nodes and $m$ edges, there is an algorithm that
makes $O(\epsilon^{-5}\log^{5}n\log^{6}(\log n))$ non-adaptive BIS queries to
$G$ and returns an estimate $\widehat{m}$ satisfying:
$m(1-\epsilon)\leq\widehat{m}\leq m(1+\epsilon),\textup{with probability at
least }3/5$.

###### Proof.

We denote $\epsilon^{\prime}=O(\epsilon\log\log n)$. As $m\leq\bar{m}_{0}\leq
O(m\log^{2}n)$, the approximation factor $\alpha_{0}$ could be as large as
$O(\log^{2}n)$. From Lemma 27, we have that each refinement improves the
approximation factor to $m(1+\epsilon\cdot\alpha+\epsilon\cdot\log n)\leq
m(1+\epsilon^{\prime}\alpha_{0})\leq m+\epsilon^{\prime}m\alpha_{0}$.
Therefore, after $O(\log_{{1}/{\epsilon^{\prime}}}\log n)$ _refinements_ , we
expect the upper bound in the approximation to reduce from $\alpha_{0}\cdot m$
to $O(\epsilon^{\prime}\cdot m)$. However, each _refinement_ worsens the lower
bound from $m$ to $m(1-\epsilon^{\prime}\cdot\alpha)$. In order to maintain
the invariant that the input to Algorithm 4 always satisfies
$\bar{m}_{1}=\widehat{m}\geq m$, we normalize it by adding
$\epsilon^{\prime}m_{0}$. This implies that $\widehat{m}\leq
m+2\epsilon^{\prime}m\alpha_{0}$, and the new approximation factor
$\alpha_{1}\leq 2\epsilon^{\prime}\alpha_{0}$. Continuing this, after
$T-1=3\log_{1/\epsilon^{\prime}}\log n$ refinements, we will have
$\widehat{m}_{T}\leq m+(2\epsilon^{\prime})^{T}m\alpha_{0}$. By scaling
$\epsilon=O(\epsilon/\log\log n)$, we have, $\epsilon^{\prime}\leq 1/c$ for
some integer constant $c>2$ and $\widehat{m}_{T}\leq m+\epsilon\cdot m$. So,
the final estimate $\widehat{m}$ returned satisfies:

$m(1-\epsilon)\leq\widehat{m}\leq m(1+\epsilon)$

For each level of sampling, we use Algorithm 2 to return degree estimates
which requires $O(\epsilon^{-5}\log^{4}n\log(\log n))$ BIS queries and
$O(\epsilon^{-5}\log^{5}n\log^{2}(\log n))$ in total including all the $L$
levels (without scaling of $\epsilon$). As we have scaled by setting
$\epsilon=O(\epsilon/\log\log n)$, the total number of BIS queries is
$O(\epsilon^{-5}\log^{5}n\log^{6}(\log n))$.

Recall that we have conditioned on the event $\mathcal{E}_{0}$ that our degree
estimates are accurate. Using union bound, the total probability of failure
across $O(\log\log n)$ refinements is:

$\Pr[\neg\mathcal{E}_{0}]+(1/10\log\log n+1/n)\cdot\log\log n\leq
0.30+1/11+\log\log n/n\leq 2/5\textup{ for sufficiently large }n.$

Hence, the theorem. ∎

##  5 Non-adaptive algorithms for uniform sampling

In this section, we describe algorithms for sampling a near-uniform edge in
the graph. In Section 5.1, we discuss connections between OR queries
(Definition 4) and BIS queries, and outline an algorithm that takes as input
two disjoint subsets $L,R$ and returns a uniform vertex in $|\Gamma(L)\cap
R|$. Next, in Section 5.2, we use this algorithm to return uniform neighbors
for every vertex in a given subset sampled from $V$. Finally, in Section 5.3,
we combine these neighbors obtained for each vertex, and return a near-uniform
sample among the edges of the graph.

###  5.1 Identifying uniform neighbor of a subset of vertices

We will describe connections between OR queries (Definition 4) and BIS queries
that give us algorithms for sampling uniformly an edge from the neighborhood
of a subset of vertices $L$ in another disjoint subset $R$. This is similar to
Section 4, where we discussed algorithms for counting the number of edges in
the neighborhood of a set $L$ in another disjoint subset $R$.

In [ACK21], the authors discuss various algorithms for the well-studied single
element recovery problem using OR-queries. In the single element recovery
problem, we are given a boolean vector, and we want to identify a non-zero
index (also called element) of the vector.

######  Definition 29 (Single Element Recovery [ACK21]).

Given a boolean vector $x\in\\{0,1\\}^{N}$, return a non-zero element from the
support of $x$, denoted by $\textup{supp}(x)$.

######  Lemma 30 (Lemma 4.3 from [ACK21] restated).

Suppose $x\in\\{0,1\\}^{N}$ is a boolean vector. There is a non-adaptive
randomized algorithm that recovers a uniform element $j\in\textup{supp}(x)$
with probability $1-\delta$ and uses $O(\log^{2}N\log(1/\delta))$ OR queries.

Simulating a BIS query using OR query. We start with an observation that any
BIS query can be simulated using a single OR query. An OR query (Definition 4)
takes as input a subset $S\subseteq V\times V$ of pairs of vertices and
returns if an edge of the graph is present among the subset. Therefore, a BIS
query $\mathcal{BIS}(L,R)$ is equivalent to an OR query of the subset
$S=\\{(u,v)\mid u\in L,v\in R\\}$.

Now, we will show a connection in the other direction for the problem of
single element recovery, i.e., we show that OR queries used for finding single
element recovery can be simulated using appropriate BIS queries.

Suppose we are given two disjoint subsets $L,R\subseteq V$, and we want to
output a neighbor of $L$ in $R$, i.e., a vertex in the set $\Gamma(L)\cap R$.
Intuitively, this is equivalent to finding a non-zero element (corresponds to
a neighbor vertex) in the vector defined over the subset $R$ for a given
subset $L$.

Simulating an OR query using BIS query for finding a neighbor. Let
$x_{R}\in\\{0,1\\}^{R}$ denote a vector such that $i$th element of the vector
corresponds to the the $i$the vertex $v_{i}$ in $R$ (according to some fixed
ordering of vertices). If $v_{i}\in\Gamma(L)\cap R$ for some
$i\in\\{1,2,\cdots,|R|\\}$, then, $x_{R}[i]=1$, otherwise it is $0$. Let
$\mathcal{Q}$ denotes the set of OR queries used to recover a uniform element
from $x_{R}$ using the algorithm from Lemma 30. Each of the OR queries $q\in
Q$ is defined over a subset $R_{q}\subseteq\\{v_{1},v_{2},\cdots v_{|R|}\\}$
and can be replaced with a corresponding BIS query $\mathcal{BIS}(L,R_{q})$
with the same output. Therefore, we can restate Lemma 30 in terms of BIS
queries as follows:

######  Lemma 31.

Suppose $L,R\subseteq V$ are disjoint subsets. There is a non-adaptive
randomized algorithm that recovers a uniform neighbor $u\in\Gamma(L)\cap R$
with probability $1-\delta$ and uses $O(\log^{2}|R|\log(1/\delta))$ BIS
queries.

###  5.2 Identifying uniform neighbour for each vertex

In this section, given a subset $S\subseteq V$, we describe an algorithm that
returns a uniform neighbor for every vertex in $S$ based on the ideas from
Section 5.1.

Overview of Algorithm Uniform-Neighbor. Our algorithm extends Estimate-Degree
by also returning a uniform neighbor for every vertex in $S$, along with the
degree estimates. Consider a vertex $v$ contained in the partition $S^{ta}$.
Along with the estimating the neighborhood size of the partition containing a
vertex $v$, we also return a uniform neighbor from the set $\Gamma(S^{ta})\cap
V\setminus S^{ta}$ using Lemma 31 from Section 5.1. So, we will have a set of
$T=O(\log n)$ neighbors for every vertex. By selecting the neighbor
corresponding to the partition $S^{t_{\textup{min}}(v)a}$ containing $v$, we
ensure that the neighbor is a uniform neighbor of $v$ with high success
probability. Here, the partition $S^{t_{\textup{min}}(v)a}$ where
$t_{\textup{min}}(v)\in[T]$, corresponds to the random partition with the
minimum neighborhood estimate size and is used for degree estimate of $v$,
i.e., $\widehat{d}(v)$.

Algorithm 5 Uniform-Neighbor: Uniform neighbor for each vertex in a given
subset $S$

1:Input: Subset $S\subseteq V$.

2:Output: Degree estimates and a uniform neighbour for each vertex $v\in S$.

3:Initialize $\hat{d}(v)\leftarrow n$ for every $v\in S$.

4:for $t$ in $\\{1,2,\ldots,T=O(\log n)\\}$ do

5: Consider a random partitioning of $S$ into $S^{t1},S^{t2},\ldots
S^{t\lambda}$ where $\lambda=O(\epsilon^{-4}\log^{2}n)$.

6: for every partition $S^{ta}$ where $a\in[\lambda]$ do

7: Let $z^{ta}$ is sample returned using Lemma 31 where $L=S^{ta},R=V\setminus
S^{ta}$ and $\delta=O(\epsilon/\log n^{4})$.

8: ${\eta}_{\text{est}}(S^{ta})\leftarrow\textsc{Neighborhood-
Size}(S^{ta},V\setminus S^{ta})$.

9: for $v\in S^{ta}$ do

10: if $\hat{d}(v)>{\eta}_{\text{est}}(S^{ta})$ then

11: $\hat{d}(v)\leftarrow{\eta}_{\text{est}}(S^{ta})$.

12: $t_{\textup{min}}(v)\leftarrow t$.

13: end if

14: end for

15: end for

16:end for

17: $\mathcal{U}_{j}(v)=z^{t_{\textup{min}}(v)a}$ for every $v\in S$.

18: return $\hat{d}(v),\mathcal{U}_{j}(v)$ for every $v\in S$.

We extend Lemma 31 and obtain the following corollary:

######  Corollary 32.

If $v\in S^{ta}$ for some $t\in[T],a\in[\lambda]$, then, for every neighbor
$w\in\Gamma(v)\cap V\setminus S^{ta}$, we have:

$\Pr[w=z^{ta}]=\frac{1}{|\Gamma(S^{ta})\cap V\setminus{S}^{ta}_{j}|}$

###### Proof.

From Lemma 31, we know that any vertex $w\in\Gamma(S^{ta})\cap V\setminus
S^{ta}$ will satisfy :

$\Pr[w=z^{ta}]=\frac{1}{|\Gamma(S^{ta})\cap V\setminus{S}^{ta}_{j}|}.$

As $\Gamma(v)\cap V\setminus S^{ta}\subseteq\Gamma(S^{ta})\cap V\setminus
S^{ta}$, we have the corollary. ∎

######  Lemma 33.

Suppose $S\subseteq V$. Then, Algorithm 5 uses
$O(\epsilon^{-4}\log^{5}n\log(\epsilon^{-1}\log n))$ BIS queries and with
probability $1-O(\epsilon/\log n)$, returns degree estimates $\hat{d}(v)$ for
every vertex $v\in S$ satisfying:

$d(v)(1-\epsilon)\leq\hat{d}(v)\leq d(v)+\frac{\epsilon^{4}}{\log^{2}n}\cdot
d(S).$

###### Proof.

For every random partition, we use Lemma 31 to return a uniform neighbor. This
step uses $O(\log^{2}n\log(1/\delta))$ BIS queries and succeeds with
probability at least $1-\delta$, where $\delta=O(\epsilon/T\lambda\log n)$,
$T=O(\log n)$, and $\lambda=O(\epsilon^{-4}\log^{2}n)$. The total number of
random partitions considered is $O(T\cdot\lambda)=O(\epsilon^{-4}\log^{3}n)$.
Following the proof of Lemma 10, we get the lemma. ∎

###  5.3 Identifying a uniform edge in the graph

In this section, we give an algorithm that returns an edge sample from a
distribution that is close to the uniform distribution. Our algorithm extends
Algorithm Edge-Estimator and is based on the following idea. Suppose we know
the degrees of all the vertices, denoted by $d(v)\ \forall v\in V$, in the
graph. In order to sample a uniform edge, we can sample a vertex $v$ with
probability $d(v)/\sum_{w\in V}d(w)$ and return a uniform neighbor among the
neighbors of $v$. We can observe that the probability that an edge $e=(v,u)$
is sampled is $d(v)/\sum_{w\in V}d(w)\cdot 1/d(v)+d(u)/\sum_{w\in V}d(w)\cdot
1/d(u)=1/m$.

Algorithm 6 Sampling: Non-adaptive algorithm for sampling uniform edges

1:Input: $V$ set of $n$ vertices and $\epsilon>0$ error parameter.

2:Output: Edge of the graph sampled from a (near)-uniform distribution.

3:Scale $\epsilon\leftarrow\frac{\epsilon}{600\log_{1/\epsilon}\log n}$ and
initialize $\gamma\leftarrow{1}/{(1-\epsilon)}$ and
$B\leftarrow{2}/{\epsilon}$.

4:Let $s$ be an integer selected uniformly at random from the interval
$[0,B)$.

5:Let $\mu(j)\leftarrow-s+j\cdot B$ for every integer $j$ in the interval
$\left[0,\frac{1}{B}\cdot\log_{\gamma}n\right].$

6:Initialize $S_{0}\leftarrow V$ and construct $S_{1}$ by sampling vertices in
$S_{0}$ with probability $1/\gamma^{\mu(1)}$.

7:Construct $S_{1}\supseteq S_{2}...\supseteq S_{L}$ for
$L=\frac{1}{B}\cdot\log_{\gamma}n$ where each $S_{j}$ is obtained by sampling
vertices in $S_{j-1}\ \forall j\geq 2$, independently with probability
$1/\gamma^{B}$.

8:for $j=0,1,\ldots L$ do

9: Run Uniform-Neighbor (Algorithm 5) on $S_{j}$, to obtain the degree
estimates $\widehat{d}_{j}(v)$ satisfying
$(1-\epsilon)d(v)\leq\widehat{d}_{j}(v)\leq d(v)+\frac{c_{1}\epsilon^{3}\cdot
m}{\log n\cdot\gamma^{\mu(j)}}$ for all $v\in S_{j}$.

10: Let $\mathcal{U}(v)$ denote the neighbor returned by Algorithm 5 for
vertex $v\in S_{j}$.

11:end for

12:Let $\bar{m}_{0}$ be the $O(\log n)$-approximate estimate from the
Algorithm CoarseEstimator in Beame et al. [BHPR+18] on a random partition of
$V$.

13:Set $\bar{m}_{0}\leftarrow\max\\{2,16\log n\cdot\bar{m}_{0}\\}$, so that we
have $m\leq\bar{m}_{0}\leq(64\log^{2}n)\cdot m.$

14:for $t=1,2,\cdots,T=2\log_{1/\epsilon}\log n$ do

15: $\bar{m}_{t}$ is assigned the output of Refine-Estimate that takes as
input approximate degree values $\widehat{d}_{j}(v)\ \forall v\in S_{j}\
\forall j\in[L]$, the previous estimate $\bar{m}_{t-1}$ and the iteration $t$.

16:end for

17: For every $v$ recovered, let $\widehat{\ell}(v)$ denote the level at which
$v$ was recovered by $T$th iteration of Refine-Estimate. Include all the
recovered vertices in $\mathcal{R}.$

18: Let $v_{\textup{sampled}}$ be the vertex drawn from the distribution such
that a vertex $v$ in $\mathcal{R}$ is selected with probability proportional
to $\gamma^{\mu(\widehat{\ell}(v))}\cdot\widehat{d}_{\widehat{\ell}(v)}(v)$.

19: return edge $(v_{\textup{sampled}},\mathcal{U}(v_{\textup{sampled}}))$.

In order to extend the above idea to our setting, there are two challenges.
First, we do not know the degrees (or approximate degrees) of all the
vertices. This is because the set of recovered vertices, i.e., with
$(1\pm\epsilon)$-approximate degree estimates known is a subset of the sampled
vertices at each level of sampling. Secondly, each vertex is recovered at a
different level and is therefore sampled with different probabilities. In
order to return a uniform edge based on the previously discussed idea, we must
return a single vertex among the set of recovered vertices with probability
proportional to its degree.

We address these two challenges by, amongst the recovered vertices, returning
vertex $v$ with probability proportional to
$\gamma^{\widehat{\ell}(v)}\cdot\widehat{d}(v)$ where $\widehat{\ell}(v)$ is
the level at which it is recovered, and $\widehat{d}_{\ell(v)}(v)$ is the
degree estimate at the level of recovery. From Section 4.3, we know that our
estimator $\sum_{v\textup{ is recovered}}\widehat{X}(v)=\sum_{v\textup{ is
recovered}}\gamma^{\widehat{\ell}(v)}\cdot\widehat{d}(v)$ is concentrated
around $2m$ (See Lemma 27) and we will be able to return a _near_ -uniform
sample.

Overview of Algorithm Sampling. Our algorithm is an extension of Algorithm
Edge-Estimator (Algorithm 3) and the differences are highlighted in blue.
During the process of constructing the edge estimator, by repeated
refinements, let $\widehat{\ell}(v)$ denote the level at which a vertex $v$ is
recovered at the last, i.e., $T=O(\log_{1/\epsilon}\log n)^{th}$ refinement
iteration, and the corresponding degree estimate
$\widehat{d}_{\widehat{\ell}(v)}(v)$. Let $\mathcal{R}$ denote the set of all
recovered vertices, i.e., $\widehat{X}(v)\neq 0$, in the last refinement
iteration. Then, we draw a vertex $v$ from the distribution such that it is
selected with probability proportional to
$\gamma^{\mu(\widehat{\ell}(v))}\cdot\widehat{d}_{\widehat{\ell}(v)}(v)$. From
our earlier discussion, this approach will result in a _near_ -uniform sample.

####  5.3.1 Proof of Theorem 2

######  Claim 34.

With probability $1-2\epsilon$, for all levels $j\in\\{1,2,\cdots,L\\}$, we
have:

$d(S_{j})\leq\frac{m\cdot L}{\epsilon\gamma^{\mu(j)}}.$

###### Proof.

As every vertex is included in $S_{j}$ with probability $1/\gamma^{\mu(j)}$,
we get:

$\operatorname*{{\bf{E}}}[d(S_{j})]=\frac{\sum_{v\in
V}d(v)}{\gamma^{\mu(j)}}=\frac{2m}{\gamma^{\mu(j)}}$

Therefore, by Markov’s Inequality, $\Pr[d(S_{j})\geq{m\cdot
L}/{\epsilon\gamma^{\mu(j)}}]\leq 2\epsilon/L$. Taking a union bound over all
the levels, with probability at least $1-2\epsilon$,

$d(S_{j})\leq{m\cdot L}/\epsilon\gamma^{\mu(j)}\leq{m\cdot\log
n}/\epsilon\gamma^{\mu(j)}\textup{for every level }j\in[L].$

∎

By setting $\lambda=O(\epsilon^{-4}\log^{2}n)$, a multiplicative factor of
$1/\epsilon$ more than that in section 4, we ensure that the exact guarantees
hold with probability $1-\epsilon$. Combining Claim 34 and Lemma 33, for
sufficiently large $n$, we have:

######  Corollary 35.

The degree estimates returned by Algorithm 5 for each sampling level
$j\in[L]$, satisfy the following with probability at least $1-\epsilon$:

$(1-\epsilon)d(v)\leq\widehat{d}_{j}(v)\leq
d(v)+\frac{c_{1}\epsilon^{3}m}{\gamma^{\mu(j)}\log n}\ \quad\forall v\in
S_{j}.$

For the remaining portion of this section, we will condition on the event that
Corollary 35 is satisfied. In the proof of the main Theorem 38, we account for
the failure probability of this event.

In the next lemma, we show that if a vertex is recovered at level $j$ (recall
the threshold value for recovery from Section 4.3), the neighbor returned by
Algorithm 5, given by $\mathcal{U}_{j}(v)$ is equal to any neighbor of $v$
with probability $1/\widehat{d}(v)$. From Section 4.3, we know that
approximate degree of $v$ obtained from the set $S$, denoted by
$\widehat{d}_{j}(v)$, when $\ell(v)=j$ is a $(1\pm\epsilon)$-approximation of
$d(v)$, therefore, we have returned a neighbor of $v$ with probability
$(1\pm\epsilon)/d(v)$.

######  Lemma 36.

Suppose $v\in S_{j}$ satisfies the following:
$\widehat{d}(v)\geq\frac{m}{\gamma^{\mu(j)}}\cdot\frac{c_{2}\epsilon^{2}}{\log
n}$. Then, for every $w\in\Gamma(v)$, we have with probability $1-\epsilon$:

$(1-\epsilon)\frac{1}{\widehat{d}(v)}\leq\Pr[\mathcal{U}_{j}(v)=w]\leq(1+\epsilon)\frac{1}{\widehat{d}(v)}.$

###### Proof.

From Lemma 9, we know that:

$(1-\epsilon)|\Gamma(S^{t_{\textup{min}}(v)a})\cap
V\setminus{S}^{t_{\textup{min}}(v)a}|\leq{\eta}_{\text{est}}(S^{t_{\textup{min}}(v)a})\leq(1+\epsilon)|\Gamma(S^{t_{\textup{min}}(v)a})\cap
V\setminus{S}^{t_{\textup{min}}(v)a}|.$

Moreover, our degree estimates in Algorithm 5 are obtained by
$\widehat{d}(v)={\eta}_{\text{est}}(S^{t_{\textup{min}}(v)a})$.

Consider a vertex $w\in\Gamma(v)$. If $w\in\Gamma(v)\setminus
S^{t_{\textup{min}}(v)a}$, we have:

$\displaystyle\Pr\left[\mathcal{U}_{j}(v)=w\right]$
$\displaystyle=\frac{1}{|\Gamma(S^{t_{\textup{min}}(v)a})\cap V\setminus
S^{t_{\textup{min}}(v)a}|}$
$\displaystyle(1-\epsilon)\cdot\frac{1}{\widehat{d}(v)}\leq\Pr\left[\mathcal{U}_{j}(v)=w\right]$
$\displaystyle\leq(1+\epsilon)\cdot\frac{1}{\widehat{d}(v)}$

If $w\in\Gamma(v)\cap S^{t_{\textup{min}}(v)a}$, then, it is never returned.
In iteration $t_{\textup{min}}(v)\in[T]$, $w\in S$ is assigned to one of the
$\lambda$ random partitions, we observe that such an event happens with
probability:

$\Pr[w\in
S^{t_{\textup{min}}(v)a}\cap\Gamma(v)]=\frac{1}{\lambda}=\frac{\epsilon^{4}}{c\log^{2}n}\leq\epsilon,\mbox{
for some constant $c>1$.}$

It is possible that $\mathcal{U}_{j}(v)\not\in\Gamma(v)\cap(V\setminus
S^{t_{\textup{min}}(v)a})$, which is a failure event for us, as no neighbor of
$v$ will be returned. We will argue that probability for such an event
occurring is small.

From the analysis in Lemma 10 and Corollary 35, with probability at least
$1-1/n^{3}$ and for an appropriate choice of $c_{2}$, we have:

$\displaystyle d(S^{t_{\textup{min}}(v)a}\setminus\\{v\\})$
$\displaystyle\leq\frac{c_{1}m\cdot\epsilon^{3}}{\gamma^{\mu(j)}\log
n}\leq\epsilon\widehat{d}(v)\quad(\mbox{as we are given}\
\widehat{d}(v)\geq\frac{m}{\gamma^{\mu(j)}}\cdot\frac{c_{2}\epsilon^{2}}{\log
n}).$

$\displaystyle\Pr[\mathcal{U}_{j}(v)\not\in\Gamma(v)\cap(V\setminus
S^{t_{\textup{min}}(v)a})]$
$\displaystyle\leq\frac{|\Gamma(S^{t_{\textup{min}}(v)a}\setminus\\{v\\})\cap
V\setminus{S}^{t_{\textup{min}}(v)a}|}{|\Gamma(S^{t_{\textup{min}}(v)a})\cap
V\setminus{S}^{t_{\textup{min}}(v)a}|}$
$\displaystyle\leq\frac{d(S^{t_{\textup{min}}(v)a}\setminus\\{v\\})}{|\Gamma(S^{t_{\textup{min}}(v)a})\cap
V\setminus{S}^{t_{\textup{min}}(v)a}|}$
$\displaystyle\leq(1+\epsilon)\cdot\frac{d(S^{t_{\textup{min}}(v)a}\setminus\\{v\\})}{\widehat{d}(v)}\leq\epsilon(1+\epsilon)=2\epsilon.$

By union bound, failure probability is at most $1/n^{3}+\epsilon\leq
2\epsilon$. Scaling $\epsilon$ appropriately, gives us the lemma. ∎

In the next lemma, we show that if a vertex is not in $V_{\textup{boundary}}$,
then, it is recovered with the required probability of $\widehat{d}(v)/2m$
(upto $1\pm\epsilon$ factor). Otherwise, we argue that the probability of
returning it is not too large.

######  Lemma 37.

For any vertex $v$, with probability at least $1-\epsilon$, we have:

  1. 1.

$(1-\epsilon)\frac{\widehat{d}_{\widehat{\ell}(v)}(v)}{2m}\leq\Pr[v_{\textup{sampled}}=v]\leq(1+\epsilon)\frac{\widehat{d}_{\widehat{\ell}(v)}(v)}{2m}\textup{
if }v\not\in V_{\textup{boundary}}.$

  2. 2.

$\Pr[v_{\textup{sampled}}=v]\leq\frac{15(1+\epsilon)\widehat{d}_{\widehat{\ell}(v)}(v)}{2m}\textup{
if }v\in V_{\textup{boundary}}.$

###### Proof.

We condition on the event that the
$(1-\epsilon)2m\leq\sum_{v\in\mathcal{R}}\widehat{X}(v)\leq(1+\epsilon)2m$,
which happens with probability at least $1-\epsilon$ (follows from Corollary
35, Lemma 27, and Theorem 11).

From Claim 18, we know that a vertex not lying at the boundary will be
recovered at level $\ell(v)$, i.e., $\widehat{\ell}(v)=\ell(v)$. Consider a
vertex $v\in V\setminus V_{\textup{boundary}}$, we have:

$\Pr[v\in\mathcal{R}]=\Pr[v\in
S_{\widehat{\ell}(v)}]=\frac{1}{\gamma^{\mu(\widehat{\ell}(v))}}$

From construction, for any vertex $v\in\mathcal{R}$, we have that

$\Pr[v_{\textup{sampled}}=v\mid
v\in\mathcal{R}]=\frac{\gamma^{\mu(\widehat{\ell}(v))}\widehat{d}_{\widehat{\ell}(v)}(v)}{\sum_{w\in\mathcal{R}}\gamma^{\mu(\widehat{\ell}(v))}\widehat{d}_{\widehat{\ell}(w)}(w)}\leq(1+2\epsilon)\frac{\gamma^{\mu(\widehat{\ell}(v))}\widehat{d}_{\widehat{\ell}(v)}(v)}{2m}.$

Similarly, we get:

$\Pr[v_{\textup{sampled}}=v\mid
v\in\mathcal{R}]\geq(1-\epsilon)\frac{\gamma^{\mu(\widehat{\ell}(v))}\widehat{d}_{\widehat{\ell}(v)}(v)}{2m}.$

Combining both the above statements and scaling $\epsilon=\epsilon/2$, we get:

$(1-\epsilon)\frac{\widehat{d}_{\widehat{\ell}(v)}(v)}{2m}\leq\Pr[v_{\textup{sampled}}=v]\leq(1+\epsilon)\frac{\widehat{d}_{\widehat{\ell}(v)}(v)}{2m}.$

Now, consider a vertex $v\in V_{\textup{boundary}}$. From Claim 20, if
included in we know that
$\widehat{\ell}(v)\in\\{\ell(v)-1,\ell(v),\ell(v)+1\\}$, provided it is
included in their corresponding set $S_{\widehat{\ell}(v)}$.

$\displaystyle\Pr[v\in\mathcal{R}]\leq\sum_{\widehat{\ell}(v)\in\\{\ell(v)-1,\ell(v),\ell(v)+1\\}}\Pr[v\in
S_{\widehat{\ell}(v)}]$ $\displaystyle\leq\frac{3}{\gamma^{\mu(\ell(v)-1)}}$
$\displaystyle\Pr[v_{\textup{sampled}}=v]=\Pr[v_{\textup{sampled}}=v\mid
v\in\mathcal{R}]\cdot\Pr[v\in\mathcal{R}]$
$\displaystyle\leq\frac{3(1+2\epsilon)\gamma^{\mu(\widehat{\ell}(v))}}{\gamma^{\mu(\ell(v)-1)}}\cdot\frac{\widehat{d}_{\widehat{\ell}(v)}(v)}{2m}$
$\displaystyle\leq\frac{15(1+2\epsilon)\widehat{d}_{\widehat{\ell}(v)}(v)}{2m}$

Hence, the lemma. ∎

######  Theorem 38.

Given a graph $G$ with $n$ nodes, $m$ edges, and edge set $E$, there is an
algorithm that makes $O(\epsilon^{-4}\log^{6}n\log(\epsilon^{-1}\log
n)+\epsilon^{-6}\log^{5}n\log^{6}(\log n)\log(\epsilon^{-1}\log n))$ non-
adaptive BIS queries which, with probability at least $1-\epsilon$, outputs an
edge from a probability distribution $P$ satisfying $(1-\epsilon)/{m}\leq
P(e)\leq(1+\epsilon)/{m}$ for every $e\in E$.

###### Proof.

Consider an edge $e=(v,u)$. Then, the edge $e=(v,u)$ can be returned by
Algorithm 6 if either $v$ or $u$ is the vertex sampled $v_{\textup{sampled}}$
and the other vertex is the neighbor returned by Algorithm 5. From Lemmas 36
and 37, we have:

$\displaystyle\Pr[e\textup{ is returned by
Algorithm~{}\ref{alg:estimator_sample}}]$
$\displaystyle=\Pr[v_{\textup{sampled}}=v]\cdot\Pr[\mathcal{U}(v)=u]+\Pr[v_{\textup{sampled}}=u]\cdot\Pr[\mathcal{U}(u)=v]$
$\displaystyle\Rightarrow\Pr[v_{\textup{sampled}}=v]$
$\displaystyle=\Pr[v_{\textup{sampled}}=v\mid v\in V\setminus
V_{\textup{boundary}}]\Pr[v\in V\setminus V_{\textup{boundary}}]$
$\displaystyle+\Pr[v_{\textup{sampled}}=v\mid v\in
V_{\textup{boundary}}]\Pr[v\in V_{\textup{boundary}}]$
$\displaystyle\leq(1+\epsilon)^{2}\frac{\widehat{d}_{\widehat{\ell}(v)}(v)}{2m}+\epsilon\cdot\frac{15(1+2\epsilon)\widehat{d}_{\widehat{\ell}(v)}(v)}{2m}$
$\displaystyle\leq(1+O(\epsilon))\cdot\frac{\widehat{d}_{\widehat{\ell}(v)}(v)}{2m}$

Therefore, we have:

$\displaystyle\Pr[e\textup{ is returned by
Algorithm~{}\ref{alg:estimator_sample}}]$
$\displaystyle\leq(1+O(\epsilon))\cdot\frac{\widehat{d}_{\widehat{\ell}(v)}(v)}{2m}\cdot\frac{1}{\widehat{d}_{\widehat{\ell}(v)}(v)}+(1+O(\epsilon))\cdot\frac{\widehat{d}_{\widehat{\ell}(u)}(u)}{2m}\cdot\frac{1}{\widehat{d}_{\widehat{\ell}(u)}(u)}$
$\displaystyle\leq(1+O(\epsilon))\cdot\frac{1}{m}.$

The total number of additional (other than those used for edge estimation) BIS
queries used is $O(\log n\cdot Q)$ where $Q$ is the queries used by Algorithm
5 to return a (near) uniform sample. From Claim 33, we have that
$Q=O(\epsilon^{-4}\log^{5}n\log(\epsilon^{-1}\log n))$. In Algorithm 5, as we
partition each sampled subset $S_{j}$, for every $j\in L$, into an additional
$1/\epsilon$ factor many partitions as compared to Algorithm 2. Therefore, we
use a total of $O(\epsilon^{-4}\log^{6}n\log(\epsilon^{-1}\log
n)+\epsilon^{-6}\log^{5}n\log^{6}(\log n)\log(\epsilon^{-1}\log n))$ BIS
queries for edge estimation.

Using union bound, we have that the failure probability in Lemma 37 and
Corollary 35 is at most $O(\epsilon)$. Scaling the $\epsilon$ appropriately,
gives us a failure probability of $\epsilon$. Hence, the theorem. ∎

##  6 Graph Connectivity

In this section, we present Algorithm Connectivity-BIS that uses $2$-rounds of
adaptivity to determine the connectivity of an input graph $G$. This improves
upon on a prior three-round algorithm of [ACK21]. In particular, the algorithm
of [ACK21] selects $O(\log^{2}n)$ random neighbors per vertex, and contracts
the connected components of this random graph into _supernodes_. This random
sampling step can be performed using one round of $\widetilde{O}(n)$ BIS
queries. They prove that in the contracted graph on the supernodes, there are
at most $O(n\log n)$ edges. Using this fact, they then show how to identify
whether all the supernodes are connected using $\widetilde{O}(n)$ BIS queries
and two additional around of adaptivity.

We follow the same basic approach: using a first round of $\widetilde{O}(n)$
queries to randomly sample $O(\log^{2}n)$ neighbors per vertex and contract
the graph into supernodes. Once this is done, we observe that we have BIS
query access to the contracted graph simply by always grouping together the
set of nodes in each supernode. So, we can directly apply the non-adaptive
sampling algorithm of Theorem 2 to sample edges from the contracted graph. By
a coupon collecting argument, drawing $O(n\log^{2}n)$ near-uniform edge
samples (with replacement) from the contracted graph suffices to recover all
$O(n\log n)$ edges in the graph, and thus determine connectivity of the
contracted graph, and, in turn, the original graph.

Algorithm Connectivity-BIS:

  1. 1.

For every node $v\in V$, sample $O(\log^{2}n)$ edges uniformly with
replacement, from the neighborhood $\Gamma(v)$, using Lemma 31. Let the
resulting set of edges sampled be denoted by $E^{\prime}\subseteq E$ and the
connected components in the subgraph $G(V,E^{\prime})$ be $S_{1},S_{2},\cdots
S_{p}$.

  2. 2.

Let $G^{\text{sup}}(V^{\text{sup}},E^{\text{sup}})$ where
$E^{\text{sup}}\subseteq V^{\text{sup}}\times V^{\text{sup}}$ denotes the
supergraph obtained from $G(V,E^{\prime})$ by collapsing the connected
components $S_{1},S_{2},\cdots S_{p}$ into single supernodes
$s_{1},s_{2},\cdots s_{p}$ respectively, given by:

$V^{\text{sup}}=\\{s_{i}\mid S_{i}\text{ where }i\in[p]\text{ is a connected
component in }G(V,E^{\prime})\\}$ $E^{\text{sup}}=\\{(s_{i},s_{j})\mid\exists
x\in S_{i},y\in S_{j}\text{ where }i\neq j\text{ such that }(x,y)\in E\\}.$

  3. 3.

Run Algorithm 6 (with any constant value for $\epsilon$) on $G^{\text{sup}}$
to draw $T=O(n\log^{2}n)$ uniform superedge samples with replacement, from
$E^{\text{sup}}$ . If the resulting graph $G^{\text{sup}}$ is connected,
output ‘Yes’. Otherwise, output ‘No’.

######  Theorem 39.

Given a graph $G$ with $n$ nodes, there is a $2$-round adaptive algorithm that
determines if $G$ is connected with probability at least $1-1/n$ using
$\tilde{O}(n\log^{8}n)$ BIS queries, where $\tilde{O}(\cdot)$ ignores the
$\log^{O(1)}\log n$ dependencies.

###### Proof.

We have: $|E^{\text{sup}}|=O(n\log n)$ (see Lemma 6.5 in [ACK21]). From
Theorem 38, we have:

$\displaystyle\Pr[(s_{i},s_{j})\in E^{\text{sup}}\mbox{ is returned}]$
$\displaystyle\geq(1-\epsilon)\cdot\frac{(1-\epsilon)}{|E^{\text{sup}}|}\geq(1-2\epsilon)\cdot
c\cdot\frac{1}{n\log n}\mbox{ for constant $\epsilon<0.5$}$
$\displaystyle\Rightarrow\Pr[(s_{i},s_{j})\mbox{ is not returned}]$
$\displaystyle=\left(1-\Pr[(s_{i},s_{j})\in E^{\text{sup}}\mbox{ is
returned}]\right)^{T}$ $\displaystyle\leq e^{-\frac{2c}{3}\cdot\frac{1}{n\log
n}\cdot T}\leq\frac{1}{n^{4}}.$

By union bounding over at most $O(n\log n)$ many superedges, the total failure
probability is at most $1/n^{2}$. Similarly, union bounding over the failure
probability of recovering $O(n\log^{2}n)$ edges in the first step, we have
that the failure probability is at most $1/n^{2}$. Therefore, Algorithm
Connectivity-BIS recovers all the edges in $E^{\text{sup}}$ with probability
at least $1-1/n$.

From Lemma 31, the total number of BIS queries required in the first round of
our algorithm is $O(n\cdot\log^{2}n\cdot\log^{3}n)=O(n\log^{5}n)$. Setting
$\epsilon$ to be any constant value, from Theorem 38, the total number of BIS
queries required is
$O(n\log^{5}n)+\tilde{O}(n\log^{2}n\cdot\log^{6}n)=\tilde{O}(n\log^{8}n)$,
where $\tilde{O}(\cdot)$ ignores the $\log\log n$ dependencies. Hence, the
theorem. ∎

##  7 Conclusion and Open Questions

In this paper, we presented non-adaptive algorithms for edge estimation and
sampling using BIS queries. It would be interesting to see if there is a
better dependence on $\epsilon$ than that obtained by our algorithms, when we
consider non-adaptive algorithms for edge estimation. Using Independent Set
(IS) queries, adaptive algorithms for edge estimation with optimal query
complexity $O(\min\\{\sqrt{m},n/\sqrt{m}\\}\cdot\textup{poly}(\log
n,1/\epsilon))$ were obtained only recently [CLW20, BHPR+18]. It would be
interesting to see if we can extend our techniques to study _non-adaptive_
algorithms for edge estimation using IS queries or in the standard adjacency
list model. We believe that adaptivity plays a role similar to that of number
of passes for streaming algorithms, and optimizing for the rounds of
adaptivity could be a good future direction, even for problems that might
already have query optimal adaptive sub-linear time algorithms.

## Acknowledgements

Part of this work was done while R. Addanki was a visiting student at the
Simons Institute for the Theory of Computing. This work was supported by a
Dissertation Writing Fellowship awarded by the Manning College of Information
and Computer Sciences, University of Massachusetts Amherst to R. Addanki. In
addition, this work was supported by NSF grants CCF-1934846, CCF-1908849, and
CCF-1637536, awarded to A. McGregor; and NSF grants CCF-2046235, IIS-1763618,
as well as Adobe and Google Research Grants, awarded to C. Musco. We thank the
anonymous reviewers of the European Symposium on Algorithms (ESA) 2022, for
their helpful suggestions.

## References

  * [AAAK17] Arpit Agarwal, Shivani Agarwal, Sepehr Assadi, and Sanjeev Khanna.  Learning with limited rounds of adaptivity: Coin tossing, multi-armed bandits, and ranking from pairwise comparisons.  In Proceedings of the 30 Annual Conference on Computational Learning Theory (COLT), pages 39–75, 2017.
  * [ABG+18] Maryam Aliakbarpour, Amartya Shankha Biswas, Themis Gouleakis, John Peebles, Ronitt Rubinfeld, and Anak Yodpinyanee.  Sublinear-time algorithms for counting star subgraphs via edge sampling.  Algorithmica, 80(2):668–697, 2018.
  * [AC08] Dana Angluin and Jiang Chen.  Learning a hidden graph using $o(\log n)$ queries per edge.  Journal of Computer and System Sciences, 74(4):546–556, 2008.
  * [ACK21] Sepehr Assadi, Deeparnab Chakrabarty, and Sanjeev Khanna.  Graph connectivity and single element recovery via linear and OR queries.  In 29th Annual European Symposium on Algorithms, (ESA), pages 7:1–7:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
  * [AGM12] Kook Jin Ahn, Sudipto Guha, and Andrew McGregor.  Analyzing graph structure via linear measurements.  In Proceedings of the 23 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 459–467, 2012.
  * [AHP08] Boris Aronov and Sariel Har-Peled.  On approximating the depth and related problems.  SIAM Journal on Computing, 38(3):899–921, 2008.
  * [AN19] Hasan Abasi and Bshouty Nader.  On learning graphs with edge-detecting queries.  In Algorithmic Learning Theory (ALT), pages 3–30, 2019.
  * [BBGM19] Anup Bhattacharya, Arijit Bishnu, Arijit Ghosh, and Gopinath Mishra.  Hyperedge estimation using polylogarithmic subset queries.  arXiv:1908.04196, 2019.
  * [BBGM21] Anup Bhattacharya, Arijit Bishnu, Arijit Ghosh, and Gopinath Mishra.  On triangle estimation using tripartite independent set queries.  Theory of Computing Systems, pages 1–28, 2021.
  * [BBGM22] Anup Bhattacharya, Arijit Bishnu, Arijit Ghosh, and Gopinath Mishra.  Faster counting and sampling algorithms using colorful decision oracle.  In Proceedings of the 39 International Symposium on Theoretical Aspects of Computer Science (STACS), 2022.
  * [Beh22] Soheil Behnezhad.  Time-optimal sublinear algorithms for matching and vertex cover.  In Proceedings of the 63 Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 873–884, 2022.
  * [BER21] Amartya Shankha Biswas, Talya Eden, and Ronitt Rubinfeld.  Towards a decomposition-optimal algorithm for counting and sampling arbitrary motifs in sublinear time.  In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM), 2021.
  * [BGK+18] Arijit Bishnu, Arijit Ghosh, Sudeshna Kolay, Gopinath Mishra, and Saket Saurabh.  Parameterized query complexity of hitting set using stability of sunflowers.  In 29th International Symposium on Algorithms and Computation, 2018\.
  * [BGMP19] Arijit Bishnu, Arijit Ghosh, Gopinath Mishra, and Manaswi Paraashar.  Efficiently sampling and estimating from substructures using linear algebraic queries.  arXiv:1906.07398, 2019.
  * [BHPR+18] Paul Beame, Sariel Har-Peled, Sivaramakrishnan Natarajan Ramamoorthy, Cyrus Rashtchian, and Makrand Sinha.  Edge estimation with independent set oracles.  Proceedings of the 9 Conference on Innovations in Theoretical Computer Science (ITCS), 2018.
  * [BS18] Eric Balkanski and Yaron Singer.  The adaptive complexity of maximizing a submodular function.  In Proceedings of the 50 Annual ACM Symposium on Theory of Computing (STOC), pages 1138–1151, 2018.
  * [CG18] Clément L Canonne and Tom Gur.  An adaptivity hierarchy theorem for property testing.  Computational Complexity, 27(4):671–716, 2018.
  * [CJ15] Sergio Cabello and Miha Jejčič.  Shortest paths in intersection graphs of unit disks.  Computational Geometry, 48(4):360–367, 2015.
  * [CLW20] Xi Chen, Amit Levi, and Erik Waingarten.  Nearly optimal edge estimation with independent set queries.  In Proceedings of the 31 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2916–2935, 2020.
  * [CM05] Graham Cormode and Shan Muthukrishnan.  An improved data stream summary: the count-min sketch and its applications.  Journal of Algorithms, 55(1):58–75, 2005.
  * [CQ19] Chandra Chekuri and Kent Quanrud.  Parallelizing greedy for submodular set function maximization in matroids and beyond.  In Proceedings of the 51 Annual ACM Symposium on Theory of Computing (STOC), pages 78–89, 2019.
  * [CS90] Chao L Chen and William H Swallow.  Using group testing to estimate a proportion, and to test the binomial model.  Biometrics, pages 1035–1046, 1990.
  * [CS21] Amit Chakrabarti and Manuel Stoeckl.  The element extraction problem and the cost of determinism and limited adaptivity in linear queries.  arXiv:2107.05810, 2021.
  * [DHH00] Dingzhu Du, Frank K Hwang, and Frank Hwang.  Combinatorial group testing and its applications, volume 12.  World Scientific, 2000.
  * [DL21] Holger Dell and John Lapinskas.  Fine-grained reductions from approximate counting to decision.  ACM Transactions on Computation Theory (TOCT), 13(2):1–24, 2021\.
  * [DLM20] Holger Dell, John Lapinskas, and Kitty Meeks.  Approximately counting and sampling small witnesses using a colourful decision oracle.  In Proceedings of the 31 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2201–2211, 2020.
  * [Dor43] Robert Dorfman.  The detection of defective members of large populations.  The Annals of Mathematical Statistics, 14(4):436–440, 1943.
  * [ER18] Talya Eden and Will Rosenbaum.  On sampling edges almost uniformly.  In 1st Symposium on Simplicity in Algorithms (SOSA), 2018.
  * [ERS20] Talya Eden, Dana Ron, and C Seshadhri.  On approximating the number of k-cliques in sublinear time.  SIAM Journal on Computing, 49(4):747–771, 2020.
  * [Fei06] Uriel Feige.  On sums of independent random variables with unbounded variance and estimating the average degree in a graph.  SIAM Journal on Computing, 35(4):964–984, 2006.
  * [Fis03] Aleksei V Fishkin.  Disk graphs: A short survey.  In International Workshop on Approximation and Online Algorithms, pages 260–264. Springer, 2003.
  * [GR08] Oded Goldreich and Dana Ron.  Approximating average parameters of graphs.  Random Structures & Algorithms, 32(4):473–493, 2008.
  * [INR10] Piotr Indyk, Hung Q Ngo, and Atri Rudra.  Efficiently decodable non-adaptive group testing.  In Proceedings of the 21 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1126–1142, 2010.
  * [IPW11] Piotr Indyk, Eric Price, and David P Woodruff.  On the power of adaptivity in sparse recovery.  In Proceedings of the 52 Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 285–294, 2011.
  * [KK20] Lidiya Khalidah binti Khalil and Christian Konrad.  Constructing large matchings via query access to a maximal matching oracle.  In 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 2020.
  * [KP19] Akshay Kamath and Eric Price.  Adaptive sparse recovery with limited adaptivity.  In Proceedings of the 30 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2729–2744, 2019.
  * [KSV10] Howard Karloff, Siddharth Suri, and Sergei Vassilvitskii.  A model of computation for mapreduce.  In Proceedings of the 21 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 938–948, 2010.
  * [McG14] Andrew McGregor.  Graph stream algorithms: a survey.  ACM SIGMOD Record, 43(1):9–20, 2014.
  * [MS22] Ashley Montanaro and Changpeng Shao.  Quantum algorithms for learning a hidden graph.  In 17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2022.
  * [Nis21] Noam Nisan.  The demand query model for bipartite matching.  In Proceedings of the 32 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 592–599, 2021.
  * [NSWZ18] Vasileios Nakos, Xiaofei Shi, David P Woodruff, and Hongyang Zhang.  Improved algorithms for adaptive compressed sensing.  In Proceedings of the 45 International Colloquium on Automata, Languages and Programming (ICALP), 2018.
  * [ORRR12] Krzysztof Onak, Dana Ron, Michal Rosen, and Ronitt Rubinfeld.  A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size.  In Proceedings of the 23 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1123–1131, 2012.
  * [Ron19] Dana Ron.  Sublinear-time algorithms for approximating graph parameters.  In Computing and Software Science, pages 105–122. Springer, 2019\.
  * [RSW18] Aviad Rubinstein, Tselil Schramm, and S. Matthew Weinberg.  Computing Exact Minimum Cuts Without Knowing the Graph.  In Proceedings of the 9 Conference on Innovations in Theoretical Computer Science (ITCS), 2018.
  * [RT16] Dana Ron and Gilad Tsur.  The power of an example: Hidden set size approximation using group queries and conditional sampling.  ACM Transactions on Computation Theory (TOCT), 8(4):1–19, 2016\.
  * [RWZ20] Cyrus Rashtchian, David P Woodruff, and Hanlin Zhu.  Vector-matrix-vector queries for solving linear algebra, statistics, and graph problems.  In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM), 2020.
  * [Ses] C Seshadhri.  A simpler sublinear algorithm for approximating the triangle count.  arXiv:1505.01927.
  * [Sto83] Larry Stockmeyer.  The complexity of approximate counting.  In Proceedings of the 15 Annual ACM Symposium on Theory of Computing (STOC), pages 118–126, 1983.
  * [Sto85] Larry Stockmeyer.  On approximation algorithms for # p.  SIAM Journal on Computing, 14(4):849–861, 1985.
  * [TT22] Jakub Tětek and Mikkel Thorup.  Edge sampling and graph parameter estimation via vertex neighborhood accesses.  In Proceedings of the 54 Annual ACM Symposium on Theory of Computing (STOC), pages 1116–1129, 2022.