Edge Estimation with Independent Set Oracles
Sariel Har-Peled†

Paul Beame∗
beame@cs.washington.edu

sariel@illinois.edu

Sivaramakrishnan Natarajan Ramamoorthy

∗§

∗‡

Cyrus Rashtchian

cyrash@cs.washington.edu

arXiv:1711.07567v2 [] 22 Nov 2017

sivanr@cs.washington.edu
∗‡

Makrand Sinha

makrand@cs.washington.edu
Abstract
We study the problem of estimating the number of edges in a graph with access to only an
independent set oracle. Independent set queries draw motivation from group testing and have
applications to the complexity of decision versus counting problems. We give two algorithms
to estimate the number of edges in an n-vertex graph: one that uses only polylog(n) bipartite
independent set queries, and another one that uses n2/3 · polylog(n) independent set queries.

1

Introduction

We study the problem of estimating the number of edges in a simple, unweighted, undirected
graph G = ([n], E), where [n] := {1, 2, . . . , n} and m = |E|, using only an oracle that answers
independent set queries. For a parameter ε > 0, we wish to output an estimate m
e satisfying
(1 − ε)m ≤ m
e ≤ (1 + ε)m with high probability. We consider randomized algorithms with access
to one of the two following independent set oracles:
Bipartite independent set (BIS) oracle: Given disjoint subsets A, B ⊆ [n], a BIS query answers
whether A, B satisfy e(A, B) = 0, where e(A, B) denotes the number of edges with one
endpoint in A and the other in B.
Independent set (IS) oracle: Given a subset A ⊆ [n], an IS query answers whether A satisfies
e(A) = 0, where e(A) denotes the number of edges with both endpoints in A.
Previous work on graph parameter estimation has primarily focused on local queries, such as
degree queries (which output the degree of a vertex v), edge existence queries (which answer whether
a pair (u, v) forms an edge), or neighbor queries (which provide the ith neighbor of a vertex v).
However, such queries cannot achieve sub-polynomial query costs on certain lower bound graphs
identified by Feige [Fei06] and Goldreich and Ron [GR08], essentially due to the fact that these
queries can only obtain local information about the graph. This motivates an investigation of other
types of queries that may enable very efficient parameter estimation. The independent set queries
described above naturally generalize an edge existence query, and their non-locality opens the door
for sub-polynomial query algorithms for various graph parameter estimation tasks.
∗
Paul G. Allen School of Computer Science & Engineering, University of Washington, Seattle. Research supported
in part by NSF grants CCF-1524246.
†
Department of Computer Science, University of Illinois, Urbana-Champaign. Supported in part by NSF AF
awards CCF-1421231 and CCF-1217462. Work done while visiting University of Washington on Sabbatical in 2017.
‡
Supported by the NSF under agreements CCF-1149637, CCF-1420268 and CCF-1524251.
§
Work partially completed while the author was at Microsoft Research.

1

1.1

Motivation and Related Work

The most relevant previous work comes from the area of sub-linear time algorithms for graph
parameter estimation. BIS and IS queries also have interesting connections to the classical area
of group testing, to emptiness versus counting questions in computational geometry, and to the
complexity of decision versus counting problems.
Graph Parameter Estimation. Many researchers have studied the problem of estimating various parameters of graphs using many types of queries. Feige [Fei06] estimated the number of edges
in a graph using degree queries, where a degree query returns the degree deg(v) of a specified
vertex v in G([n], E). In a follow-up work, Goldreich and Ron [GR08] estimated the number of
edges in a graph using both degree and neighbor queries, where a neighbor query returns the j th
neighbor of a vertex v for j, v ∈ [n]. Related work has also appeared on estimating the number of
stars [GRS11], the minimum vertex cover [ORRR11], the number of triangles [ELRS15, Ses15], and
the number of k-cliques [ERS17]. A special case of BIS query termed a group query (where one
of the bipartition sets is a singleton) was considered for testing k-colorability of graphs [BKKR13]
and edge estimation [WLY13].
The results of Feige [Fei06] and Goldreich and Ron [GR08] on estimating the number of edges
√
in a graph are quite relevant to our work. Feige [Fei06] showed how to use O ( n/ε) degree queries
to output an estimate m
e that satisfies (2 − ε)m ≤ m
e ≤ (2 + ε)m. Moreover, he showed that any
algorithm achieving better than a 2-approximation must use a nearly linear number of queries in the
worst case. Goldreich and Ron [GR08] showed that by using both degree and neighbor queries, the
√
approximation could be improved to (1−ε)m ≤ m
e ≤ (1+ε)m by using n·poly(log n, 1/ε) queries.
Finally, we mention that Feige [Fei06] and Goldreich and Ron [GR08] have identified certain hard
instances showing that these upper bounds cannot be improved, up to polylog(n) factors.
Group Testing. A classic estimation problem involves efficiently approximating the number of
defective items or infected individuals in a certain collection or population [CS90, Dor43, Swa85].
To query a population, a small group is formed, and all the individuals in the group are tested in
one shot. For example, in genome-wide association studies, combined pools of DNA may be tested
as a group for certain variants [KZC+ 05]. In group testing, the result of a test often indicates only
whether there is at least one infected or defective unit, or if there is none. Such a dichotomous
outcome resembles the independent set queries that we study. Group testing in the graph setting
suggests the interpretation that we wish to test pairwise interactions between items or individuals,
instead of singular events.
Computational Geometry. Certain geometric applications exhibit the phenomena that emptiness queries have more efficient algorithms than counting queries. For example, in three dimensions,
for a set P of n points, half-space counting queries (i.e., what is the size of the set |P ∩ h|, for a
query half-space h), can be answered in O(n2/3 ) time, after near-linear time preprocessing. On the
other hand, emptiness queries (i.e., is the set P ∩ h empty?) can be answered in O(log n) time.
Aronov and Har-Peled [AH08] used this to show how to answer approximate counting queries (i.e.,
estimating |P ∩ h|), with polylogarithmic emptiness queries.
As another geometric example, consider the task of counting edges in disk intersection graphs
using GPUs [Fis03]. For these graphs, IS queries decide if a subset of the disks have any intersection
(this can be done using sweeping in O(n log n) time [CJ15]). Using a GPU, one could quickly draw
the disks and check if the sets share a common pixel. In cases like this – when IS and BIS oracles
have fast implementations – algorithms exploiting independent set queries may be useful.
2

Decision versus Counting Complexity. A generalization of IS and BIS queries has previously
appeared in a line of work investigating the relationship between decision and counting problems
[Sto83, Sto85, DL17]. Stockmeyer [Sto83, Sto85] showed how to estimate the number of satisfying
assignments for a given circuit with queries to an NP oracle. Ron and Tsur [RT14] observed that
Stockmeyer implicitly provided an algorithm for estimating set cardinality using subset queries,
where a subset query specifies a subset X ⊆ U and answers whether |X ∩ S| = 0 or not. Subset
queries generalize IS and BIS queries because S corresponds to the set of edges in the graph with
|S| and X is an arbitrary subset of pairs of vertices.
In what follows, we
 consider subset queries in the context of estimating edges in a graph and fix
n
|S| = m and |U| = 2 . Stockmeyer provided an algorithm using only O(log log m·poly(1/ε)) subset
queries to estimate m within a factor of (1 + ε) with a constant success probability. Note that for a
high probability bound, which is what we focus on in this paper, the algorithm would naively require
O(log n · log log m · poly(1/ε)) queries to achieve success probability at least 1 − 1/n. Falahatgar,
Jafarpour, Orlitsky, Pichapati, and Suresh [FJO+ 16] gave an improved algorithm that
 estimates m
2
up to a factor of (1 + ε) with probability 1 − δ using 2 log log m + O (1/ε ) log(1/δ) subset queries.
Nearly matching lower bounds are also known for subset queries [Sto83, Sto85, RT14, FJO+ 16].
Ron and Tsur [RT14] also study a restriction of subset queries, called interval queries, where they
assume that the universe U is ordered and the subsets must be intervals of elements. We view the
independent set queries that we study as another natural restriction of subset queries.
Analogous to Stockmeyer’s results, a recent work of Dell and Lapinskas [DL17] provides a
framework that relates edge estimation using BIS and edge existence queries to a question in finegrained complexity. They study the relationship between decision and counting versions of problems
such as 3SUM and Orthogonal Vectors. We first describe their edge estimation result and then
explain their connection to fine-grained complexity. They prove the following for bipartite graphs.
Theorem 1.1 ([DL17]). For every 0 ≤ ε ≤ 1 , there exists an algorithm using
and

n·polylog(n)
ε4

O(log6 n)
ε2

BIS queries

edge existence queries, and outputs m
e such that with probability at least 1 − 1/n2
(1 − ε)m ≤ m
e ≤ (1 + ε)m.

Dell and Lapinskas [DL17] used their edge estimation algorithm to obtain approximate counting
algorithms for problems in fine-grained complexity. For instance, given an algorithm for 3SUM with
runtime T , they obtain an algorithm that estimates the number of YES instances of 3SUM with
6
n)
runtime T · O(log
+ n·polylog(n)
. The relationship is quite simple and natural. The decision
ε2
ε4
version of 3SUM corresponds to checking if there is at least one edge in a certain bipartite graph.
The counting version then corresponds to counting the edges in this graph. We note that in
their application, the large number O(n · polylog(n)) of edge existence queries does not affect the
dominating term in the overall time in their reduction; the larger term in the time is a product of
the time to decide 3SUM and the number of BIS queries.

1.2

Our Results

In this work, we present two new algorithms. In what follows, let G = ([n], E) be a simple,
unweighted graph with |E| = m edges. Our first algorithm, using BIS queries, gives the following.
Theorem 1.2. Given n ≥ 16 and

36√log n
m

≤ ε ≤ 12 , there exists an algorithm that makes

BIS queries and outputs m
e such that with probability at least 1 −
(1 − ε)m ≤ m
e ≤ (1 + ε)m.
3

polylog(n)
,
n2

polylog(n)
ε4

We remark that since polylog(n) BIS queries can simulate a degree query (see Appendix A), one
can obtain a (2 ±ε)-factor approximation of m by using Feige’s algorithm [Fei06], which uses degree
√
queries. This gives an algorithm that uses O( n · polylog(n)/poly(ε)) BIS queries. Theorem 1.2,
however, provides better guarantees in terms of the approximation and the number of BIS queries.
Compared to the result of Dell and Lapinskas [DL17] (Theorem 1.1), our algorithm uses a
significantly fewer number of queries, since we do not have to make n · polylog(n) edge existence
queries. In terms of their specific applications, it does not seem that our improvement implies
anything significant for fine-grained complexity. It would be interesting to find problems where a
more efficient BIS algorithm would lead to new decision versus counting complexity results.
Our second algorithm, using only IS queries, gives the following.
Theorem 1.3. Given n ≥ 8 and

324√log4 n
m


min

≤ ε ≤ 21 , there exists an algorithm that makes

√ 
m
n2
· polylog(n)
,
2
ε m ε

IS queries and outputs m
e such that with probability at least 1 −

1
,
n2

(1 − ε)m ≤ m
e ≤ (1 + ε)m.
The first term

n2
ε2 m

· polylog(n) comes from a folklore algorithm that estimates the number of
√

edges using edge existence queries (see Section 6 for a proof). The second term
the number ofnqueries
used by our new algorithm.
√ o
2/3
m
n2
Since min ε2 m , ε
≤ nε4/3 , we also get the following corollary.
Corollary 1.4. Given n ≥ 8 and

324√log4 n
m

m
ε

≤ ε ≤ 12 , there is an algorithm that makes

IS queries and outputs m
e such that with probability at least 1 −

· polylog(n) is

n2/3
·polylog(n)
ε4/3

1
,
n2

(1 − ε)m ≤ m
e ≤ (1 + ε)m.
Comparing the above theorems, we observe that, perhaps surprisingly, BIS queries are much
more effective for estimating the number of edges than IS queries.
Comparison with Other Queries. Table 1 quantitatively summarizes the results for estimating
the number of edges in a graph in the context of various query types. Given some of the results
in Table 1 on edge estimation using other types of queries, a natural question is how well BIS
and IS queries can simulate such queries. In Appendix A, we show that polylog(n) BIS queries
are sufficient to simulate degree queries. On the other hand, we do not know how to simulate
a neighbor query (to find a specific neighbor) with few BIS queries, but a random neighbor of a
vertex can be found with O(log n) BIS queries (see [BKKR13]). For IS queries,
 it turns
 out that
n
estimating the degree of a vertex v up to a constant factor requires at least Ω deg(v) IS queries
(we expand on this in Section 6.4).
Notation. Throughout this text, log and ln will denote the logarithm taken in base two and e,
respectively. The set {1, . . . , k} will be denoted by [k]. The notation x = polylog(n) means
x = O(logc n) for some constant c > 0. When we say A1 , . . . , Ak is a partition of the set A into k
parts we allow each Ai to be empty. In particular, a uniformly random partition of A into k parts
is chosen by coloring each element of A with a random number in [k] and identifying Ai with the
elements colored with i.
4

Query Types

Approximation

# Queries (up to const. factors)

Reference

Edge Existence

1+ε

Degree

2+ε

Degree + Neighbor

1+ε

n2
· poly(log n, 1/ε)
m
√
n
· log n
ε
√
n · poly(log n, 1/ε)

Subset

1+ε

log n · poly(1/ε)

[Sto85, FJO+ 16]

BIS + Edge Existence

1+ε

n · poly(log n, 1/ε)

[DL17]

BIS

1+ε

This Work

IS

1+ε

poly(log n, 1/ε)


√
n2
m,
· poly(log n, 1/ε)
min
m

Folklore (see §6)
[Fei06]
[GR08]

This Work

Table 1: Comparison of the best known algorithms using a variety of queries for estimating the
number of edges m in a graph with n vertices. The bounds stated are for high probability results,
with error probability at most 1/n. Constant factors are suppressed for readability.

2

Overview of the Algorithms

We describe our algorithms using BIS and IS queries separately.

2.1

BIS Algorithm

Our discussion of the BIS algorithm will parallel Figure 2.1, which depicts the main components
of one level of our recursive algorithm.
Our algorithms rely on the ability to exactly count the edges between two subsets of vertices,
in time nearly linear in the number of such edges. In particular, we provide a simple, deterministic divide and conquer algorithm to determine e(A, B) using O(e(A, B) log n) BIS queries. More
concretely, we will prove the following in the next section.
Lemma 2.1. For every A, B ⊆ [n] that are disjoint, there is a deterministic algorithm that exactly
computes e(A, B) using at least e(A,B)+1
and at most 5 · e(A, B)dlog ne + 1 BIS queries.
2
Given this algorithm, it is natural to wonder if the graph could be sparsified in such a way that
the number of remaining edges is a good estimate for the original number of edges (after scaling).
Consider sparsifying the graph by coloring the vertices of graph and only looking at the edges going
between certain pairs of color classes (in our algorithm, these pairs will be a matching of the color
classes). We prove that it suffices to only count the edges between the color classes, and we can
ignore the edges with both endpoints inside a single color class.
Lemma 2.2 (Basic Sparsification). Let G = ([n], E) be a graph with m edges. For 1 ≤ k ≤ bn/2c,
let A1 , . . . , Ak , B1 , . . . , Bk be a uniformly random partition of [n] Then,
"
#
k
X
√
1
P 2k
e(Ai , Bi ) − m ≥ 18k · m log n ≤ 4 .
n
i=1

5

Coloring

Sparsification

Coarse Estimate
sparse

dense

Group by Estimates

Importance Sampling
Exact Count

Recurse

Figure 2.1: A depiction of one level of the BIS algorithm. In the first step, we color the vertices and sparsify the
graph by only looking at the edges between vertices of the same color. In the second step, we coarsely estimate the
number of edges in each colored subgraph. Next, we group these subgraphs based on their coarse estimates, and we
subsample from the groups with a relatively large number of edges. In the final step, we exactly count the edges in
the sparse subgraphs, and we recurse on the dense subgraphs.

An important consequence of this lemma is that we can assume without loss of generality that
the graph is bipartite. Indeed, invoking the lemma with k = 2, estimating the edges between the
two color classes is equivalent to estimating the total number of edges, up to a factor of two. For
the rest of the discussion, we will consider colorings that respect the bipartition.
After coloring the graph, we have reduced the problem to estimating the total number of edges
in a collection of bipartite subgraphs. However, certain subgraphs may still have a large number of
edges, and it would be too expensive to directly use the exact counting algorithm. To remedy this,
we develop an algorithm that coarsely estimates the number of edges in a subgraph, up a O(log2 n)
factor, using only O(log3 n) BIS queries.
Using the coarse estimates we can form O(log n) groups of bipartite subgraphs, where each group
contains subgraphs with a comparable number of edges. For the groups with only a polylogarithmic
number of edges, we can exactly count edges using polylog(n) BIS queries. For the remaining
groups, we subsample a polylogarithmic number of subgraphs from each group. Since the groups
contained subgraphs with a similar number of edges, the number of edges in the subsampled
subgraphs will be proportional to the total number of edges in the group, up to a scaling factor

6

depending on the group, with high probability. This corresponds to the technique of importance
sampling that is used for variance reduction when estimating a sum of random variables that have
comparable magnitudes.
After exactly counting the edges in the sparse subgraphs, we are left with the task of estimating
the number of edges in the subsampled subgraphs. By the sparsification guarantee, the number
of edges in these subgraphs has gone down by a factor of k (which will be a constant) with high
probability. We now recurse on the collection of subsampled subgraphs. Since the number of edges
has gone down by a constant fraction, we only need to repeat this process a logarithmic number of
times. Overall, at every level of the recursion, we work with a polylogarithmic number of subgraphs,
and hence, we only make a polylogarithmic number of BIS queries in total.
Note that we have to scale the estimates after the sparsification step and the subsampling
step. We handle this in our algorithm by associating each subgraph with a weight, and outputting
the weighted sum of the estimates of the subgraphs. The scaling factors after sparsification and
subsampling are reflected by updating the weights appropriately. These weights are also used when
grouping subgraphs based on the coarse estimates. Overall, the final estimate corresponds to the
weighted sum of the estimates of the subgraphs. Figure 2.1 depicts the main components of one
level of our algorithm.
We now describe the algorithms for exact counting and coarse estimation in more detail.
2.1.1

Exact Counting

Let A, B be disjoint subsets of vertices. We explain how to use BIS queries to compute e(A, B),
the number of edges between A and B. We use a divide and conquer approach. For the first step,
let A1 , A2 and B1 , B2 be equipartitions of A and B, respectively. Observe that
e(A, B) = e(A1 , B1 ) + e(A1 , B2 ) + e(A2 , B1 ) + e(A2 , B2 ).
For any pair (Ai , Bj ) that has no edges, we can determine e(Ai , Bj ) = 0 with a single BIS query.
Otherwise, we describe how to recursively determine e(Ai , Bj ).
We build a quadtree starting with (A, B) as the root. If |A| = |B| = 1, then we query this pair
directly and label it with the value of e(A, B), which is 0 or 1 in this case. Otherwise, we still query
the pair (A, B), and if e(A, B) = 0, label the node as 0 and terminate. In the remaining case, we
know that e(A, B) 6= 0, and the algorithm will recurse on the four children of (A, B), which will
correspond to the pairs (A1 , B1 ), (A1 , B2 ), (A2 , B1 ), and (A2 , B2 ).
To determine e(A, B), the algorithm simply needs to sum the labels of all the leaves in this
tree. The number of queries is equal to total number of nodes in the tree. One can prove that the
number of nodes is at most O(e(A, B) · log n) + 1. The intuition is that the number of leaves labeled
with a 1 is exactly e(A, B), and the number labeled with a zero is at most O(e(A, B) · log n) + 1.
2.1.2

Coarse Estimator

We explain how to estimate e(A, B) up to a factor of O(log2 n) using O(log3 n) BIS queries. As
a warm-up, assume all vertices in A have degree in the range (2i , 2i+1 ] for some i > 0. Sample a
subset A0 ⊆ A by including every vertex in A independently with probability 2i /e
e for an estimate ee
0
we will determine later. Then, sample B ⊆ B by including every vertex in B independently with
probability 1/2i . When ee ≈ e(A, B), there will be an edge between A0 and B 0 with good probability,
and when ee  e(A, B) · log(n), then there will be no such edge with good probability. Therefore,
we can perform a geometric search for ee ≈ e(A, B) to determine e(A, B).

7

Now, we are left with the task of finding a value i∗ such that a good fraction of all the edges
∗
in the graph are incident on the vertices in A that have degree roughly 2i . By grouping vertices
of degree (2i , 2i+1 ] together, the pigeonhole principle guarantees that there is an i∗ ∈ {0, . . . , log n}
∗
such that the edges touching the vertices of degree roughly 2i is 1/ log n fraction of all the edges. To
find the value of i∗ , we perform a geometric search over the possible values i = 1, 2, 4, 8, . . . , 2 log n.
The two sources of error thus come from the estimate of i∗ and the acceptance probability based
on the estimate for ee. Since each contributes a factor of O(log n) to the error, the coarse estimate
for e(A, B) will have the following guarantee.
Lemma 2.3. Let n ≥ 16. For every A, B ⊆ [n] that are disjoint, there exists a randomized
algorithm CoarseEstimator(A, B) that makes at most cce log3 n BIS queries (for a constant cce ) and
n
outputs ee ≤ n2 such that with probability at least 1 − 4 log
, the following holds
n4
e(A, B)
≤ ee ≤ e(A, B) · 8 log n.
8 log n

2.2

IS Algorithm

As with the BIS algorithm, the main building block for the IS algorithm is an efficient way to exactly
count edges using IS queries. The strategy for the BIS exact counting algorithm fails because the
total number of nodes in the tree can be much large than e(A ∪ B), up to O(n2 ) in the worse case.
However, if we pick the sets A1 , A2 at random, then the overall number of queries will be small
with high probability. Thus, this randomized modification of the BIS exact counting algorithm
computes e(A, B) using O(e(A ∪ B) log2 n) IS queries with high probability. In particular, we prove
the following result.
Lemma 2.4. For every A, B ⊆ [n] that are disjoint, there is a randomized algorithm that exactly
and at most c·e(A∪B)dlog2 ne+1 IS queries for a constant
computes e(A, B) using at least e(A,B)+1
2
1
c, with probability at least 1 − n6 .
With this lemma in hand, we will again sparsify the graph to reduce the overall number of IS
queries. In contrast to the BIS queries, we do not know how to design a coarse estimator using only
IS queries (see §6.4). This prohibits us from designing an analogous recursive algorithm. Instead,
we estimate the number of edges in one shot, by coloring the graph with a large number of colors
and estimating the number of edges going between a matching of the color classes. We now discuss
the reasons behind using a matching of the color classes.
An initial sparsification attempt might be to count only the edges going
 between a single pair
of colors. If the total number of colors is 2k, then we expect to see m/ 2k
this pair.
2 edges between

2k
Therefore, we could set k to be large and invoke Lemma 2.4. Scaling by a factor of 2 , we would
hope to get an unbiased estimator for m.
Unfortunately, a star graph demonstrates that this approach does not work, due to large
 variance. If we randomly color the vertices of the star graph with 2k colors, then out of the 2k
2 pairs
of color classes, only 2k − 1 pairs have any edge going across. So, if we only chose one pair of color
classes, then with high probability one of the following two cases occurs: either (i) there is no edge
crossing the color pair, or (ii) the number
 of edges crossing the pair is ≈ m/2k. In both cases our
estimate after scaling by a factor of 2k
2 will be far from the truth.
At the other extreme, the vast majority of edges will be present if we look at the edges crossing
all pairs of color classes. Indeed, the only edges we miss have both endpoints in a color class, and
this accounts for only a 1/k fraction of the total number of edges. Thus, this does not achieve any
substantial sparsification.
8

By using a matching of the color classes, we simultaneously get a reliable estimate of the
number of edges and a sufficiently sparsified graph, as already testified by Lemma 2.2. Let
A1 , · · · , Ak , B1 , · · · , Bk be a random partition of the
2.2 then
Pvertices into 2k color classes. Lemma
√
implies that with high probability, the estimator 2k ki=1 e(Ai , Bi ) is in the range m±O(k m log n).
√
Hence, as long as we choose k to be less than ε m/polylog(n), we approximate m up to a factor
of (1 ± O(ε)). We use geometric search to find such a k efficiently.
P
To get a bound on the number of IS queries, we claim that we can compute ki=1 e(Ai , Bi )
using Lemma 2.4, with a total of k + m
k · polylog(n) IS queries. The first term arises since we
have to make at least one query for each of the k color pairs (even if there are no edges between
them). For the second term, we pay for both (i) the edges between the color classes and (ii) the
total number of edges with both endpoints within a color class (since the number of IS queries in
Lemma 2.4 scales with e(A ∪ B)). By the sparsification lemma, we know that (i) is bounded by
O( m
and we can prove an analogous statement for (ii). Hence, plugging in
k ) with high probability
√
√
ε m
a value of k ≈ polylog(n) , the total number of IS queries is bounded by m · polylog(n)/ε.

2.3

Outline

The rest of the paper is organized as follows. In Section 3, we formally present the algorithms
to exactly count edges between two subsets of vertices (Lemmas 2.1 and 2.4). In Section 4, we
prove our sparsification result (Lemma 4.1). In Section 5.1, we present the algorithm that uses
BIS queries to coarsely estimate the number of edges between two subsets of vertices (Lemma 2.3).
We combine these building blocks to construct our edge estimation algorithm using BIS queries in
Section 5.2. In Section 6, we present our algorithm using IS queries. We conclude in Section 7 and
mention open questions.

3

Exact Edge Counting using BIS and IS Queries

In this section, we prove Lemmas 2.1 and 2.4. We give a deterministic algorithm that builds a tree
by repeatedly partitioning A and B using BIS queries. The leaves of this tree identify the edges we
want to count and the number of BIS queries made to construct this tree is O(e(A, B) log n). For
the case of IS queries, we give a similar randomized algorithm that uses random partitioning and
makes O(e(A ∪ B) log2 n) IS queries.
To present the proof, we will need the following definition.
Definition 3.1. An equipartition of a set A with |A| ≥ 2 is a partition A1 , A2 of A satisfying
|A1 | = d|A|/2e and |A2 | = b|A|/2c. A random equipartition is an equipartition chosen uniformly
at random from all equipartitions.

3.1

Proof of Lemma 2.1

We construct a rooted tree where every vertex is identified with a pair (A0 , B 0 ), where A0 ⊆ A and
B 0 ⊆ B, and the root of the tree is the input pair (A, B). The leaves of the tree will correspond
to (A0 , B 0 ) with either |A0 | = |B 0 | = 1 or e(A0 , B 0 ) = 0. These leaves will be labeled with 1 if
e(A0 , B 0 ) > 1 and 0 otherwise. The tree has the property that every edge contributing to e(A, B)
appears as a leaf, and there will be exactly e(A, B) leaves labeled 1. Thus, the leaves and their
labels suffice to compute e(A, B). Finally, this tree can be built and labeled using BIS queries.

9

We now proceed to describe the tree, which is constructed recursively by the following deterministic process. If e(A, B) = 0, then assign a 0 to the root and terminate. Otherwise, let (A0 , B 0 )
be the current internal node. Then
• if e(A0 , B 0 ) ≥ 1, |A0 | > 1 and |B 0 | > 1, let A01 , A02 (resp. B10 , B20 ) be an equipartition of A0
(resp. B 0 ). Add the nodes (A01 , B10 ), (A01 , B20 ), (A02 , B10 ) and (A02 , B20 ) as the children.
• if e(A0 , B 0 ) ≥ 1, |A0 | = 1 and |B 0 | > 1, let B10 , B20 be any equipartition of B 0 . Add the nodes
(A0 , B10 ) and (A0 , B20 ) as the children.
• if e(A0 , B 0 ) ≥ 1, |A0 | > 1 and |B 0 | = 1, let A01 , A02 be any equipartition of A0 . Add the nodes
(A01 , B 0 ) and (A02 , B 0 ) as the children.
We claim that the total number of BIS queries used by this process is at most 5e(A, B)dlog ne+1.
First, note that since we make one query for each node, we simply have to bound the number of
nodes. We argue that each internal node of this tree lies on a path from the root to a leaf with
value 1. Indeed, if (A0 , B 0 ) is an internal node, then e(A0 , B 0 ) ≥ 1, and hence some leaf in the
sub-tree rooted at (A0 , B 0 ) is labeled with the value 1.
Notice that the depth of the tree is dlog ne and the number of leaves with value 1 is e(A, B).
This implies that the total number of internal nodes is at most e(A, B)(dlog ne − 1). The number of
leaves that are assigned a 0 is at most 4e(A, B)dlog ne + 1 (since each node has at most 4 children).
Therefore, the total number of nodes in the tree is at most e(A, B)dlog ne + 4e(A, B)dlog ne + 1, in
turn implying that the total number of BIS queries made is at most 5e(A, B)dlog ne + 1.
The number of BIS queries made is always at least max{e(A, B), 1} ≥ e(A,B)+1
since every edge
2
with one endpoint in A and the other in B is identified.

3.2

Proof of Lemma 2.4

We will need the following fact. Let A1 , A2 be a random equipartition of A ⊆ [n], then
E[e(A1 ) + e(A2 )] ≤ e(A)/2.

(3.1)

This holds because any edge with both endpoints in Ai for i ∈ [2] contributes one to the sum
e(A1 ) + e(A2 ) with probability at most 1/2.
We again construct a tree with root (A, B). In this case, the leaves will correspond to (A0 , B 0 )
with either |A0 | = |B 0 | = 1 or e(A0 ∪ B 0 ) = 0. These leaves will be labeled with 1 if e(A0 , B 0 ) > 1
and 0 otherwise. As before, there will be exactly e(A, B) leaves labeled 1. This tree can be built
and labeled using IS queries.
We now describe the tree, which is constructed recursively by the following random process. If
e(A ∪ B) = 0, then assign a 0 to the root and terminate. Otherwise, let (A0 , B 0 ) be the current
internal node. Then
• if e(A0 ∪ B 0 ) ≥ 1, |A0 | > 1 and |B 0 | > 1, let A01 , A02 (resp. B10 , B20 ) be a random equipartition
of A0 (resp. B 0 ). Add the nodes (A01 , B10 ), (A01 , B20 ), (A02 , B10 ) and (A02 , B20 ) as the children.
• if e(A0 ∪ B 0 ) ≥ 1, |A0 | = 1 and |B 0 | > 1, let B10 , B20 be a random equipartition of B 0 . Add the
nodes (A0 , B10 ) and (A0 , B20 ) as the children.
• if e(A0 ∪ B 0 ) ≥ 1, |A0 | > 1 and |B 0 | = 1, let A01 , A02 be a random equipartition of A0 . Add the
nodes (A01 , B 0 ) and (A02 , B 0 ) as the children.

10

We first bound the expected number of IS queries, then we use this Las Vegas algorithm as a
black-box to prove the lemma. The expected number of IS queries equals the expected number of
nodes. Since each internal node has either two or four children, the total number of nodes is at
most twice the number of leaves. Let L(A0 , B 0 ) denote the number of leaves in the sub-tree rooted
at (A0 , B 0 ). We will use the following claim to prove the lemma, then we will prove the claim.
Claim 3.2. For any node (A0 , B 0 ) in the tree, we have



E L(A0 , B 0 ) ≤ 6 · log max{|A0 |, |B 0 |} e(A0 ∪ B 0 ) + 1,
where the expectation is over the random sub-tree rooted at (A0 , B 0 ).
Applying the claim to (A, B), we have that the expected number of IS queries is at most
2E[L(A, B)] ≤ 12dlog ne·e(A, B)+2. By Markov’s inequality, we conclude that the probability that
the algorithm makes more than 24e(A, B)dlog ne + 4 IS queries is at most 21 . The lemma follows by
running 6dlog ne independent threads of the above algorithm in parallel and outputting the answer
of the first copy that finishes while terminating the other parallel threads.
 With probability at least
1 − n16 , the total number of IS queries at most c · e(A ∪ B) log2 n + 1 for some constant c > 1.
The number of IS queries made by the algorithm is always at least max{e(A, B), 1} ≥
since every edge with one endpoint in A and the other in B is identified by an IS query.
We now prove the claim.

e(A,B)+1
2

Proof of Claim 3.2. We may assume that e(A0 ∪ B 0 ) ≥ 1, since if e(A0 ∪ B 0 ) = 0, then the sub-tree
rooted at (A0 , B 0 ) is a leaf and hence L(A0 , B 0 ) = 1. We now prove the claim by induction on |A0 ∪B 0 |.
Base Case (|A0 ∪ B 0 | = 2): In this case, the sub-tree rooted at (A0 , B 0 ) is a leaf and L(A0 , B 0 ) = 1.
Induction Step (|A0 ∪ B 0 | ≥ 3): Without loss of generality, we can assume that |A0 | ≥ |B 0 |.
This implies |A0 | ≥ 2. If (A01 , A02 ) is an equipartition of A0 , then |A02 | ≤ |A01 | = d|A0 |/2e and
 0 
|A |
1
0 ≤ log |A01 | ≤ log
≤ log |A0 | − .
(3.2)
2
2
We now separately consider two cases, depending on if the node has two or four children.
(i) Case (A0 , B 0 ) has four children: Since (A0i , Bj0 ) for i, j ∈ [2] are children of (A0 , B 0 ), using
linearity of expectation, we have










E L(A0 , B 0 ) = E L(A01 , B10 ) + E L(A01 , B20 ) + E L(A02 , B10 ) + E L(A02 , B20 ) .
As |A0i ∪ Bj0 | < |A0 ∪ B 0 |, for i, j ∈ [2], we can apply the induction hypothesis on (A0i , Bj0 ). Since
|A0 | ≥ |B 0 |, we have that max{|A0i |, |Bj0 |} ≤ |A01 |. By the inductive hypothesis and (3.2), we have
E[L(A0 , B 0 )] ≤ 6 log |A01 | · E[e(A01 ∪ B10 ) + e(A01 ∪ B10 ) + e(A01 ∪ B10 ) + e(A01 ∪ B10 )] + 4


1
≤ 6 log |A0 | −
· E[e(A01 ∪ B10 ) + e(A01 ∪ B10 ) + e(A01 ∪ B10 ) + e(A01 ∪ B10 )] + 4
2


1
0
= 6 log |A | −
· E[2e(A01 ) + 2e(A02 ) + 2e(B10 ) + 2e(B20 ) + e(A0 , B 0 )] + 4, (3.3)
2
where the last equality follows since e(A0i ∪ Bj0 ) = e(A0i ) + e(Bj0 ) + e(Ai , Bj ) for i, j ∈ [2].
11

Since A01 , A02 and B10 , B20 are random equipartitions, we have by (3.1) that
E[e(A01 ) + e(A02 ) + e(B10 ) + e(B20 )] ≤

e(A0 ) + e(B 0 )
.
2

Plugging this in (3.3), and using (3.2) and e(A0 ∪ B 0 ) = e(A0 ) + e(B 0 ) + e(A0 , B 0 ), we have




1
· e(A0 ∪ B 0 ) + 4
E L(A0 , B 0 ) ≤ 6 log |A0 | −
2
= 6 log |A0 | · e(A0 ∪ B 0 ) − 3e(A0 ∪ B 0 ) + 4 ≤ 6 · log |A0 | · e(A0 ∪ B 0 ) + 1,
where the last inequality follows from our initial assumption that e(A0 ∪ B 0 ) ≥ 1.
(ii) Case (A0 , B 0 ) has two children: Recall that we have assumed |A0 | ≥ |B 0 | and hence |A0 | ≥ 2.
Since this node has two children, it must be the case that |B 0 | = 1. Let (A01 , B 0 ) and (A02 , B 0 ) be
the two children. By linearity of expectation,






E L(A0 , B 0 ) = E L(A01 , B 0 ) + E L(A02 , B 0 ) .
As |A0i ∪ B 0 | < |A0 ∪ B 0 |, for i ∈ [2], we can apply the induction hypothesis on (A0i , B 0 ). Since
≥ |B 0 | = 1, we have that max{|A0i |, |B 0 |} = |A0i | ≤ |A01 |. By the inductive hypothesis and (3.2),


E L(A0 , B 0 ) ≤ 6 · log |A01 | · E[e(A01 ∪ B 0 ) + e(A02 ∪ B 0 )] + 2




1
0
≤ 6 log |A | −
· E e(A01 ∪ B 0 ) + e(A02 ∪ B 0 ) + 2
2


1
0
= 6 log |A | −
· E[e(A01 ) + e(A02 ) + e(A0 , B 0 )] + 2,
(3.4)
2

|A0 |

since e(B 0 ) = 0 when |B 0 | = 1. Using (3.1), we have E[e(A01 ) + e(A02 )] ≤ e(A0 )/2 ≤ e(A0 ). Now, as
e(A0 ∪ B 0 ) = e(A0 ) + e(A0 , B 0 ), we can use (3.2) and (3.4) to conclude




1
0
0
0
E L(A , B ) ≤ 6 log |A | −
· e(A0 ∪ B 0 ) + 2
2
= 6 log |A0 | · e(A0 ∪ B 0 ) − 3e(A0 ∪ B 0 ) + 2 ≤ 6 · log |A0 | · e(A0 ∪ B 0 ),
where in the last inequality we again used our initial assumption that e(A0 ∪ B 0 ) ≥ 1.

4

Sparsification by Coloring

In this section, we present and prove our sparsification lemma, which is key to both the BIS and
the IS algorithms. As discussed before, for technical reasons, we need a slightly more general
sparsification statement than the one (Lemma 2.2) described in Section 2.
Lemma 4.1. Let G = ([n], E) be a graph with m edges. For any 1 ≤ k ≤ bn/2c, let A1 , . . . , A2k be
a uniformly random partition of [n]. Then,
"
#
k
√
1
m X
(a) P
−
e(Ai , Ak+i ) ≥ 9 m log n ≤ 4
2k
n
i=1

12

"
(b) P

2k

√
m X
−
e(Ai ) ≥ 9 m log n
2k
i=1

#
≤

1
.
n4

Furthermore, for disjoint sets A, B ⊆ [n] and 2 ≤ k ≤ max{|A|, |B|}, let A1 , . . . , Ak and B1 , . . . , Bk
be uniformly random partitions of A and B, respectively. Then,
"
#
k
p
e(A, B) X
1
−
(c) P
e(Ai , Bi ) ≥ 9 e(A, B) log n ≤ 4
k
n
i=1

Proof. (a) Consider the random process that colors vertex t at step t ∈ [n] with a uniformly random
color Xt ∈ [2k]. The colors correspond to the partition of [n] into classes A1 , . . . , A2k . Define
f (X1 , . . . , Xn ) =

k
X

e(Ai , Ak+i ),

i=1

and notice that E[f ] = m/(2k) and that 0 ≤ f (X1 , . . . , Xn ) ≤ m.
When the vertex t is colored, let Ni,t be the
P number of neighbors of t colored with color i among
the first t − 1 vertices. Now, define dt = i∈[2k] Ni,t to be the total number of colored neighbors
P
of vertex t. Observe that dt is deterministic and that nt=1 dt = m holds, since dt is the number
of edges between the vertex t and the vertices in [t − 1]. Notice that E[Ni,t ] = dt /(2k). For
i ∈ [2k], let Ei,t be the event that
Ni,t −

p
dt
≤ 2 dt ln n.
2k

(4.1)

Note that when dt = 0, the event Ei,t holds with
√ probability 1 and when deg(t) ≥ 1, applying
dt
Lemma B.1(a) (with r = dt , µ = 2k and s = 2 dt ln n) gives us that Ei,t holds with probability
at least 1−2n−8 . Since 2k ≤ n, a union bound implies that with probability at least 1−2n−7 the
events E1,t , . . . , E2k,t hold simultaneously, that is, Et = ∩i∈[2k] Ei,t holds. Defining E = ∩t∈[n] Et ,
by a union bound we have that E holds with probability at least 1 − 2n−6 .
To prove our claim, we will use Lemma B.4, a version of Azuma’s inequality that takes into
account a rare bad event. √We will set the bad event to be E. We have just argued that
P[E] ≤ 2n−6 . Letting ct = 4 dt ln n + n4 , we will show
|E[f | X1 , . . . , Xt−1 , Xt = i, E] − E[f | X1 , . . . , Xt−1 , Xt = j, E]| ≤ ct

(4.2)

for any two colors i, j ∈ [2k] chosen for the vertex t. For t ∈ [n], let Mt be the number of
edges incident to the set of uncolored vertices {t + 1, . . . , n} that go between the colored pairs
(A1 , A1+k ), (A2 , A2+k ), . . . , (Ak , A2k ). For every i, j ∈ [2k],
|E[f | X1 , . . . , Xt−1 , Xt = i, E] − E[f | X1 , . . . , Xt−1 , Xt = j, E]|
= |Ni,t + E[Mt | X1 , . . . , Xt−1 , Xt = i, E] − Nj,t − E[Mt | X1 , . . . , Xt−1 , Xt = j, E]|
≤ |Ni,t − Nj,t | + |E[Mt | X1 , . . . , Xt−1 , Xt = i, E] − E[Mt | X1 , . . . , Xt−1 , Xt = j, E]| ,
where the inequality follows from the triangle inequality. Note that for any i ∈ [n], we have
0 ≤ E[Mt | X1 , . . . , Xt−1 , Xt = i, E] ≤ m. Also, since Mt only involves vertices {t + 1, . . . , n},
we have, for any j ∈ [n],
E[Mt | X1 , . . . , Xt−1 , Xt = i] = E[Mt | X1 , . . . , Xt−1 , Xt = j].
13

(4.3)

and combining (4.1) and (4.3), and conditioning on E,
 
P E
∆t ≤ max |Ni,t − Nj,t | +
· E[Mt | X1 , . . . , Xt = i, E] − E[Mt | X1 , . . . , Xt = j, E]
P[E]
i,j∈[2k]
 
p
2m · P E
4
≤ max |Ni,t − Nj,t | +
< 4 dt ln n + = ct .
P[E]
n
i,j∈[2k]
P
P
To apply Lemma B.4, using nt=1 dt = m, we compute t c2t as follows:
X
t∈[n]

c2t = 16 ln n

X

dt +

X 16 32 X p
+
dt ln n
n2
n

t∈[n]

t∈[n]

= 16m ln n +

16
n

≤ 16m ln n +

16
n

t∈[n]

32 X p
+
dt ln n
n
t∈[n]
r
m ln n
+ 32
≤ 17m ln n,
n

where the penultimate inequality follows from the concavity of the square-root function.
√
√
Setting s = 9 m log n − 1 > 9 m ln n − 1 and invoking Lemma B.4 finishes the proof.
P
(b) The proof is analogous to the one in part (a) with f (X1 , . . . , Xn ) = 2k
i=1 e(Ai ).
(c) Let A = {a1 , . . . , a|A| } and B = {b1 , . . . , b|B| }. The vertex sequence is a1 , . . . , a|A| , b1 , . . . , b|B|
with Xi ∈ [k] being the color
Pof the ith vertex in the sequence, for i ∈ [|A| + |B|]. Then f is
defined as f (X1 , . . . , Xn ) = ki=1 e(Ai , Bi ). The proof is analogous to part (a).

5

Edge Estimation using BIS Queries

To describe our algorithm using BIS queries, we first prove Lemma 2.3 which allows us to cheaply
get a coarse estimate for the number of edges between two subsets of the vertices. This coarse
estimator along with Lemma B.3 and the sparsification (Lemma 4.1) and exact edge counting
(Lemma 2.1) results presented in the previous sections will be essential tools in constructing our
algorithm.

5.1

Coarse Estimator

Let G = G([n], E) be a graph and let A, B ⊆ [n] be disjoint subsets of the vertices. In this section,
we prove Lemma 2.3 by giving an efficient algorithm that coarsely estimates the number of edges
e(A, B) between A and B using only O(log3 n) BIS queries.
To describe the algorithm, we will need some more notation. For a subset S ⊆ [n], define N (S)
to be the union of the neighbors of all the vertices in S and for a vertex v, let degS (v) denote the
number of neighbors of v that lie in S. For i ∈ [log n], define the set of vertices in A with degree
between 2i and 2i+1 as
Ai = {v | v ∈ A, 2i < degB (v) ≤ 2i+1 },
and let A0 denote the vertices in A with degB (v) ≤ 2.
We start with the following claim.

14

Claim 5.1. There exists an i∗ ∈ {0, 1, . . . , log n} such that
e(Ai∗ , B) ≥

e(A, B)
log n + 1

|Ai∗ | ≥

and

e(A, B)
1
·
.
∗
i
2
2(log n + 1)

P n
Proof. Since log
i=0 e(Ai , B) = e(A, B), the proof of the first inequality follows from averaging. To
see the second inequality, observe that for every i, we have e(Ai , B) ≤ |Ai |2i+1 . Hence, using the
first inequality
e(Ai∗ , B)
e(A, B)
1
|Ai∗ | ≥
≥
·
.
2i∗ +1
2 i∗
2(log n + 1)

Suppose we have an estimate ee for the number of edges between A and B in the graph. Consider the test CheckEstimate defined in Algorithm 1 for checking if the estimate ee is correct up to
logarithmic factors using a logarithmic number of BIS queries.
Algorithm 1: CheckEstimate((A, B), ee)
Input: ((A, B), ee) where A, B ⊆ [n] are disjoint and ee is a guess for e(A, B)
1
2
3
4
5
6
7
8

for i = 0, 1, . . . , log n do
Sample A0 ⊆ A by choosing each vertex in A with probability min
Sample B 0 ⊆ B by choosing each vertex of B with probability
if e(A0 , B 0 ) 6= 0 then
Output accept;
end
end
Output reject.

n

1
.
2i

o
.

2i
ee , 1

We have the following claim about the test described in Algorithm 1.
Claim 5.2. Let n ≥ 16. If e(A, B) > 0, then
(a) if ee ≥ 4e(A, B)(log n + 1), CheckEstimate((A, B), ee) accepts with probability at most 14 .
(b) if ee ≤

e(A,B)
4 log n ,

CheckEstimate((A, B), ee) accepts with probability at least 21 .

Proof. (a) For any value of the loop variable
n i i, the
o probability that a fixed edge is present in the
2
0
0
induced subgraph on A and B is min ee , 1 · 21i ≤ 1ee . Thus, E[e(A0 , B 0 )] = e(A,B)
≤ 4(log1n+1)
ee
and hence, the probability that the event e(A0 , B 0 ) 6= 0 happens for a particular value of i is
P[e(A0 , B 0 ) 6= 0] ≤ E[e(A0 , B 0 )] ≤

1
.
4(log n + 1)

By the union bound over the loop variable, the probability that the test accepts is at most 41 .
(b) It is enough to show that the probability is at least 12 when the loop variable attains the value
1
i∗ where i∗ is given by Claim 5.1. In this case, we have that |Ai∗ | ≥ e(A,B)
so
2i∗ 2(log n+1)



∗ |Ai∗ |
2i
m
1
1−
≤ exp −
ee
ee 2(log n + 1)


4 log n
1
≤ exp −
≤ 1.6 ,
2(log n + 1)
e

P[A0 ∩ Ai∗ = ∅] =

15

where the second last inequality follows since ee ≤

e(A,B)
4(log n+1)

and the last one holds since n ≥ 16.

∗

Furthermore, since degB (v) ≥ 2i for any v ∈ Ai∗ , it follows that when A0 ∩ Ai∗ 6= ∅, then
∗
|N (A0 ∩ Ai∗ )| ≥ 2i . So, we can bound
 i∗

1
1 2
≤ .
P[B ∩ N (A ∩ Ai∗ ) = ∅ | A ∩ Ai∗ =
6 ∅] ≤ 1 − i∗
2
e
0

0

0

From the above, we get
P[e(A0 , B 0 ) 6= 0] = P[A0 ∩ Ai∗ 6= ∅] P[B 0 ∩ N (A0 ∩ Ai∗ ) 6= ∅ | A0 ∩ Ai∗ 6= ∅]



1
1
1
≥ 1 − 1.6
1−
≥ .
e
e
2
Armed with the above test, we can easily estimate the number of edges up to a O(log n) factor
by just doing a search, where we start with ee = n2 and halve the number of edges each iteration.
The algorithm is given in Figure 2 and the following claim gives an analysis.
Algorithm 2: CoarseEstimator(A, B)
Input: (A, B) where A, B ⊆ [n] are disjoint
Output: An estimate ee for the number of edges e(A, B)
1
2
3
4
5
6
7
8
9

if e(A, B) = 0 then
Output 0;
end
for j = 2 log n, . . . , 0 do
Run t := 128 log n independent trials of CheckEstimate((A, B), 2j ).
if at least 3t
8 of them output accept then
Output 2j ;
end
end
e(A,B)
e ≤ 8e(A, B) log n
8 log n ≤ e
cce log3 n for a constant cce .

Claim 5.3. Let n ≥ 16. CoarseEstimator(A, B) outputs ee ≤ n2 satisfying
n
with probability at least 1 − 4 log
. The number of BIS queries made is
n4

Proof. For any fixed value of the loop variable j such that 2j ≥ 4(e(A, B) log n + 1), the expected
t
t
number of accepts is at most 4t using Claim 5.2(a). The probability that we see at least 3t
8 = 4+8
1 2
accepts can be bounded by e−2t( 8 ) ≤ n−2 by taking µ = t and s = t in Lemma B.1(a). By
u

4

8

a union bound over all values of j, the probability that none of the iterations satisfying 2j ≥
8e(A, B) log n ≥ 4e(A, B)(log n + 1) accept is at least 1 − 2 logn4n+1 by the choice of t = 128 log n.

e(A,B)
t
4 log n , the expected number of accepts is at least 2 and so the
2
−2t( 18 )
t
t
probability that we see at least 3t
≥ 1 − n14 by applying
8 = 2 − 8 accepts is at least 1 − e
t
t
Lemma B.1(a) with µl = 2 and s = 8 . Hence, conditioned on the event that the estimator has
not accepted for any j satisfying 2j > e(A,B)
4 log n , the probability that we accept for the unique j that
e(A,B)
e(A,B)
satisfies 8 log n ≤ 2j < 4 log n , is at least 1 − n−4 .

On the other hand, when 2j ≤

Overall, by the union bound, the probability that the estimator outputs an estimate ee that
n
does not satisfy e(A,B)
e ≤ 8e(A, B) log n is at most 2 logn4n+2 ≤ 4 log
. The number of queries is
8 log n ≤ e
n4
3
easily seen to be 128 log n · (2 log n + 1)(log n + 1) = 256 log n + O(log2 n) since for each value of
16

j there are t = 128 log n trials of CheckEstimate, each of which makes log n + 1 queries to the BIS
oracle.
The above claim finishes the proof of Lemma 2.3.

5.2

Overall BIS Algorithm (Proof of Theorem 1.2)

We now describe an algorithm EdgeEstimator (Algorithm 3) that makes polylog(n)
BIS queries to
ε4
estimate m within a factor of (1 ± ε). The subroutine BipartiteEstimator is given by Algorithm 4.

Algorithm 3: EdgeEstimator(ε)
Input: (n, ε): n is the number of vertices and ε is an error parameter.
Output: Estimate m
e for the number of edges m = |E|.
1
2

Partition the vertices randomly into A and B.
Compute ee = CoarseEstimator(A, B).
20

3
4
5
6
7

8
9

5

n
if ee ≤ 2 ·log
then
ε2
Compute m
e = 2 · e(A, B) exactly using Lemma 2.1.
end
else


ε
Compute m
e = 2 · BipartiteEstimator [(A, B, 1)], 4, 32 log
n where BipartiteEstimator is
given in Algorithm 4.
end
return m.
e

Theorem 5.4. Let n ≥ 16. If

36√log n
m

≤ ε ≤ 12 , then with probability at least 1 −

polylog(n)
n2

(a) |m − EdgeEstimator(ε)| ≤ ε · m,
 16 
(b) EdgeEstimator(ε) uses O logε4 n BIS queries.
To prove the above, we first need to analyze the subroutine BipartiteEstimator given in Algorithm
4. To this end, we need some more definitions. Let L be a list of (A, B, w), for A, B ⊆ [n] that are
1
disjoint and w ≥ 1. For every 0 < δ < 32 log
n , L is good if |L| ≤ 2t log(n) and for every (A, B, w) ∈ L,
5

2

k log n
13 log n
e(A, B) ≥ s, where
P t = 2 · δ2 and s = 81 · δ2 as defined in Step 5 of BipartiteEstimator.
Define e(L) = (A,B,w)∈L e(A, B). We have the following guarantee on BipartiteEstimator.

Lemma 5.5. Let n ≥ 16. If L is good and 0 < δ <
16kt log2 n·logd k e e(L)
n4

2

1
32 log n ,

then with probability at least 1 −

, the following holds

(a) |wt(L) − BipartiteEstimator(L, k, δ)| ≤ 4δ logd k e e(L) · wt(L).
2

(b) the number of BIS queries is at most cbp kst log4 n · logd k e e(L) where cbp = 210 + 2cce and cce
2
is the constant from Lemma 2.3.

17

Algorithm 4: BipartiteEstimator(L, k, δ)
Input: (L, k, δ): L is a list of triples (A, B, w) where A, B ⊆ [n] are disjoint subsets and
w ≥ 1 is a positive weight for the pair (A, B), k is an integer, and δ is an error
parameter.
P
Output: Estimate for the sum wt(L) := (A,B,w)∈L w · e(A, B).
1
2
3
4

Lref = Refine(L, k).
for each (A, B, w) ∈ Lref do
ee(A, B) = CoarseEstimator(A, B).
end
5

5
6
7
8
9

10
11
12
13

14
15
16
17
18

2

n
Set t := 213 · logδ2 n and s := 81 · k log
.
δ2
Define Llight = {(A, B,P
w) | (A, B, w) ∈ Lref , ee(A, B) ≤ 8s log n}.
Compute wt(Llight ) = (A,B,w)∈Llight w · e(A, B) exactly using Lemma 2.1.
Remove Llight from Lref .
For j ∈ [2P
log n], let Sj = {(A, B, w) | (A, B, w) ∈ Lref , w · ee(A, B) ∈ (2j , 2j+1 ]}. Define
ee(Sj ) = (A,B,w)∈Sj ee(A, B).
for j = 1, · · · , 2 log n do
if |Sj | > t then
Sample t elements uniformly, independently from Sj . Denote this multiset by Sj0 .
Update Lref by replacing each (A, B, w) ∈ Sj that was sampled in Sj0 with


pw|S |
A, B, t j , where p is the number of copies of (A, B, w) in Sj0 .

Remove each (A, B, w) ∈ Sj from Lref that is not in Sj0 .
end
end
Let Lsub be the current list.
return wt(Llight ) + BipartiteEstimator(Lsub , k, δ).

Algorithm 5: Refine(L, k)
Input: (L, k): L is a list of triples (A, B, w) where A, B ⊆ [n] are disjoint subsets and
w ≥ 1 is a positive weight for the pair (A, B), k is an integer
1
2
3
4
5

for each (A, B, w) ∈ L do
Partition A and B uniformly each into k classes A1 , . . . , Ak and B1 , . . . , Bk .
Update L by replacing (A, B, w) with (A1 , B1 , wk), · · · , (Ak , Bk , wk).
end
return L.

18

We prove Theorem 5.4 using Lemma 5.5. Note that Lemma 5.5 is applied with L = [(A, B, 1)],
c log16 n
ε
2
k = 4 and δ = 32 log
for a constant
n . Since e(L) ≤ n , the number of BIS queries is at most
ε4
c after plugging in the values of k, s, t and δ.
We first informally describe BipartiteEstimator, expanding on the overview presented in Section 2. The list L, which is the input to BipartiteEstimator, corresponds to the collection of bipartite subgraphs along with their weights. The quantity e(L) denotes the total number of edges in
this collection without the weights. The algorithm BipartiteEstimator returns an estimate of wt(L),
which is the weighted sum of the number of edges in the subgraphs.
At every level of the recursion, we maintain two invariants about the list we recurse on. The
first is that the list size is O(t log n). This comes from the fact that we only keep a small collection
of bipartite subgraphs that we recurse on. The second invariant is that for every element (A, B, w)
in the list, we have e(A, B) ≥ s. This says that we only recurse on those subgraphs that are dense.
These invariants are captured in the definition of L being good. Both parameters t and s will be
set to polylog(n) while k will be a constant.
Let L be the input to BipartiteEstimator. The algorithm starts with sparsifying each subgraph
(A, B, w) ∈ L by further partitioning it into k parts (A1 , B1 ), . . . , (Ak , Bk ). Denoting the new
list by Lref , the sparsification lemma (Lemma 4.1) then guarantees that e(Lref ) ≈ e(L)/k (graph is
sparsified) and wt(Lref ) ≈ wt(L) (the weighted sum of the number of edges in the sparsified graph is
a good estimate of the original number of edges) since we partition each (A, B, w) ∈ L individually
and increase the weight of each one by a factor of k.
Next, the algorithm BipartiteEstimator computes the coarse estimates ee(A, B) for every (A, B, w)
in L. Whenever the coarse estimate is O(s log n) = polylog(n), it computes w ·e(A, B) exactly using
the algorithm from Lemma 2.1. For the rest of the elements in the list which correspond to the dense
subgraphs, the algorithm groups them into 2 log n lists S1 , . . . , S2 log n according to the weighted
coarse estimates w ·e
e(A, B) such that w ·e
e(A, B) ≈ 2j for every element in the list Sj . This allows us
to use importance sampling (Lemma B.3) – we can subsample t elements from each list and increase
the weights by a factor of |Sj |/t. Since the coarse estimates are an O(log2 n) factor approximation
of the true estimates, and as we set t = polylog(n), we are guaranteed that for the subsampled
lists Sj0 , we have that wt(Sj0 ) ≈ wt(Sj ). The algorithm BipartiteEstimator then recurses on this
subsampled collection of bipartite subgraphs and the subsampling step ensures that the size of the
list we recurse on is O(t log n). Also, assuming our coarse estimates were correct, each subgraph in
the subsampled list is dense, so our invariant about the input list being good is maintained.
Overall, the quantity e(L) goes down by a factor of k in every level of the recursion because of
sparsification, so there are O(logk e(L)) = O(log n) levels. Each level of the recursion incurs an additive error of δ/ log n, so that the overall error is O(δ). Also, in each level of the recursion, the queries
are only made by CoarseEstimator and for the exact counting of the edges. The dominating term
comes from the exact counting and since we only count the edges exactly if ee(A, B) ≤ O(s log n),
the total number of queries made is O(kst log4 n · logk e(L)) = polylog(n).
We finally move on to the proofs of Theorems 5.4 and Lemma 5.5.
Proof of Theorem 5.4. Let A, B be the random partition chosen in Step 1 of the algorithm. Let E1
be the event that
√
|2 · e(A, B) − m| ≤ 18 m · log n,
(5.1)
and
e(A, B)
≤ ee ≤ e(A, B) · 8 log n.
8 log n
19

(5.2)

Let E2 be the event that when Step 7 of the algorithm is executed,
ε
|2e(A, B) − m|
e ≤ · e(A, B),
2

(5.3)

16

and the number of BIS queries (made in Step 7) is at most c·logε4 n for a constant c to be set later.
Conditioned on E1 ∩ E2 , we will bound the number of queries the algorithm makes, and we will
prove that the estimate is within the desired range. Then, we will show that E1 ∩ E2 holds with
high probability.
Correctness. Observe that m
e computed in either Step 4 or Step 7 satisfies (5.3). Indeed, for
Step 4, this follows by the setting of m
e = 2e(A, B), and for Step 7, this follows by conditioning on
E2 . Thus, the triangle inequality combined with (5.1) and (5.3) implies
|m − EdgeEstimator(ε)| = |m − m|
e ≤ |m − 2e(A, B)| + |2e(A, B) − m|
e
√
ε
ε
ε
≤ 18 m log n + · e(A, B) ≤ · m + · e(A, B) ≤ εm,
2
2
2
where we used the assumption ε ≥

36√log n
m

and the fact e(A, B) ≤ m.

Number of Queries. In Step 2, CoarseEstimator makes O(log3 n) queries, by Lemma 2.3. In
Step 4, the algorithm from Lemma 2.1 makes at most 5e(A, B) · log n + 2 queries. This is bounded
by
 7 
log n
2
5e(A, B) · log n + 2 ≤ 40e
e · log n + 2 = O
,
ε2
where we used (5.2) to upper bound e(A, B) and the assumption on ee in Step
 163 to
 achieve the final
log n
bound. Finally, in Step 7, conditioned on E2 , the number of queries is O
.
ε4
 
Probability. We now analyze the probability of E1 ∩E2 . In particular, we will show P E1 ≤


8
0
n
and P E2 |E1 ≤ c log
, for a constant c0 > 0. This suffices since then
n2

4 log n
n4



 


 

 polylog(n)
.
P E1 ∪ E2 = P E1 + P E2 ∩ E1 ≤ P E1 + P E2 |E1 =
n2
 
n
The claim that P E1 ≤ 4 log
follows directly from Lemma 4.1, Lemma 2.3 and a union bound.
n4


To bound P E2 |E1 , we invoke Lemma 5.5 to show that both (5.3) holds and the number of BIS
16

queries is c logε4 n with high probability where c = 4cbp · 213 · 81 and cbp is the constant from Lemma
ε
5.5. The lemma requires that L is good, which holds because L = [(A, B, 1)], k = 4, δ = 32 log
n,
and using (5.2),
ee
210 · 81 · log4 n
81k log2 n
e(A, B) ≥
>
≥
= s,
8 log n
ε2
δ2
13

5

n
.
where the second inequality holds since BipartiteEstimator executes in Step 7 only if ee > 2 ·81·log
ε2
2
To verify (5.3), we compute that wt([(A, B, 1)]) = e([(A, B, 1)]) = e(A, B) ≤ n . Then, Lemma 5.5
c log10 n
implies that with probability at least 1 − p ε2 n4 (where cp is a constant), we have


ε
|2e(A, B) − m|
e = 2 wt([(A, B, 1)]) − BipartiteEstimator [(A, B, 1)], 4,
32 log n
ε
ε
≤8·
· log(n2 )e(A, B) ≤ · e(A, B).
32 log n
2

20

and the number of BIS queries is O
cp log10 n
ε2 n4

≤

c0 log8 n
n2



log16 n
ε4



. Since ε ≥

36√log n
m

≥

36 log n
,
n



it follows that P E2 |E1 ≤

for a constant c0 > 0.

Proof of Lemma 5.5. For the proof, it will be more convenient for us to view item (a) in the
statement of the claim as a ratio:
1 − 4δ logd k e e(L) ≤
2

BipartiteEstimator(L, k, δ)
≤ 1 + 4δ logd k e e(L).
2
wt(L)

(5.4)

Throughout this proof, for any inequality where we bound a ratio, we will assume that the denominator in the ratio is non-zero since in those cases the numerator will also be zero and the
inequalities we are interested in would trivially be true.
Observe that after Step 1 of the algorithm BipartiteEstimator, |Lref | ≤ k|L| ≤ 2kt log n since L
is good. Also, note that for each (A, B, w) ∈ L, the Refine step partitions A, B into k uniformly
random parts A1 , · · · , Ak and B1 , · · · , Bk respectively and increases the weight of each (Ai , Bi ) pair
2
n
by a factor of k. Since L is good, e(A, B) ≥ s = 81 · k log
for each (A, B, w) in L. Note that this
δ2
p
implies that 9 ke(A, B) log n ≤ δe(A, B). Lemma 4.1 then implies for a fixed (A, B, w) ∈ L with
n
probability at least 1 − 4 log
,
n4
k
X

k · e(Ai , Bi ) − e(A, B) ≤ 9k

p
e(A, B) · log n ≤ δ · e(A, B).

i=1

Rewriting the above as a ratio:
Pk
1−δ ≤

· e(Ai , Bi )
≤ 1 + δ.
e(A, B)

i=1 k

(5.5)

P
Note that wt(Lref ) is the sum of all the kw · ki=1 e(Ai , Bi ) terms for each (A, B, w) ∈ L. Since,
n
L is good, |L| ≤ 2t log n and by a union bound we get that with probability at least 1 − 2t nlog
,
4
(5.5) holds for all (A, B, w) ∈ L. When this happens, we can bound
P

P
k
kw
·
e(A
,
B
)
i
i
(A,B,w)∈L
i=1
wt(Lref )
P
1−δ ≤
=
≤ 1 + δ, and
(5.6)
wt(L)
(A,B,w)∈L w · e(A, B)

1−δ ≤

k · e(Lref )
≤ 1 + δ.
e(L)

(5.7)

In particular, (5.7) gives us that
e(Lref ) ≤

2
· e(L).
k

(5.8)

Furthermore, by Lemma 2.3 and an union bound over all elements in Lref , we get that with
2
n
probability at least 1 − 8kt nlog
, the coarse estimator guarantee is satisfied for the entire list Lref
4
in Steps 2-4 of BipartiteEstimator:
e(A, B)
≤ ee(A, B) ≤ e(A, B) · 8 log n for every (A, B, w) ∈ Lref .
8 log n
21

(5.9)

For the rest of this proof, let us condition on the event B that (5.6), (5.8) and (5.9) hold. By a
2
log n
union bound, the probability of the event B is at least 1 − 8kt log nn+2t
.
4
Base Case (e(L) ≤ ks/2): For every (A, B, w) ∈ Lref , By (5.8), we have
e(A, B) ≤ e(Lref ) ≤

2
· e(L) ≤ s.
k

Then, (5.9) implies that ee(A, B) ≤ 8s log n. This implies that Llight = Lref . Therefore, wt(Lref ) is
computed exactly in Step 7. So, using (5.6), item (a) in the statement of the claim follows.
The number of BIS queries made by calls to CoarseEstimator is at most
|Lref | · cce log3 n ≤ 2cce kt log3 n
and the total number of queries made for the exact counts in Step 9 using the algorithm from
Lemma 2.1 is at most (5e(Lref ) log n + 2) ≤ 5 · 2e(L)
k · log n + 2 ≤ 5s log n + 2 using (5.8). In total,
the number of queries can be bounded by cbp kst log3 n, where cbp = 210 + 2cce .
Inductive Step (e(L) > ks/2): Let us assume that the claim is true for all good lists L0 with
< e(L) and we will prove that it holds for L.
To analyze Steps 12-16 of BipartiteEstimator, we will apply Lemma B.3. Note that since we have
conditioned on B, (5.9) holds and hence for every (A, B, w) ∈ Sj ,
e(L0 )

2j
≤ w · e(A, B) ≤ 2j+1 · 8 log n
8 log n
using (5.9). In order to apply Lemma B.3, we set b = 8 log n and γ = n14 . The number of samples
required is at least


5
1
b4
log4 n
13 log n
1 + ln
· 2 = (1 + 4 ln n) · 211 ·
<
2
·
.
γ
2δ
δ2
δ2
5

Since t = 213 · logδ2 n , Lemma B.3 implies that the following holds with probability at least 1 −
for the subsampled multiset Sj0 in Steps 12-16 of BipartiteEstimator:
X
1−δ ≤

(A,B,w)∈Sj0

1
n4

|Sj |
· w · e(A, B)
t

X

w · e(A, B)

≤ 1 + δ.

(5.10)

(A,B,w)∈Sj

Note that Step 14 of the algorithm increases the weight of the each element in Sj that was subp|S |
sampled in Sj0 by a factor of t j , where p is the number of times it was sampled in Sj0 . Let D
be the event that (5.10) holds for every j ∈ [2 log n] for which Steps 14 is executed. By a union
n
. Let Lsub be the list defined in Step 17 of the algorithm.
bound, it follows that P[D|B] ≤ 2 log
n4
Since wt(Llight ) is computed exactly, we have that conditioned on D the following holds:
1−δ ≤

wt(Lsub )
≤1+δ
wt(Lref ) − wt(Llight )

22

(5.11)

We now show that Lsub is good and e(Lsub ) ≤ k2 · e(L). Note that no element in Llight is in Lsub ,
where Lsub is defined in Step 17, and thus ee(A, B) ≥ 8s log n for any (A, B, w) ∈ Lsub . By (5.9),
we know e(A, B) ≥ s. Furthermore, Steps 11-15 guarantee that |Lsub | ≤ 2t log n. This implies
that Lsub is good. Observe that e(Lsub ) ≤ e(Lref ), since Step 13 of the Algorithm ensures that the
updated Lsub does not contain any duplicated elements. Using (5.8), we get that e(Lsub ) ≤ k2 e(L).
When the recursive call is made in Step 18 with Lsub , then Lsub is good and e(Lsub ) < e(L), so
the induction hypothesis gives an event E with P[E] ≤

16kt log2 n logd k e e(Lsub )
n4

2

so the following holds:

(a)
1 − 4δ logd k e e(Lsub ) ≤
2

BipartiteEstimator(Lsub , k, δ)
≤ 1 + 4δ logk e(Lsub ).
wt(Lsub )

(5.12)

(b) the number of BIS queries is at most
cbp kst · log5 n · logd k e e(Lsub ),
2

where cbp = 210 + 2cce .
We will prove that the inductive guarantee in the statement of the claim holds for L when the
event D ∩ E occurs (recall that we have already conditioned on the event B).
Since we can write
BipartiteEstimator(Lsub , k, δ)
wt(Lsub )
BipartiteEstimator(Lsub , k, δ)
=
·
,
wt(Lref ) − wt(Llight )
wt(Lref ) − wt(Llight )
wt(Lsub )
using (5.11) and (5.12), we get that
(1−δ)(1−4δ logd k e e(Lsub )) ≤
2

BipartiteEstimator(Lsub , k, δ)
≤ (1 +δ)(1 +4δ logd k e e(Lsub )) (5.13)
2
wt(Lref ) − wt(Llight )

Since BipartiteEstimator(L, k, δ) = wt(Llight ) +BipartiteEstimator(Lsub , k, δ), using (5.13) we get that
(1 − δ)(1 − 4δ logd k e e(Lsub )) ≤
2

BipartiteEstimator(L, k, δ)
≤ (1 + δ)(1 + 4δ logd k e e(Lsub )). (5.14)
2
wt(Lref )

Equation (5.14) in combination with (5.6) lets us conclude that
(1 − δ)2 (1 − 4δ logd k e e(Lsub )) ≤
2

BipartiteEstimator(L, k, δ)
≤ (1 + δ)2 (1 + 4δ logd k e e(Lsub )) (5.15)
2
wt(L)

Note (1+x)2 (1+y) ≤ 1+4x+y when 0 ≤ x, y ≤ 41 . Also, e(Lsub ) ≤
1
4 32 log
n

log(n2 ) ≤

1
4.

2
k ·e(L),

and 4δ logd k e e(Lsub ) ≤
2

Hence, we can upper bound the right hand side in (5.15) by


1+4δ+4δ logd k e e(Lsub ) = 1+4δ(1+logd k e (e(Lsub ))) ≤ 1+4δ logd k e
2

2

2

k
· e(Lref )
2

Similarly, since (1 − x)2 (1 − y) ≥ 1 − 4x − y for 0 ≤ x, y ≤ 14 , we get that
1 − 4δ logd k e (e(L)) ≤ (1 − δ)2 (1 − 4δ logd k e e(Lsub )),
2

2

which completes the proof of item (a) in the statement of the claim.
23


≤ 1+4δ logd k e e(L).
2

We now analyze the total number of BIS queries made. Steps 2-4 of the algorithm make at
most |Lref | · cce log3 n ≤ 2cce kt log4 n queries. In Step 7 of the algorithm, the total number of queries
made is at most 5e(Llight ) log n + 2. Using (5.9), |Llight | ≤ 2kt log n, and the definition of Llight , we
have
X
X
ee(A, B) · 8 log n ≤ |Llight | · s · 64 log2 n ≤ 128kst log3 n.
e(A, B) ≤
e(Llight ) =
(A,B,w)∈Llight

(A,B,w)∈Llight

Therefore, the number of BIS queries made in Step 7 is at most
128kst log3 n · 5 log n + 2 ≤ 210 kst log4 n.
The number of queries in Steps 2-4 and Step 7 is at most cbp kst log4 n, where cbp = 2cce + 210 . The
induction hypothesis implies that Step 18 makes at most cbp kst log4 n · logd k e e(Lsub ) BIS queries.
2
In total, the algorithm makes at most
cbp kst log4 n(1 + logd k e e(Lsub ))) ≤ cbp kst log4 n logd k e e(L),
2

2

BIS queries, where the last inequality used that e(Lsub ) ≤ k2 · e(L).
We have proven that the inductive guarantees in the statement of the claim holds when the
event B ∩ D ∩ E occurs. Since
P[B] ≤

4kt log n · logd k e e(Lsub )
8kt log2 n + 2t log n
2 log n
2
,
P[D|B]
≤
,
and
P[E]
≤
,
n4
n4
n4

we can bound that
P[B ∩ D ∩ E] ≥ 1 − P[B] − P[B ∩ D] − P[E] ≥ 1 − P[B] − P[D|B] − P[E]
2
8kt log2 n + 2t log n 2 log n 16kt log n · logd k2 e e(Lsub )
≥1−
−
−
n4
n4
n4
2
16kt log2 n · logd k e e(L)
16kt log n · (1 + logd k e e(Lsub ))
2
2
≥1−
,
≥1−
n4
n4

where we once again used that e(Lsub ) ≤

6

2
k

· e(L). This finishes the proof of the claim.

Edge Estimation using IS Queries

In this section we prove Theorem 1.3. We describe and analyze two algorithms, which we will
√
eventually combine. Algorithm 6 uses m · polylog(n)/ε IS queries and employs the sparsification
(Lemma 4.1) and exact edge counting (Lemma 2.4) results developed earlier. Algorithm 8 takes a
2
simple edge sampling approach and uses n ·polylog(n)
IS queries. To get the overall IS algorithm, we
ε2 ·m
run both algorithms in parallel and output the estimate of the algorithm that terminates earliest.
Thus, by combining the two approaches, we can find m
e satisfying (1 − ε)m ≤ m
e ≤ (1 + ε)m using
 2 √ 
n
m
min 2 ,
· polylog(n)
ε m
ε
IS queries. Notice that this is n2/3 polylog(n)/ε4/3 IS queries in the worst case for any graph.
We move on to describe the first algorithm.
24

Algorithm 6: EdgeEstimatorIS(n, ε)
Input: (n, ε): n is the number of vertices, and ε is an error parameter.
Output: Estimate m
e for the number of edges m = |E|.
1

In parallel for e
k = 2j with 1 ≤ 2j ≤ bn/2c do
m
e ek = ColorCountIS(n, e
k)
j
k
εe
k
∗
Set k = 18 log4 n

2
3
4
5
6

Terminate the whole parallel for loop when the earliest iteration finishes.
end
return m
e = ColorCountIS(n, k ∗ ).

Algorithm 7: ColorCountIS(n, k)
Input: (n, k): n is the number of vertices, and k is the number of colors.
Output: Estimate m
e for the number of edges m = |E|.
1
2

Partition the vertices into 2k color classes A1 , . . . , A2k uniformly at random.
k
X
Exactly compute m
e =
e(Ai , Ak+i ) using the algorithm from Lemma 2.4.
i=1

3

return 2k · m.
e

6.1

Sparsification-based IS Algorithm

Algorithm 6 provides the following guarantees.
Lemma 6.1. For any ε, m > 0 with ε ≥

324√log4 n
,
m

Algorithm 6 outputs m
e satisfying

(1 − ε)m ≤ m
e ≤ (1 + ε)m
and uses at most O

√

m·log7 n
ε



IS queries with probability at least 1 −

1
.
n3

Proof. We first argue that the number of color classes k ∗ from Step 3 in Algorithm 6 satisfies
√
√
ε m
ε m
∗
≤k ≤
(6.1)
18 log n
324 log5 n
with high probability. Then, we will argue that total number of IS queries is at most
√

m · log7 n
O
ε

(6.2)

also with high probability. Finally, we will argue that, with high probability, the output m
e satisfies




18k ∗ log n
18k ∗ log n
√
√
·m ≤ m
e ≤ 1+
· m,
(6.3)
1−
m
m
implying (1 − ε)m ≤ m
e ≤ (1 + ε)m because of (6.1). Together, these bounds prove the lemma.

25

To prove (6.1), we claim that with high probability the earliest iteration to terminate is at a
value e
k satisfying

 √
√

m
≤e
k≤
m · log3 n .
(6.4)
18 log n
Notice that definition of k ∗ in terms of e
k from Step 3 of EdgeEstimatorIS will then imply (6.1). Let
A1 , . . . , A2ek be the random partition of vertices in ColorCountIS(n, e
k). For any value e
k, let qek be
e
e
the number of queries used by ColorCountIS(n, k). Let E be the event that for each k we have
qek ≥

e
k
X
e(Ai , Aek+i ) + 1
i=1

and also


qek ≤ ce
k + log2 (n) ·

2

e
k
X

k
e
k 1X
= +
e(Ai , Aek+i ),
2 2
e

(6.5)

i=1

e(Ai , Aek+i ) + log2 (n) ·

i=1

2e
k
X


e(Ai ),

(6.6)

i=1

where c > 1 is a constant satisfying Lemma 2.4. Observe that ColorCountIS(n, e
k) invokes the
e
algorithm from Lemma 2.4 at most 3k ≤ 3n/2 times, and there are at most log n values of e
k to
consider. Therefore, Lemma 2.4 implies P[E] ≥ 1 − n−4 .
Now, let Ee be the event that for every call to ColorCountIS(n, e
k) during the the loop of the
EdgeEstimatorIS algorithm the following two conditions hold:
k

√
m X 
−
e Ai , Aek+i ≤ 9 m · log n
2e
k

2e
k

e

and

√
m X
−
e(Ai ) ≤ 9 m · log n.
2e
k
i=1

i=1

When E ∩ Ee holds, we have that for every value of e
k the number of queries qek satisfies




e
m
9√
m log2 n √
k
+ m · log3 n .
+ max 0,
−
m · log n ≤ qek ≤ 18c · e
k+
e
2
k
4e
k 2

(6.7)

e
Note that qek is minimized at a value e
k satisfying (6.4). Thus, k ∗ satisfies (6.1) conditioned on E.
∗
Also, our assumption on ε implies k ≥ 1. Finally, Lemma 4.1 and a union bound imply that
e ≥1−
P[E]

log n
.
n4

We now prove that the total number of IS queries is bounded by (6.2). Let E ∗ be the event that
during the call to ColorCountIS(n, k ∗ ) in Step 6 of EdgeEstimatorIS the algorithm from Lemma 2.4
uses a number of queries qk∗ satisfying (6.6), and also the following holds
∗

2k∗

k
X
√
m
−
e(Ai , Ak∗ +i ) ≤ 9 m · log n
∗
2k

and

i=1

√
m X
−
e(Ai ) ≤ 9 m · log n.
∗
k
i=1

Note that P[E ∗ ] ≥ 1 − n24 by Lemmas 2.4 and 4.1. When E ∩ Ee ∩ E ∗ happens, then (6.1) holds and
also the number of queries used by ColorCountIS(n, k ∗ ) is bounded by


√

m log2 n √
m · log7 n
∗
3
O k +
+ m · log n = O
.
k∗
ε
26

Now, consider the number of queries used by ColorCountIS(n, e
k) prior to the parallel loop tere
mination. Since the loop terminates at a value k satisfying (6.4), the number of queries used by
√
each call to ColorCountIS(n, e
k) is O( m · log3 n) prior to the loop termination, by (6.7). Thus, this
√
loop with O(log n) iterations contributes O( m · log4 n) queries in aggregate. Overall, the number
of queries is bounded by (6.2) conditioned on E ∩ Ee ∩ E ∗ .
ToP
prove (6.3), we again condition on E ∩ Ee ∩ E ∗ , so the value k ∗ satisfies (6.1). The number of
∗
edges ki=1 e(Ai , Ak∗ +i ) is calculated exactly. Since E ∗ bounds the accuracy of this sum, we have
that m satisfies (6.3). Our assumption on k ∗ implies (1 − ε)m ≤ m
e ≤ (1 + ε)m, as desired.

6.2

Edge Existence Queries

 2 2 
n
edge existence queries. Recall
Here we analyze Algorithm 8, which estimates m using O n εlog
2m
that we can directly simulate an edge existence query with an IS query.
We start with a technical lemma.
Algorithm 8: EdgeExistEstimator(n, ε)
Input: (n, ε): n is the number of vertices and ε is an error parameter.
Output: Estimate m
e for the number of edges m = |E|.
1
2
3
4
5
6
7

Set t = d(200/ε2 ) · ln ne.
l
m
for j = log(1+ε/4) n2 , . . . , 1, 0 do
j
Set m
e =(1 + ε/4)
 .
n
t
Set s = 2 · m
e .
Sample s unordered pairs {u, v} ⊆ [n] uniformly at random.
If at least t of these are edges in E, then return m
e and terminate.
end

Lemma 6.2. Assume 0 < ε ≤ 1/2. Set t = d(200/ε2 ) · ln ne. Given m,
e define
&  '
n
2 ·t
s := s(n, m,
e ε) =
m
e
Sample s uniformly random pairsP
of vertices. For i = 1, 2, . . . , s, let Xi indicate whether the ith
sample is an edge in G. Let X = si=1 Xi .
(a) When (1 − ε)m ≤ m
e ≤ (1 − 2ε )m, then X ≥ t with probability at least 1 − n−4 .
(b) When m
e ≥ (1 + ε)m, then X ≥ t with probability at most n−4 .
Proof. Define µ = E[X]. The definition of s implies that

m
m
e

·t≤µ≤

m
m
e

·t+

1

(n2 )

.

(a) In this case the assumption on m implies that

ε
m
(1 − ε)m ≤ m
e ≤ 1−
m<
,
2
(1 + ε/2)
where the final inequality follows since ε > 0. Hence, 2 · t ≥ µ ≥ (1 + 2ε ) · t, since ε ≤ 1/2. We
claim that
27

Thus, by a Chernoff bound (Lemma B.1(b)),
P[X ≤ t] ≤ P[X ≤ µ − (ε/2)t] ≤ P[X ≤ µ · (1 − ε/4)] ≤ e−ε

2 µ/48

.

Since µ ≥ t ≥ (200/ε2 ) · ln n, we have that X > t with probability at least 1 − n−4 .
(b) By our assumption in this case, µ ≤ t/(1 + ε) ≤ t(1 − ε/2). We claim that
P[X ≥ (1 − ε/4)t] ≤ P[X ≥ µ + εt/4] ≤ e−ε

2 t/48

.

(6.8)

Since t = (200/ε2 ) · ln n, we have that X > t with probability at least 1 − n−4 . To prove
that (6.8) holds, we consider two cases. If εt/4 ≤ µ, then we are concerned about the event
X ≥ (1 + δ)µ, where δ = εt/(4µ) satisfies 1 ≥ δ ≥ ε/4, since µ ≤ t. Lemma B.1(b) implies
P[X ≥ µ + εt/4] = P[X ≥ µ(1 + δ)] < e−δ

2 µ/3

< e−ε

2 t/48

.

2 t/48

If εt/4 > µ, then Lemma B.1(c) implies P[X ≥ µ + εt/4] < e−εt/12 < e−ε

.

We now analyze Algorithm 8.
Lemma 6.3. For every ε, m > 0 with 1/2 ≥ ε ≥ m−1/2 , Algorithm 8 uses O



and returns m
e such that (1 − ε)m ≤ m
e ≤ (1 + ε)m with probability at least 1 −



n2 ·log n
IS
ε2 ·m
polylog(n)
.
n2

queries

Proof. During any iteration j with (1 − ε)m ≤ (1 + ε/4)j ≤ (1 + ε)m, if the algorithm terminates,
then the m
e it outputs will satisfy (1 − ε)m ≤ m
e ≤ (1 + ε)m. We argue that with high probability
such an iteration exists and the algorithm will not output an estimate out of the desired range.
∗
Let j ∗ be a value achieving (1 − ε)m ≤ (1 + 4ε )j ≤ (1 − 2ε )m. Such a value exists since 4 ≤
e ≤ (1 + ε)m
ε−2 ≤ m ≤ n2 . By Lemma 6.2, the algorithm will terminate and output (1 − ε)m ≤ m
during iteration j ∗ with probability at least 1 − n−4 . Due to the setting of j ∗ and the number of
samples s∗ for this iteration, the number of IS queries will be
 2

n · log n
∗
s =O
ε2 · m
0

Consider any iteration j 0 such that (1 + ε/4)j > (1 + ε)m. In this case, the algorithm will see
fewer than T edges with probability at least 1 − n−4 by Lemma 6.2. Thus, it will not terminate or
output any estimate during iteration j 0 , and this iteration uses at most s∗ queries.

 2
n
The number of iterations in Algorithm 8 is O(log(n)/ log(1 + ε)), each of which uses O n ε·log
2 ·m
 2 2 
n ·log n
using the approximation log(1 + ε) ≈ ε. To
queries, naively leading to a bound of O ε3 ·m
avoid the extra log(n)/ε factor, we use a standard geometric search trick (for example, see [HR15],
Theorem 3.3.2). We iteratively estimate m up to a factor of εi , where εi = ε2i−1 and ε1 = 1/2.
2
Since the number of samples
 scales
 with 1/εi , the total number of queries will be a geometric series
2

n
with dominating term O n ε·log
as desired.
2 ·m
Putting everything together, and taking a union bound over all iterations,
we
 2
 conclude that
polylog(n)
n log n
with probability at least 1 −
, the algorithm terminates, uses O ε2 m
IS queries, and
n2
outputs m
e satisfying (1 − ε)m ≤ m
e ≤ (1 + ε)m.

28

6.3

Overall IS Algorithm (Proof of Theorem 1.3)

Wrapping together Algorithms 6 and 8 will finish the proof of Theorem 1.3. Consider an input
4
n
. We will simultaneously run
graph G = ([n], E) and an error parameter 1/2 ≥ ε ≥ 324√log
m
Algorithms 6 and 8, synchronizing the IS query calls so that at every step, they each have used the
same total number of queries. Let m
e be the output of the algorithm that terminates first. We will
terminate the other algorithm and use m
e as the final output. By combining Lemmas 6.1 and 6.3,
we see that with probability at least 1 − polylog(n)
, the total number of queries is at most
n2

min

n2
,
ε2 m

√ 
m
· polylog(n)
ε

and (1 − ε)m ≤ m
e ≤ (1 + ε)m as desired. This completes the proof of Theorem 1.3.

6.4

Limitations of IS Queries

In this section, we discuss several ways in which IS queries seem more restricted than BIS queries.
Simulating Degree Queries with IS queries. A degree query can be simulated by O(log n)
BIS queries
 (see
 Appendix A for a proof sketch). In contrast, here we provide a graph instance
n
where Ω deg(v) IS queries are needed to simulate a degree query. In fact, we show that IS queries
may be no better
than
 edge existence queries for the task of degree estimation. Since it is easy

n
to see that Ω deg(v) edge existence queries are needed to estimate deg(v), this lower bound also
applies to IS queries.
For the lower bound instance, consider a graph which is a clique along with a separate vertex v
whose neighbors are a subset of the clique. We claim that IS queries involving v are essentially
equivalent to edge existence queries. Any edge existence query can be simulated by an IS query.
On the other hand, any IS query on the union of v and at least two clique vertices will always
detect a clique edge. Thus, the only informative IS queries involve exactly two vertices.
Coarse Estimator with IS queries. It is natural to wonder if it is possible to replace the
coarse estimator (Lemma 2.3) with an analogous algorithm that makes polylog(n) IS queries. This
would immediately imply an algorithm making polylog(n)/ε4 IS queries that estimates the number
of edges. We do not know if this is possible, but one barrier is a graph consisting of a clique A on
√
√
O( m) vertices along with a set B of n − O( m) isolated vertices. We claim that for this graph,
the algorithm CoarseEstimator(A, B) from Section 5.1, using IS queries instead of BIS queries,
will output an estimate m
e that differs from m by a factor of Θ(n1/3 ). Consider the execution of
CheckEstimate((A, B), ee) from Algorithm 1. A natural way to simulate this with IS queries would
be simply to use an IS query on A0 ∪ B 0 instead of a BIS query on (A0 , B 0 ). Assume for the sake of
√
argument that m = n4/3 and |A| = m = n2/3 . Consider when the estimate ee satisfies ee = cn5/3
for a small constant c. In the CheckEstimate execution, there will be a value i = Θ(log n) such that,
with constant probability, A0 ⊆ A will contain at least two vertices and B 0 ⊆ B will contain at least
one vertex. In this case, e(A0 ∪ B 0 ) 6= 0 even though e(A0 , B 0 ) = 0. Thus, using IS queries will lead
to incorrectly accepting on such a sample, and this would lead to the CoarseEstimator outputting
the estimate ee = Θ(n5/3 ) even though the true number of edges is m = n4/3 .

29

7

Conclusion

In this paper, we studied the task of using either BIS or IS queries to estimate the number of edges in
a graph. We presented randomized algorithms giving a (1 + ε)-approximation using polylog(n)/ε4
√
BIS queries and min n2 /(ε2 m), m/ε · polylog(n) IS queries. Our algorithms estimated the
number of edges by first sparsifying the original graph and then exactly counting edges spanning
certain bipartite subgraphs. Below we describe a few open directions for future research.

7.1

Open Directions

An obvious unresolved question is whether there is an algorithm to estimate the number of edges
√
√
with o( m) IS queries when m = o(n4/3 ). In this context proving a lower bound of Ω( m) IS
queries would also be very interesting. The arguments in Section 6.4 lend some support to the
possibility that a non-trivial lower bound might hold for the case of IS queries.
Other open questions include using a polylogarithmic number of BIS queries to estimate the
number of cliques in a graph (see [ERS17] for an algorithm using degree, neighbor and edge existence queries) or to sample a uniformly random edge (see [ER17] for an algorithm using degree,
neighbor and edge existence queries). In general, any graph estimation problems may benefit from
BIS or IS queries, possibly in combination with standard queries (such as neighbor queries). Finally, it would be interesting to know what other oracles, besides subset queries, enable estimating
the number of edges (or other graph parameters) with a polylogarithmic number of queries.
Acknowledgments. We thank anonymous referees for helpful comments about improving the
presentation of our paper and for pointing out relevant references.

References
[AH08]

B. Aronov and S. Har-Peled. On Approximating the Depth and Related Problems.
SIAM J. Comput., 38(3):899–921, 2008.

[BKKR13] Ido Ben-Eliezer, Tali Kaufman, Michael Krivelevich, and Dana Ron. Comparing the
strength of query types in property testing: The case of k-colorability. Computational
Complexity, 22(1):89–135, 2013.
[CJ15]

Sergio Cabello and Miha Jejčič. Shortest paths in intersection graphs of unit disks.
Computational Geometry, 48(4):360–367, 2015.

[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.

[DL17]

Holger Dell and John Lapinskas. Fine-grained reductions from approximate counting
to decision. CoRR, abs/1707.04609, 2017.

[Dor43]

Robert Dorfman. The Detection of Defective Members of Large Populations. The
Annals of Mathematical Statistics, 14(4):436–440, 1943.

[DP09]

Devdatt P Dubhashi and Alessandro Panconesi. Concentration of Measure for the
Analysis of Randomized Algorithms. Cambridge University Press, 2009.

30

[ELRS15] Talya Eden, Amit Levi, Dana Ron, and C. Seshadhri. Approximately counting triangles
in sublinear time. In Venkatesan Guruswami, editor, FOCS, pages 614–633. IEEE
Computer Society, 2015.
[ER17]

Talya Eden and Will Rosenbaum. On Sampling Edges Almost Uniformly. arXiv preprint
arXiv:1706.09748, 2017.

[ERS17]

T. Eden, D. Ron, and C. Seshadhri. On Approximating the Number of k-cliques in
Sublinear Time. ArXiv e-prints, July 2017.

[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.

[FJO+ 16] Moein Falahatgar, Ashkan Jafarpour, Alon Orlitsky, Venkatadheeraj Pichapati, and
Ananda Theertha Suresh. Estimating the number of defectives with group testing. In
ISIT, pages 1376–1380. IEEE, 2016.
[GR08]

Oded Goldreich and Dana Ron. Approximating average parameters of graphs. Random
Structures & Algorithms, 32(4):473–493, 2008.

[GRS11]

Mira Gonen, Dana Ron, and Yuval Shavitt. Counting stars and other small subgraphs
in sublinear-time. SIAM J. Discrete Math, 25(3):1365–1411, 2011.

[HR15]

Sariel Har-Peled and Benjamin Raichel. Net and Prune: A Linear Time Algorithm for
Euclidean Distance Problems. Journal of the ACM (JACM), 62(6):44, 2015.

[KZC+ 05] Robert J Klein, Caroline Zeiss, Emily Y Chew, Jen-Yue Tsai, Richard S Sackler, Chad
Haynes, Alice K Henning, John Paul SanGiovanni, Shrikant M Mane, Susan T Mayne,
et al. Complement factor h polymorphism in age-related macular degeneration. Science,
308(5720):385–389, 2005.
[ORRR11] Krzysztof Onak, Dana Ron, Michal Rosen, and Ronitt Rubinfeld. A near-optimal
sublinear-time algorithm for approximating the minimum vertex cover size. CoRR,
abs/1110.1079, 2011.
[RT14]

Dana Ron and Gilad Tsur. The power of an example: Hidden set size approximation
using group queries and conditional sampling. CoRR, abs/1404.5568, 2014.

[Ses15]

C. Seshadhri. A simpler sublinear algorithm for approximating the triangle count. ArXiv
e-prints, May 2015.

[Sto83]

Larry Stockmeyer. The complexity of approximate counting (preliminary version). In
Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, pages
118–126, Boston, Massachusetts, 25–27 April 1983.

[Sto85]

Larry Stockmeyer. On approximation algorithms for #P. SICOMP: SIAM Journal on
Computing, 14, 1985.

[Swa85]

William H Swallow. Group Testing for Estimating Infection Rates and Probabilities of
Disease Transmission. Phytopathology (USA), 1985.
31

[WLY13]

A

Jianguo Wang, Eric Lo, and Man Lung Yiu. Identifying the most connected vertices
in hidden bipartite graphs using group testing. IEEE Transactions on Knowledge and
Data Engineering, 25(10):2245–2256, 2013.

Simulating Degree Queries Using BIS Queries

For any vertex v, using polylog(n)
BIS queries we can output an estimate de satisfying (1−ε) deg(v) ≤
ε2
de ≤ (1 + ε) deg(v) with high probability. To sketch the algorithm, we first recall Lemma 2.1 which
gives us a deterministic algorithm that exactly computes e(A, B) using O(e(A, B) log n) BIS queries
for any disjoint subsets A, B ⊆ [n].
The algorithm for estimating deg(v) iteratively guesses de = n/(1 + ε)i for i = 0, . . . , log(1+ε) n.
To verify the guess de the algorithm samples t = O(log n/ε2 ) random subsets of [n] \ {v} by choosing
each vertex with probability 1/de and checks if there are Ω(t) edges (including duplicates) present
between the vertex v and the random subsets drawn. We can exactly count the number of sampled
edges with O(t log n) = polylog(n)
BIS queries using the aforementioned algorithm from Lemma 2.1.
ε2

B

Concentration Bounds

For proofs of the following concentration bounds, see the book by Dubhashi and Panconesi [DP09].
Lemma B.1
P(Chernoff Bounds). Let X1 , . . . , Xr be r i.i.d. random variables with 0 ≤ Xi ≤ 1 and
define X = ri=1 Xi . For µ = E[X], let µl and µu be real numbers such that µl ≤ µ ≤ µu .
(a) For any s > 0, we have P[X ≤ µl − s] ≤ e−2s

2 /r

and P[X ≥ µu + s] ≤ e−2s

(b) For any 0 ≤ δ < 1, we have P[X ≤ (1 − δ)µl ] ≤ e−
(c) For any δ ≥ 1, we have P[X ≥ (1 + δ)µu ] ≤ e−

µu ·δ
3

µl ·δ 2
2

2 /r

.

and P[X ≥ (1 + δ)µu ] ≤ e−

µu ·δ 2
3

.

.

Lemma B.2 (Hoeffding’s inequality). Let X1 , . . . , Xr be r independent random variables, where
Xi ∈ [ai , bi ], for i ∈ [r]. Then, for the random variable X = X1 + · · · + Xr and any s > 0, we have


2 s2
.
P[|X − E[X]| ≥ s] ≤ 2 exp − Pr
2
i=1 (bi − ai )
Lemma B.3 (Importance Sampling). Let U = {x1 , . . . , xr } be a set of numbers, all contained
in
P
the interval [ αb , αb], for α > 0 and b ≥ 1. Let γ > 0 be a parameter. Consider the sum Γ = ri=1 xi .
Let Xi be a random sample chosen uniformly (and independently) from the
 set U , for i = 1, . . . , t,
Pt
b4
and consider the estimate Y = (r/t) i=1 Xi for Γ. Then, for t ≥ 2ε2 1 + ln γ1 , we have that
P[|Y − Γ| ≥ εΓ] ≤ γ.
Proof. Observe that
µ = E[Y ] = E[(r/t)

t
X

Xi ] = (r/t)

i=1

t
X
i=1

32

E[Xi ] =

r
Γ
· t · = Γ.
t
r

We have that Γ ∈ [ αr
b , αrb], and as such, by Lemma B.2, we have
!


i
t
2 (tεΓ/r)2 b2
t
tεΓ
P |Y − Γ| ≥ εΓ = P
≤ 2 exp −
Y − Γ ≥
2
r
r
r
t (b2 − 1)α






2tε2 Γ2
2tε2 α2 r2
2tε2
≤ 2 exp − 2 2 2 ≤ 2 exp − 2 4 2
= 2 exp − 4
≤ γ.
r b α
r b α
b
h

We will need the following version of Azuma’s that takes into account rare bad events.
Lemma B.4. Let f be a function of r random variables X1 , . . . , Xr such that f (X1 , . . . , Xr ) ≤ b.
Let B be any event and let for i ∈ [r] let ci satisfy
E[f | X1 , . . . , Xi−1 , Xi = ai , B̄] − E[f | X1 , . . . , Xi−1 , Xi = a0i , B̄] ≤ ci .
Then for any s > 0, we have that

2s2
P [|f − E[f ]| > s + b · P(B)] ≤ exp − Pr

2
i=1 ci

33


+ P[B]

