Abstract 1 Introduction 2 Technical overview 3 Threshold checking 4 Sparsification 5 Full algorithm References Appendix A Concentration Inequalities

From Decision to Random Certificates: Exponential Separation for Edge Estimation with Independent Set Queries

Debarshi Chanda ORCID Indian Statistical Institute, Kolkata, India    Buddha Dev Das ORCID Indian Statistical Institute, Kolkata, India    Arijit Ghosh ORCID Indian Statistical Institute, Kolkata, India    Gopinath Mishra ORCID Institute of Mathematical Sciences, Chennai, India
Abstract

We study the problem of estimating the number of edges in an undirected, unweighted graph using sublinear query access. We consider a query model that preserves the structure of Independent Set (IS) queries, but augments their output with a random certificate: given a vertex subset, the oracle returns a uniformly random edge from the induced subgraph if one exists, and returns null otherwise.

Using this access, we give a randomized algorithm that outputs a (1±ε)-approximation to the number of edges with constant success probability using O~⁢(log2⁡m) queries. This implies an exponential separation from both standard IS queries and global random edge-sampling models: estimating the number of edges using standard IS queries require Θ~⁢(min⁡{m,nm}) queries, while direct random edge-sample access requires Θ~⁢(m) samples. Beyond separation in query complexity, our algorithm is output-sensitive: its query complexity is polylogarithmic in the number of edges in the graph. This aligns with the classical objective in group testing, where one seeks algorithms that are both worst-case optimal and instance-adaptive.

Conceptually, our model connects group testing, the decision–versus–counting dichotomy, graph property testing, and the “power of a random certificate”, and can be viewed as a structured form of conditional sampling of edges in graphs.

Keywords and phrases:
Property Testing, Edge Estimation
Category:
RANDOM
Funding:
Arijit Ghosh: Arijit Ghosh acknowledges partial support from the Science and Engineering Research Board (SERB), Government of India, through the MATRICS grant MTR/2023/001527, and from the Department of Science and Technology (DST), Government of India, through grant TPN-104427.
Copyright and License:
[Uncaptioned image] © Debarshi Chanda, Buddha Dev Das, Arijit Ghosh, and Gopinath Mishra; licensed under Creative Commons License CC-BY 4.0
2012 ACM Subject Classification:
Theory of computation → Streaming, sublinear and near linear time algorithms
Related Version:
Full Version: https://arxiv.org/abs/2607.07483 [20]
Acknowledgements:
We thank an anonymous reviewer for their suggestions in improving the query complexity from log3⁡m (in an earlier version) to log2⁡m.
Editors:
Mohit Singh and Tom Gur

1 Introduction

We consider the problem of estimating the number of edges in an undirected, unweighted, simple graph using a sublinear number of queries. Let G=(V,E) be a graph with V=[n]:={1,2,…,n} vertices and |E|=m edges. Given query access to G and an approximation parameter ε∈(0,1), the objective is to output an estimate m^ such that

(1−ε)⁢m≤m^≤(1+ε)⁢m

with success probability at least 2/3.

Query model and our result

We work in a query model built on Independent Set (IS) queries, introduced by [6]. The IS query takes a subset of vertices U⊆V and returns whether U is an independent set.

We consider the Independent Set with Certificate query, denoted by ISC, which takes as input a subset of vertices U⊆V and returns

ISC⁢(U)={e∼Unif⁢(E⁢(U)),if ⁢E⁢(U)≠∅,0,otherwise,

where E⁢(U) denotes the set of edges in the subgraph of G induced by U, and Unif⁢(S) denotes the uniform distribution over a (nonempty) set S.

Importantly, the ISC query preserves the structural constraint of a standard IS query: the algorithm specifies exactly the same vertex subsets as in the IS model, and the only difference lies in the response, which returns a uniformly random edge as a certificate whenever the induced subgraph is nonempty.

[6] showed that the number of edges in a graph can be estimated using

O~⁢(min⁡{n2m,m})=O~⁢(n2/3)

IS queries, establishing a polynomial separation from local query based algorithms that require Θ⁢(n) queries in the worst case [27]. In a subsequent work, [21] nearly resolved the query complexity of edge estimation using IS queries by showing that

Θ~⁢(min⁡{nm,m})

queries are both necessary and sufficient. In particular, this implies a worst-case complexity of Θ~⁢(n) IS queries.

Our main result shows that the natural enrichment of IS queries with random certificates yields an exponential separation from standard IS queries for edge estimation, achieving polylogarithmic query complexity in m.

Theorem 1 (Main result).

There exists a randomized algorithm that, given access to a graph G through ISC queries and an approximation parameter ε∈(0,1/3), outputs an estimate m^ of the number of edges m in G such that, with probability at least 2/3,

(1−ε)⁢m≤m^≤(1+ε)⁢m.

The algorithm uses O⁢(ε−2⁢log2⁡m⋅log⁡log⁡m) ISC queries in expectation.

The query complexity of the algorithm is strictly output-sensitive in the sense that it depends only on the number of edges, with no dependence on n, even in lower-order terms.

Theorem 1 not only demonstrates the power gained by augmenting IS access with random certificates over standard IS access, but also underscores the strength of sampling within induced subgraphs. When edges can only be sampled uniformly at random from the entire graph, estimating the number of edges requires Θ~⁢(m) samples [30]. In contrast, allowing the algorithm to sample a uniformly random edge from a queried induced subgraph yields an exponential separation from global random edge-sampling, achieving query complexity O~⁢(log2⁡m).

In what follows, we highlight conceptual connections between our results and query model with several well-studied themes, including group testing, graph property testing, the power of random certificates, decision versus counting problems, and conditional sampling.

Group testing perspective

The introduction of IS queries in graph algorithms was originally motivated by ideas from group testing. In classical group testing, introduced by [25] and studied extensively since then, the goal is to infer the size of an unknown set of defective items by querying subsets of a known universe [3]. A standard group test returns only a binary result indicating whether the queried subset contains at least one defective item.

This viewpoint applies naturally to graph edge estimation. Here, edges play the role of defective items, and the allowed vertex pairs for queries impose structural constraints on the possible subsets of edges that can be queried. [6] introduced both IS and Bipartite Independent Set (BIS) queries through this lens. A BIS query takes two disjoint vertex sets as input and returns whether there exists an edge with one endpoint in each set.

In the same vein, [13] and [5] introduced the Edge Emptiness query EE to study triangle estimation and connectivity in graphs, respectively. An EE query specifies a set of candidate edges and reports whether at least one of them exists in the graph.

Decision versus counting

In a series of seminal works, [32, 33] studied the relationship between approximate counting and decision access for Boolean formulas. In particular, they showed that given decision access to satisfiability, one can approximately count the number of satisfying assignments of any Boolean formula on n variables using only O⁢(log⁡n) such queries.

Our work establishes an analogous phenomenon in the setting of graph edge estimation: augmenting decision-style IS queries with a random certificate enables efficient approximate counting of edges in a graph.

Conditional sampling

Our model also bears a close conceptual relationship to work on property testing and estimation with conditional sampling access. In distribution testing, a conditional sampling oracle [18, 16] allows the algorithm to specify a subset of the domain and receive a sample drawn from the distribution restricted to that subset. Such structured sampling can lead to exponential savings over standard sampling in tasks such as uniformity testing, support size estimation, and testing of joint distributions [15, 9, 14, 10].

In our setting, the ISC oracle plays an analogous role: the algorithm specifies a vertex subset, and if the induced subgraph is nonempty, it receives a uniformly random edge from that subgraph. Thus, ISC can be viewed as a structured conditional sampling primitive over the edge set of the graph, where the conditioning is constrained to induced subgraphs. Our results demonstrate that, as in distribution testing, such conditional access can fundamentally change the complexity of estimation problems in graphs.

Power of a random certificate

Studying the power of random certificates for approximate counting is an important question across a variety of query models [31, 17]. These works show that augmenting group queries with access to random certificates can lead to significant reductions in query complexity.

In the graph setting, several queries have been introduced from the viewpoint of group queries while retaining the structural properties of the graph. Two notable examples are IS and BIS, introduced by [6] for estimating the number of edges. Our ISC query fits naturally within this framework: it preserves the structure of IS while adding a random certificate. In particular, our algorithm achieves substantially lower query complexity compared to algorithms using only IS access, and also improves over the best known O~⁢(log5⁡n)-query algorithm based on BIS access due to [2].

The main difference between the power of random certificates studied in [31, 17] and our setting is that our query oracles are group graph queries that retain the structural properties of the underlying graph.

Graph property testing

Estimating the number of edges in a graph with sublinear queries has been studied in several access models. Early works focused on local queries such as degree, neighbour, and pair queries [28, 29, 27, 34], which provide fine-grained access but face inherent limits for edge estimation.

This led to models that incorporate global information. In particular, augmenting local access with random edge sampling [4, 26, 7] enables more efficient estimation. More recently, a finer-grained analysis of edge estimation under local queries enriched with random edge sampling have provided an understanding of the tradeoffs between local and global access [11, 12, 19, 7].

Another line of work studies structured global queries, notably IS and BIS [6, 21, 2]. These queries provide decision-only access over vertex subsets while preserving graph structure, and have been extended to hypergraphs [23, 8, 24]. We discussed their known upper and lower bounds earlier in the Introduction.

Finally, [1] showed that augmenting IS queries with additional local queries yields a quadratic separation from using IS queries alone, further illustrating the power of combining different query primitives. Other than the BIS query, all query models discussed above requires polynomial number of queries in the worst case.

Notations

Throughout, the notation O~⁢(f), suppress factors polynomial in 1/ε and log⁡f. For an integer k, we define [k]={1,…,k}. We write a=(1±ε)⁢b to indicate that a is a (1±ε)-approximation of b.

Throughout, we use G=(V,E) to denote the input graph with m=|E| number of edges and V=|V| vertices. For a subset U⊆V, let m⁢(U) be the number of edges in the graph induced by the subset U.

2 Technical overview

We give a high-level description of our algorithm for estimating the number of edges in an undirected graph using Independent Set with Certificate (ISC) queries. Conceptually, our approach converts approximate counting into a sequence of controlled decisions and sampling steps that gradually reduce the graph while preserving a constant fraction of its edges.

A central conceptual contribution is the use of approximation preserving subsets and approximation preserving sequences, which formalise how much of the graph’s edge mass is retained at each stage and guide both the algorithm and its analysis. We leverage graph sparsification techniques to enable iterative construction of approximation-preserving sequences on graphs using ISC queries.

Outline of the Algorithm

At a high level, our algorithm maintains a nested sequence of vertex subsets

V=U0⊇U1⊇⋯⊇Uκ,

where each Uj contains a constant fraction of the edges of Uj−1. The algorithm alternates between two modes:

  • ■

    If the current induced subgraph is “small” (that is, has fewer than τ edges), we estimate its edge count directly.

  • ■

    Otherwise, we construct a smaller approximation preserving subset of the graph by randomly partitioning the vertex set and selecting a part that provably retains a constant fraction of the edges.

This iterative reduction of the graph continues until we reach a subset Uκ whose edge count is small enough to estimate accurately; we set the threshold for Uκ to be a sufficiently large constant. The final estimate of m is then reconstructed by multiplying the relative edge losses across all steps.

Where the 𝑶~⁢(𝐥𝐨𝐠𝟐⁡𝒎) query complexity comes from

A key novelty of our approach is that all complexity bounds are driven by log⁡m rather than log⁡n. This is achieved through three ideas that are not present in prior IS or BIS based algorithms:

  • ■

    Random certificates enable output-sensitive sparsification: Unlike decision-only IS or BIS queries, ISC queries allow us to estimate how many edges of a subset lie in a randomly chosen part, which lets us iteratively construct smaller induced subgraphs to work on while tracking edge mass locally.

  • ■

    Approximation Preserving Sequence: Instead of estimating m directly, we construct a chain of subsets U0⊇U1⊇⋯⊇Uκ such that each Uj retains a constant fraction of edges of Uj−1. Crucially, we establish κ to be O⁢(log⁡m) in expectation, independent of n. We also bound the number of queries required to construct this sequence as O⁢(κ2) and bound its expectation.

  • ■

    Local multiplicative reconstruction: We only need to estimate the ratios pj=m⁢(Uj)m⁢(Uj−1), each of which is Ω⁢(1) due to the U0,…,Uκ being an approximation preserving subsequence. This keeps the per-level query complexity small and makes the overall cost in expectation O~⁢(κ2)=O~⁢(log2⁡m).

Estimating Small Edge Counts

Fix a threshold τ. One can design an algorithm that makes O⁢(τ) ISC queries and guarantees the following with desired probability about a given subset U⊆V. If m⁢(U)≤τ, then the algorithm reports an approximation of m⁢(U). Moreover, if m⁢(U)≥8⁢τ, the algorithm reports that m⁢(U) is large. The proof is based on the birthday paradox. The details can be found in Section 3.

Graph Sparsification

The idea here is to leverage graph sparsification to construct a smaller subset of vertices to work on at each step. We partition U uniformly at random into two subsets U1 and U2. A graph sparsification lemma, along the result of [6], shows that with desired probability,

|m⁢(U)2−∑i=12m⁢(Ui)|≤c⁢m⁢(U)⁢log⁡m⁢(U).

We provide the proof in Section 4. Intuitively, this means that the total number of edges inside U1 and U2 is close to half of m⁢(U), up to a lower-order error term. As long as m⁢(U) is sufficiently large, this implies that at least one of U1 or U2 must contain a constant fraction of the edges of U. More precisely, there exists an absolute constant ζsp such that if m⁢(U)≥ζsp, then with probability at least 1−1/m⁢(U), at least one of m⁢(U1)/m⁢(U) and m⁢(U2)/m⁢(U) is at least 1/8, and both m⁢(U1)/m⁢(U) and m⁢(U2)/m⁢(U) are at most 3/4.

Choosing the Good Part

After partitioning U into U1 and U2, we must identify which part retains an appropriate fraction of the edges. Note that this step is fundamentally enabled by the ISC queries. The idea is to take a random sample of the edges in U, and check whether it is preserved in the induced subgraph of either U1 or U2.

To do this, we draw random edges from U via ISC queries. Let p^⁢(Ui) be the fraction of sampled edges that fall inside Ui, for i∈[2]. If p^⁢(Ui)≥1/16, we select Ui as the next subset; otherwise, we pick an arbitrary part. A Chernoff bound guarantees that, with desired probability, we correctly identify a subset satisfying

132≤m⁢(Ui)m⁢(U)≤34.

Such subsets are called approximation preserving subsets. The upper bound of 3/4 is useful to bound the final query complexity and the lower bound of 1/32 is useful for guaranteeing the quality of the estimator.

Constructing an Approximation Preserving Sequence

Starting with U0=V, we iterate:

  1. 1.

    Run threshold checking on Uj.

  2. 2.

    If m⁢(Uj)<τ, stop and set Uκ=Uj.

  3. 3.

    Otherwise, sparsify Uj and select an approximation preserving subset Uj+1.

This yields a sequence V=U0⊇U1⊇⋯⊇Uκ, where, with probability at least 4/5, each Uj satisfies

132≤m⁢(Uj)m⁢(Uj−1)≤34.

Final Estimation

For each j∈[κ], define

pj=m⁢(Uj)m⁢(Uj−1).

Then we have the identity

m=m⁢(Uκ)∏j=1κpj.

Instead of estimating each m⁢(Uj) from scratch, we estimate only the ratios pj. Because each pj=Ω⁢(1) by construction of the approximation preserving sequence, we can estimate each pj using small number of queries, independent of n or m⁢(Uj). This yields an estimate p^j satisfying the following with desired probability.

p^j=(1±ε/O⁢(κ))⁢pj

Note that the entire approximation preserving subsequence is constructed a priori. Hence, we know κ during the final estimation phase that we use to fix the approximation parameters appropriately for the multiplicative estimation for each pj,j∈[κ]. Let m^⁢(Uκ) be the estimate obtained via the birthday-based estimator. Our final output is

m^=m^⁢(Uκ)∏j=1κp^j.

A careful multiplicative error analysis shows that this is a (1±ε)-approximation to m.

Proof Roadmap

The correctness proof proceeds in the following stages:

  • ■

    Threshold correctness: We show that the collision-based test reliably distinguishes between m⁢(U)<τ and m⁢(U)≥8⁢τ, and that the birthday-paradox estimator is accurate when m⁢(U)<τ.

  • ■

    Constructing approximation preserving subsequence: While we decrease the failure probability of choosing a good subset at each iteration, the probability of failure of the sparsification step depends on the number of edges remaining. This necessitates a careful analysis of the failure probability of the sparsification step and of our threshold-checking mechanisms to establish the correctness of our algorithm and query complexity bounds.

  • ■

    Multiplicative reconstruction: Given our approximation preserving subsequence, we estimate each pj with appropriately scaled approximation error. Then, we bound the cumulative error from estimating all pj and show that the product estimator preserves a global (1±ε) approximation.

  • ■

    Complexity analysis: We show that 𝔼⁢[κ]=O⁢(log⁡m) and that the total query complexity is dominated by estimating the pj’s, yielding an overall expected complexity of O~⁢(log2⁡m/ε2).

Outline

We begin in Section 3, where we present the threshold-checking algorithm and show how to estimate the edge count when the number of edges is below a given threshold. In Section 4, we describe the algorithm for constructing an approximation-preserving subsequence. In Section 4.1, we establish how graph sparsification yields an approximation-preserving subset, and use this result in Section 4.2 to construct an approximation-preserving subsequence. Finally, in Section 5, we present the complete algorithm for edge estimation. Appendix A discusses some useful concentration inequalities.

3 Threshold checking

Let a fixed threshold (τ≥1) be given. We consider the following threshold-checking problem: given a subset of vertices U⊆V, determine whether m⁢(U)<τ. If this condition holds, the goal is to estimate the (1±ε) approximation of m⁢(U).

To address this task, we present two algorithms IsCollision and BirthdayEstimate based on the birthday paradox techniques [30, Chapter 5]. IsCollision distinguishes between the cases m⁢(U)<τ or m⁢(U)≥8⁢τ (Lemma 2). BirthdayEstimate outputs an (1±ε) approximation of m⁢(U), if m⁢(U)<τ (Lemma 3). The corresponding guarantees are stated below. For details, see the full version of the paper [20].

Lemma 2 (Correctness of IsCollision).

For a subset U⊆V and a threshold τ≥1, the following statements hold for IsCollision with probability at least 1−δ:

  1. (i)

    If m⁢(U)≤τ, then IsCollision outputs 1.

  2. (ii)

    If m⁢(U)≥8⁢τ, then IsCollision outputs 0.

The number of ISC queries made is O⁢(τ⁢log⁡(δ−1))

Suppose that a collision is detected, i.e., IsCollision outputs 1. We can obtain a (1±ε)-approximation of m⁢(U) using additional ISC queries. This estimation procedure is implemented in BirthdayEstimate.

Lemma 3 (Correctness of BirthdayEstimate).

For a subset U⊆V, threshold τ≥1 and approximation error ε>0. If m⁢(U)≤τ, then BirthdayEstimate outputs an (1±ε) estimate of m⁢(U) with probability at least 15/16. The number of ISC query made is Θ⁢(ε−1⁢τ).

4 Sparsification

In this section, we will describe a procedure to generate an approximation preserving sequence (formally defined below) U0,…,Uκ with probability at least 7/8. Moreover, the expected query complexity of the procedure is O⁢(log2⁡m).

Definition 4 (Approximation preserving subset).

For U,U′⊂V such that U′⊆U, we say that U′ is an approximation preserving subset of U if

132≤m⁢(U′)m⁢(U)≤34.
Definition 5 (Approximation preserving sequence).

For a sequence U0,U1,…,Uκ⊆V with U0⊇U1⊇…⊇Uκ, We say that U0,U1,…,Uκ is an approximation preserving sequence if Ui−1 is an approximation preserving subset of Ui for all i∈[κ].

Formally, we will prove the following lemma in this section.

Lemma 6 (Approximate sequence lemma).

There exists an algorithm that outputs an approximation preserving sequence U0,U1,…,Uκ with probability at least 4/5. The expected value of κ is O⁢(log⁡m), and the expected number of ISC queries made is O⁢(log2⁡m).

To prove the above lemma, we start with U0=V, and find Ui iteratively. Informally speaking, we stop with Uκ when m⁢(Uκ) is small enough. In Section 4.1, we discuss a procedure (ApproxSubset corresponding to Lemma 7) that generates a U′ which is an approximation preserving subset of U, with specified probability, for any given U as long as m⁢(U) is large. In Section 4.2, we describe the procedure (ApproxSequence corresponding to Lemma 12) that uses IsCollision and ApproxSubset iteratively to generate an approximation preserving subsequence U0,…,Uκ. Essentially, IsCollision is used to determine whether the number of edges in the current subset Ui is small or large and ApproxSubset is used to generate a good subset as long as m⁢(Ui) is large.

4.1 Procedure to find approximate preserving subset

In this section, we describe the procedure ApproxSubset (see Algorithm 1) for finding the approximation preserving subset U′⊆U, for any given U and prove its guarantee.

Algorithm 1 ApproxSubset(U,δ).

Formally, we will prove the following.

Lemma 7 (Approximate subset lemma).

Let ζsp be a suitably large constant. Consider ApproxSubset that takes U⊆V as input and produces U′⊆U as the output.

  1. (i)

    𝔼[m⁢(U′)]≤m⁢(U)/2;

  2. (ii)

    If m⁢(U)≥ζsp, with probability 1−δ−1/m⁢(U), U′ is an approximation preserving subset of U.

The construction of an approximation-preserving subset U′ proceeds in two steps. First, we sparsify the graph by randomly partitioning the set U into U1 and U2 (see Lemma 8). When m⁢(U) is large enough, this partition guarantees the existence of Ui such that m⁢(Ui) is a constant fraction of m⁢(U) (Corollary 10). In the second step, we identify such an approximation-preserving subset from U1 and U2 (Lemma 11). Combining these results yields the proof of Lemma 7.

We prove the following variant of the graph sparsification result of Beame et al. [6].

Lemma 8 (Graph Sparsification).

For a given δ∈(0,1), there exists an absolute constant c such that the following holds. Let G=(V,E) be a graph with n vertices and m edges. Let U1 and U2 be a uniformly random partition of V. Then,

  1. (i)

    𝔼[m⁢(U1)+m⁢(U2)]=m⁢(U)/2;

  2. (ii)

    Pr⁡[|m/2−∑i=12m⁢(Ui)|≥c⁢m⁢log⁡(m/δ)]≤δ.

We will need the following lemma to prove the above graph sparsification lemma.

Lemma 9.

Let A be a set of ℓ elements. For every element t∈A, one assigns a color independently and uniformly from {1,2}. Let C(i) be the number of vertices in A with color i, for any i∈{1,2}. Then for δ∈(0,1), we have

Pr⁡[|C(1)−C(2)|≥6⁢ℓ⁢log⁡(4⁢δ−1)]≤δ⁢ and ⁢𝔼[|C(1)−C(2)|]≤ℓ
Proof.

For t∈A, let Xt be the indicator random variable that is 1 if t is assigned color 1 and 0 otherwise. Then, C(1)=∑t∈AXt and 𝔼[C(1)]=ℓ/2. Using Chernoff’s inequality (Lemma 19) with ε=(6/ℓ)⁢log⁡(4/δ), we have

Pr⁡[|C(1)−ℓ2|>ε⁢ℓ2]≤2⁢exp⁡(6⁢log⁡(4⁢δ−1)ℓ⋅ℓ6)≤δ2 (1)

Similarly, we can have the same bound for color 2.

Pr⁡[|C(2)−ℓ2|>ε⁢ℓ2]≤δ2 (2)

Observe that |C(1)−C(2)|≤|C(1)−(ε⁢ℓ/2)|+|C(2)−(ε⁢ℓ/2)|. Therefore

Pr⁡[|C(1)−C(2)|>ε⁢ℓ]≤δ

For t∈A, let Yt be a random variable that is 1 if t is assigned the color 1 and −1 otherwise. Then C(1)−C(2)=∑t∈AYt=Y. We have that Pr⁡[Yt=1]=Pr⁡[Yt=1]=1/2, then

𝔼[Yt]=0⁢ and ⁢𝔼[Yt2]=1

By the independence of Yt, we get

𝔼[Y2]=∑t∈A𝔼[Yt2]+∑u≠v𝔼[Yu⁢Yv]=ℓ

Finally, we have 𝔼[|Y|]≤𝔼[|Y|2]=𝔼[Y2]≤ℓ. ◀

We now prove Lemma 8.

Proof of Lemma 8.

Let each vertex t∈V be associated with a random variable Yt∈{1,2} such that Pr⁡[Yt=1]=1/2. For i∈{1,2}, define Ui={t∈V∣Yt=i} and

f⁢(Y1,…,Yn)=m⁢(U1)+m⁢(U2).

A fixed edge is counted by f if and only if both its endpoints are assigned the same label, which occurs with probability 1/2. Therefore, 𝔼[f]=m/2.

Consider the Doob martingale X0,X1,…,Xn, where Xt=𝔼[f⁢(Y1,…,Yn)|Y1,…,Yt]. For a fix values of Y1,…,Yt−1, we have,

Xt−1=g⁢(1)+g⁢(2)2, where ⁢g⁢(i)=𝔼[f⁢(Y1,…,Yn)|(Y1,…,Yt−1)∩(Yt=i)]

Since, Xt is either g⁢(1) or g⁢(2), we have |Xt−Xt−1|≤|g⁢(1)−g⁢(2)|. Let N⁢(t) be the set of neighbours of the vertex t and deg⁡(t)=|N⁢(t)|. Let N<t=N⁢(t)∩[t−1] and N>t=N⁢(t)∩{(t+1),…,n}. Let C<t(i) and C>t(i) be the number of vertices in N<t and N>t respectively. So,

Δt=|g⁢(1)−g⁢(2)|=|C<t(1)+𝔼[C>t(1)∣Yt=1]−C<t(2)−𝔼[C>t(2)∣Yt=2]|

The above equation is true because any edge with vertices in [t−1] will have the same contribution to g⁢(1) and g⁢(2). Similarly, any edge which have one vertex in [t−1] and another in {(t+1),…,n} or both of its vertices in {(t+1),…,n} will have the same contribution. Using Lemma 9, we have with probability at least 1−δ′,

Δt≤6⁢deg⁡(t)⁢log⁡4δ′+deg⁡(t)≤2⁢c⁢deg⁡(t)⁢log⁡1δ′=ct

Let ℬ be the event that there exits a t such that Δt>ct. Let na be the set of active vertices (vertices with degree at least 1). Therefore, using union bound Pr⁡[ℬ]≤4⁢na⁢δ′≤4⁢m⁢δ′.

Let S=∑t=1nct2=∑t=1n4⁢c2⁢deg⁡(t)⁢log⁡(4/δ′)=O⁢(m⁢log⁡(1/δ′)) and s=c⁢m⁢log⁡(1/δ′). Using Lemma 21, we have

Pr⁡[|f−m2|>s]≤2⁢exp⁡(−s22⁢S)+Pr⁡[ℬ]≤δ′+4⁢m⁢δ′

Replacing δ′ with δ/c⁢m for a sufficiently large constant, we obtain

Pr⁡[|m2−∑i=12m⁢(Ui)|≥c⁢m⁢log⁡(mδ)]≤δ

which completes the proof. ◀

Corollary 10.

For a subset U⊆V, suppose there exists a sufficiently large absolute constant ζsp such that m⁢(U)≥ζsp. Let U1 and U2 be a uniformly random partition of U. Then, with probability at least 1−1m⁢(U), the following hold.

  1. (i)

    m⁢(U1)m⁢(U)≥1/8 or m⁢(U2)m⁢(U)≥1/8;

  2. (ii)

    m⁢(U1)m⁢(U)≤3/4 and m⁢(U2)m⁢(U)≤3/4.

Proof.

Taking ζsp to be sufficiently large, we have c⁢m⁢(U)⁢log⁡m⁢(U)≤m⁢(U)4. So, by taking δ=1/m⁢(U) in Lemma 8, we

Pr⁡[m⁢(U)4≤∑i=12m⁢(Ui)≤3⁢m⁢(U)4]≥1−1m⁢(U).

This implies that, with probability at least 1−1/m⁢(U), at least one of m⁢(U1)/m⁢(U) and m⁢(U2)/m⁢(U) is at least 1/8, and both m⁢(U1)/m⁢(U) and m⁢(U2)/m⁢(U) are at most 3/4. ◀

To prove the guarantees of ApproxSubset described in Algorithm 1, we need Lemma 11.

Lemma 11.

With probability at least 1−δ, the following statements hold for ApproxSubset

  1. (i)

    If m⁢(Ui)m⁢(U)≥18, then p^⁢(Ui)≥116.

  2. (ii)

    If m⁢(Ui)m⁢(U)<132, then p^⁢(Ui)<116.

The number of ISC queries made is O⁢(log⁡(δ−1)).

Proof.

Consider a subset Ui⊆U for any i∈{1,2}. For each sampled edge, define the indicator random variable

Xj={1if the jth sampled edge lies in Ui,0otherwise.

Observe that 𝔼[Xj]=m⁢(Ui)m⁢(U).

Define the fraction of sampled edges that belong to Ui by X=1|S|⁢∑j∈[|S|]Xj. where S is the multiset of sampled edges (Line 2) obtained via ISC queries on U. Note that X=p^⁢(Ui) and hence

𝔼[p^⁢(Ui)]=1|S|⁢∑j∈[|S|]𝔼[Xj]=m⁢(Ui)m⁢(U)=m⁢(Ui)m⁢(U).

Applying Hoeffding’s bound (Lemma 20), we get

Pr⁡(|p^⁢(Ui)−m⁢(Ui)m⁢(U)|≥132)≤exp⁡(−|S|2⋅(1/32)2)≤δ/2.

The last inequation holds since |S|=O⁢(log⁡1/δ). Using the union bound over i∈{1,2}, we get the desired result. ◀

We now give the proof of Lemma 7, using Lemma 8, Corollary 10 and Lemma 11

Proof of Lemma 7.

In ApproxSubset, the set U is partitioned uniformly at random into U1 and U2. From Lemma 8(i),

𝔼[m⁢(U1)+m⁢(U2)]=m⁢(U)/2.

Since U′ is either U1 or U2, it follows that 𝔼[m⁢(U′)]≤m⁢(U)/2, proving part (i).

We now prove part (ii). Let ℰapx denote the event that U′ is an approximation-preserving subset of U, that is, 1/32≤m⁢(U′)/m⁢(U)≤3/4. Let ℰ be the event that at least one of m⁢(U1)/m⁢(U) and m⁢(U2)/m⁢(U) is at least 1/8, and both m⁢(U1)/m⁢(U) and m⁢(U2)/m⁢(U) are at most 3/4. By Corollary 10,

Pr⁡[ℰ]≥1−1m⁢(U).

Let us condition on the event ℰ. It suffices to bound Pr⁡[ℰapx∣ℰ]. Then both m⁢(U1)/m⁢(U) and m⁢(U2)/m⁢(U) are at most 3/4, and at least one of m⁢(U1)/m⁢(U) and m⁢(U2)/m⁢(U) is at least 1/8; w.l.o.g. assume m⁢(U1)/m⁢(U)≥1/8. If m⁢(U2)/m⁢(U)≥1/32, then since U′∈{U1,U2} we immediately have 1/32≤m⁢(U′)/m⁢(U)≤3/4, that is, Pr⁡[ℰapx∣ℰ]=1. Otherwise m⁢(U2)/m⁢(U)<1/32. By Lemma 11, with probability at least 1−δ, we obtain p^⁢(U1)≥1/16 and p^⁢(U2)<1/16, implying U′=U1. Consequently 1/32≤m⁢(U′)/m⁢(U)≤3/4 holds with probability at least 1−δ conditioned on ℰ. Thus in all cases

Pr⁡[ℰapx∣ℰ]≥1−δ.

Therefore,

Pr⁡[ℰapx] ≥Pr⁡[ℰ]⋅Pr⁡[ℰapx∣ℰ]≥1−1m⁢(U)−δ.

◀

4.2 Procedure to find approximate preserving sequence

We now describe the algorithm ApproxSequence (see Algorithm 2), which constructs the sparsification sequence used by the main estimator.

Algorithm 2 ApproxSequence(V).
Lemma 12 (Correctness of ApproxSequence).

Consider ApproxSequence as described in Algorithm 2. With probability at least 4/5, it outputs an approximation preserving sequence U1,U2,…,Uκ such that m⁢(Uκ)≤8⁢ζsp. Here ζsp is given large constant. The number of ISC queries made is O⁢(κ2).

Proof.
Correctness.

Let us consider the event ℰcol that denotes

  • ■

    There does not exist a j such that the algorithm goes to the next iteration if m⁢(Uj)≤ζsp.

  • ■

    For any j such that the algorithm goes to the next iteration if m⁢(Uj)≥8⁢ζsp.

The probability of ℰcol is lower bounded by IsCollision succeeds in all iterations during the run of the algorithm. Using the union bound, we have

Pr⁡[ℰcol]≥1−∑i=1∞12i+5≥1−125⁢∑i=1∞12i≥1−116=1516.

Let us continue the argument under the conditional space that ℰcol has occurred.

We assume m⁢(U0)=m is sufficiently large; hence, the algorithm does not terminate in the first iteration, given that ℰcol has occurred. Let U0,…,Uκ be the output of the algorithm, where κ is a positive integer. Conditioned on the event ℰcol, we have m⁢(Uj)≥ζsp for every j≤κ−1.

We prove the claim by induction on κ. For each j≥0, let ℰj denote the event which is that the algorithm executes iteration j and either terminates with, m⁢(Uj)≤8⁢ζsp, or it produces an approximation preserving subset Uj+1 such that m⁢(Uj+1)≤3⁢m⁢(Uj)4.

Let ℰ≤j denote the event that ℰi occurs for all i∈[j], that is,

ℰ≤j=⋂i=1jℰi.

Equivalently, ℰ≤j is the event that the algorithm runs for j iterations, such that U0,…,Uj is an approximation preserving sequence, and at iteration j either it produces Uj+1, an approximation preserving subset of Uj such that m⁢(Uj+1)≤3⁢m⁢(Uj)4, or the algorithm terminates with m⁢(Uj)≤8⁢ζsp.

The induction hypothesis is that

Pr⁡[ℰ≤j]≥ 1−δ≤j,

where

δi=1m⁢(Ui)+12i+5,andδ≤j=∑i=0jδi.

We first prove the base case. That is, Pr⁡[ℰ0]≥1−δ0. Recall that we assume that m⁢(U0)=m is sufficiently large. Moreover, we assume that event ℰcol has occurred and algorithm produced a sequence U0,…,Uκ with κ≥1. So, ℰ0 occurs if ApproxSubset reports an approximate preserving subset Uj+1. By Lemma 7, this occurs with probability at least 1−δ0.

For the inductive step, we mainly show that Pr⁡[ℰj|ℰ≤j−1]≥1−δj for j≥1. Let us argue that it is sufficient. Note that δ≤j=δ≤j−1+δj for j≥1 and

Pr⁡[ℰ≤j]=Pr⁡[ℰ≤j−1∩ℰj]=Pr⁡[ℰ≤j−1]⋅Pr⁡[ℰj∣ℰ≤j−1].

By the induction hypothesis, Pr⁡[ℰ≤j−1]≥1−δ≤j−1. We will show that

Pr⁡[ℰj∣ℰ≤j−1]≥1−δj.

Therefore,

Pr⁡[ℰ≤j] =Pr⁡[ℰ≤j−1]⋅Pr⁡[ℰj∣ℰ≤j−1]
≥(1−δ≤j−1)⁢(1−δj)
≥1−δ≤j−1−δj
=1−δ≤j.

Consider any j with 1≤j≤κ−1. Under the conditional space ℰcol and along with the fact that we assume m⁢(U0)=m is sufficiently large, m⁢(Uj)≥ζsp for each j≤κ−1.

We consider two cases: m⁢(Uj)≥8⁢ζsp, and ζsp≤m⁢(Uj)≤8⁢ζsp, and analyse them individually.

Case 1: (𝒎⁢(𝑼𝒋)>𝟖⁢𝜻𝐬𝐩).

Recall that we are assuming that the event ℰcol has occurred. So, ApproxSequence does not terminate after executing IsCollision and execute ApproxSubset. Moreover it produces an approximate preserving subset Uj+1 with m⁢(Uj+1)≤3⁢m⁢(Uj)4, that is event ℰj occurs, when ApproxSubset reports an approximate preserving subset Uj+1 with m⁢(Uj+1)≤3⁢m⁢(Uj)4. By Lemma 7 and Line 7 of ApproxSequence, this occurs with probability at least 1−δj where,

δj=1m⁢(Uj)+12j+5

Hence,

Pr⁡[ℰj∣ℰ≤j−1]≥1−δj(1),
Case 2: (𝜻𝐬𝐩≤𝒎⁢(𝑼𝒋)≤𝟖⁢𝜻𝐬𝐩).

In this case, we show that

Pr⁡[ℰj∣ℰ≤j−1]≥1−δj

regardless of whether ApproxSequence terminates after executing IsCollision or proceeds to execute ApproxSubset.

In the former case, the claim follows directly from the definition of ℰj together with the fact that m⁢(Uj)≤8⁢ζsp. In the latter case, ApproxSequence produces an approximate preserving subset Uj+1 of Uj provided that ApproxSubset returns an approximate preserving subset Uj+1. By Lemma 7, this occurs with probability at least 1−δj, where

δj≤1m⁢(Uj)+12j+5.

Hence,

Pr⁡[ℰj∣ℰ≤j−1]≥1−δj.

We are done with the proof of the inductive step. We summarize the above discussion as follows. Pr⁡[ℰcol]≥15/16. When the event ℰcol occurs, Pr⁡[ℰj|ℰj−1]≥1−δj for all j≥0. Moreover, Pr⁡[ℰ≤j]≥1−δ≤j for all j≥0. Recall that the algorithm outputs a sequence U0,…,Uκ−1. The events ℰcol and ℰ≤κ−1 occur with probability at least

Pr⁡[ℰcol]−δ≤κ−1.

Hence, the following facts hold with the same probability:

  1. 1.

    U0,…,Uκ is an approximate preserving sequence, that is,

    132≤m⁢(Ui)m⁢(Ui−1)≤34,where⁢i∈[κ].
  2. 2.

    m⁢(Uj)≥ζsp for each j≤κ−1, and m⁢(Uκ)≤8⁢ζsp.

Note that ApproxSequence produces an approximation-preserving sequence U1,U2,⋯,Uκ such that m⁢(Uκ)≤8⁢ζsp whenever both of the above conditions hold. This occurs with probability at least 1/5, provided δκ−1≤1/10, since Pr⁡[ℰcol]≥15/16.

We complete the proof of correctness of ApproxSequence by showing that δκ−1≤1/10.

δ≤κ−1=∑i=0κ−11m⁢(Uj)+12j+5≤∑i=0∞12j+4+∑i=0κ−11m⁢(Uj)≤116+∑i=0κ−13κ−1−i4κ−1−i⁢ζsp.

The last inequation holds since m⁢(Uκ−1)≥ζsp and m⁢(Ui)≤3⁢m⁢(Ui−1)4 for all i∈[κ−1]. We obtain the bound of δ≤κ−1 as below:

δ≤κ−1=116+1ζsp⁢∑i=0κ−13κ−1−i4κ−1−i=116+1ζsp⁢∑i=0κ−13i4i≤116+2ζsp≤110.

Here we have used the fact that ζsp is a large constant.

Query Complexity.

From Lemma 2 and 11, the number of ISC queries made by IsCollision (for a constant threshold τ=ζsp) and ApproxSubset over κ iterations is,

O⁢(∑j=1κlog⁡(2κ+5))=O⁢(κ2)

◀

Note that the number of iterations and the query complexity of ApproxSequence (as mentioned in the above lemma) are random variables. We will argue their expectation in the following lemma. Moreover, when we discuss the full algorithm in Section 5 (that uses ApproxSequence as a subroutine), we show that the query complexity of the full algorithm is O⁢(κ2⋅log⁡κ), where κ is the number of iterations of ApproxSequence. The following lemma will be useful in establishing the final query complexity in Section 5.

Lemma 13.

𝔼[κ]=O⁢(log⁡m), 𝔼[κ2]=O⁢(log2⁡m), and 𝔼[κ2⁢log⁡κ]=O⁢(log2⁡m⋅log⁡log⁡m).

From Lemma 12 and Lemma 13, Lemma 6 follows. In the rest of the section, we prove Lemma 13 and Lemma 6.

Proof of Lemma 13.

Here, we prove that

𝔼[κ2⁢log⁡κ]=O⁢(log2⁡m⁢log⁡log⁡m)

The remaining bounds follow similarly.

We want to analyse 𝔼[κ2⁢log⁡κ] where the expectation is over the distribution of κ for a run of the algorithm. To analyse this, we consider two different cases. For the first case, let t∗ denote the time when the algorithm generates a subgraph with less than or equal to ζsp edges. Formally, we define t∗ as the time t such that m⁢(Ut)≤ζsp, and m⁢(Ut−1)>ζsp. If this is not the case, i.e. when m⁢(Ut)>ζsp holds throughout the algorithm, we show that κ=O⁢(log⁡m).

First, we bound the expectation of m⁢(Ut) for some t∈[κ]. By Lemma 7, we have

𝔼[m⁢(Ut)|m⁢(Ut−1)]≤m⁢(Ut−1)2.

By a inductive argument, and the fact that m⁢(U0)=m, we have

𝔼[m⁢(Ut)]=𝔼[𝔼[m⁢(Ut)∣m⁢(Ut−1)]]≤𝔼[m⁢(Ut−1)]2≤…≤m2t (3)

Now, when m⁢(Uj)>ζsp holds throughout the algorithm, we have

ζsp<𝔼[m⁢(Uκ)]≤m2κ⟹κ=O⁢(log⁡m)

Hence, we now focus on the case when there exists a t∗≤κ. Note that t∗ is unique for a run of the algorithm. Once, the algorithm reaches t∗, the probability of the algorithm terminating depends on the calls to IsCollision succeeding. We start with analysing the conditional expectation of κ2⁢log⁡κ given t∗.

𝔼[κ2⁢log⁡κ∣t∗] =∑j=1∞j2⁢log⁡j⁢Pr⁡[κ=j∣t∗]
=∑j=1t∗−1j2⁢log⁡j⁢Pr⁡[κ=j∣t∗]+∑j=t∗∞j2⁢log⁡j⁢Pr⁡[κ=j∣t∗]
=∑j=t∗∞j2⁢log⁡j⁢Pr⁡[κ=j∣t∗] (As t∗≤κ)
≤∑j=t∗∞j2⁢log⁡j⁢Pr⁡[κ≥j∣t∗]
≤∑j=t∗∞j2⁢log⁡j2j+5
=O⁢(t∗2⁢log⁡t∗) (4)

Now, we analyse the distribution of t∗. We use (3) to obtain a bound on the probabilities of different values of t∗.

Pr⁡[t∗=t]≤Pr⁡[t∗≥t] ≤Pr⁡[m⁢(Ut)>ζsp]
≤𝔼[m⁢(Ut)]ζsp Markov’s Inequality (Lemma 17)
≤m2t⁢ζsp (5)

Now, we bound the expectation of κ2⁢log⁡κ.

𝔼[κ2⁢log⁡κ] =𝔼[𝔼[κ2⁢log⁡κ∣t∗]]
=𝔼[t∗2⁢log⁡t∗] (Equation 4)
=∑j=1∞j2⁢log⁡j⁢Pr⁡[t∗=j]
=∑j=12⁢log⁡mj2⁢log⁡j⁢Pr⁡[t∗=j]+∑j=2⁢log⁡m+1∞j2⁢log⁡j⁢Pr⁡[t∗=j]
≤8⁢log2⁡m⁢log⁡log⁡m⁢∑j=12⁢log⁡mPr⁡[t∗=j]+∑2⁢log⁡m∞m⁢j2⁢log⁡j2j⁢ζsp
=O⁢(log2⁡m⁢log⁡log⁡m)

which proves the desired result. ◀

Lemma 6 follows from the algorithm ApproxSequence (Algorithm 2) along with Lemma 12 and Lemma 13.

5 Full algorithm

In this section, we present the full algorithm for estimating the number of edges using ISC queries and prove our main result stated below.

Theorem 1 (Main result). [Restated, see original statement.]

There exists a randomized algorithm that, given access to a graph G through ISC queries and an approximation parameter ε∈(0,1/3), outputs an estimate m^ of the number of edges m in G such that, with probability at least 2/3,

(1−ε)⁢m≤m^≤(1+ε)⁢m.

The algorithm uses O⁢(ε−2⁢log2⁡m⋅log⁡log⁡m) ISC queries in expectation.

EdgeEstimation (Algorithm 4) begins by calling ApproxSequence which outputs an approximation preserving sequence U1,…,Uκ, where each pi=m⁢(Ui)/m⁢(Ui−1) is bounded below by a constant. This ensures that each ratio can be estimated efficiently. To estimate each pi, we use the subroutine MulEstimation which returns an (1±ε)-approximation of pi. The procedure MulEstimation is described in Algorithm 3 and its guarantee is established in Lemma 14.

Algorithm 3 MulEstimation(U′,U,ε,δ).
Algorithm 4 EdgeEstimation(V,ε).
Lemma 14 (Correctness of MulEstimation).

For subsets U′⊆U⊆V and ε>0 , If p⁢(U′)=m⁢(U′)m⁢(U)≥132, then MulEstimation outputs p^⁢(U′)=(1+x)⁢p⁢(U′), where 𝔼[x]=0 and x∈(−ε,ε) with probability at least 1−δ. The number of ISC queries made is O⁢(log⁡(δ−1)/ε2).

Proof.

Let Xj be the indicator random variable such that,

Xj={1If the jt⁢h sampled edge is in U′0Otherwise 

Define number of edges sampled that belong to U′ is X=∑j∈[|S|]Xj, where S is the multi-set of sampled edges (Line 2) and the expected size of X is

𝔼[X]=∑j∈[|S|]𝔼[Xj]=|S|⋅m⁢(U′)m⁢(U)=|S|⋅p⁢(U′)≥|S|32

Therefore,

𝔼[x]=𝔼[p^⁢(U′)p⁢(U′)]−1=𝔼[X]|S|⁢p⁢(U′)−1=0

By the Chernoff Bound (see Lemma 19), we have
Pr⁡[x∈(−ε,ε)]=Pr⁡[p^⁢(U′)∈(1±ε)⁢p⁢(U′)]=Pr⁡[X∈(1±ε)⁢𝔼[X]]≥1−2⁢exp⁡(−ε2⁢|S|96)≥1−δ,

where the last step uses |S|=O⁢(log⁡(δ−1)/ε2). ◀

Now, we prove the guarantees of EdgeEstimation In particular, we prove the correctness of EdgeEstimation and its query complexity in Lemma 16 and Lemma 15, respectively.

Lemma 15.

The expected query complexity of EdgeEstimation is O⁢(log2⁡m⋅log⁡log⁡m).

Proof.

From Lemma 14, the number of ISC queries made by MulEstimation in j-th iteration is

O⁢(log⁡(16⁢κ)ε′⁣2)⁢where ⁢ε′=ε200⁢κ

Summing over κ iterations, we get

O⁢(∑j=1κlog⁡(κ)ε′⁣2)=O⁢(κ2⁢log⁡κε2)

From Lemma 12, the number of ISC queries made by ApproxSequence is O⁢(κ2). Finally, from Lemma 3, the number of ISC queries made by BirthdayEstimate is O⁢(8⁢ζsp/ε)=O⁢(1/ε). Combining all contributions, the total number of ISC queries made by EdgeEstimation is dominated by MulEstimation, and hence is, O⁢(κ2⁢log⁡κ/ε2). From Lemma 13,

𝔼[κ2⁢log⁡κ]=O⁢(log2⁡m⁢log⁡log⁡m)

which bounds the expected query complexity. ◀

Lemma 16.

In EdgeEstimation, the estimate m^ is an (1±ε)-approximation to m with probability at least 3/4.

Proof.

Let ℰ1=ℰsub∩ℰbir, where ℰsub be the event that ApproxSequence outputs an approximation-preserving sequence U1,U2,…,Uκ with m⁢(Uκ)≤8⁢ζsp. From Lemma 12 we have Pr⁡[ℰsub]≥4/5.

ℰbir be the event that BirthdayEstimate outputs an (1±ε/3) approximation of m⁢(Uκ) from Lemma 3. Also, from Lemma 3, we have Pr⁡[ℰbir∣ℰsub]≥15/16. Therefore,

Pr⁡[ℰ1]=Pr⁡[ℰsub]⁢Pr⁡[ℰbir∣ℰsub]≥1−(15+116)≥5980

Let ℰ2 be the event that MulEstimation(Ui,Ui−1,ε′,1/16⁢κ) outputs pi^=(1±xi/4)⁢pi such that 𝔼[xi]=0 and xi∈(−4⁢ε′,4⁢ε′) for all i∈[κ], where ε′=ε200⁢κ . Therefore, using Lemma 14 and applying the union bound over all i∈[κ],

Pr⁡[ℰ2∣ℰ1]=1−∑j=1κ116⁢κ≥1516.

Let ℰ3 be the event that |∑i=1κxi|≤ε/9. By Hoeffding’s bound (Lemma 20),

Pr⁡[ℰ3∣ℰ1∩ℰ2] =1−Pr⁡[|∑i=1κxi|>ε9|ℰ1∩ℰ2]
≥1−2⁢exp⁡(−2⁢ε281⁢∑i=1κ(2⁢ε50⁢κ)2)≥1−1e12. (6)

Hence,

Pr⁡[ℰ1∩ℰ2∩ℰ3] =Pr⁡[ℰ1]⋅Pr⁡[ℰ2|ℰ1]⋅Pr⁡[ℰ3∣ℰ1∩ℰ2]≥1−(2180+116+1e12)≥23

In what follows, we assume that all of the events ℰ1, ℰ2 and ℰ3 occur. Since, Pr⁡[ℰ1∩ℰ2∩ℰ3]≥2/3, it is enough to argue that EdgeEstimation returns an (1±ε)-approximation to m when all ℰ1, ℰ2 and ℰ3 holds.

Combining the output of MulEstimation over the κ iterations, we get,

∏i=1κp^i=∏i=1κpi⋅∏i=1κ(1+xi4)

Using the fact that for each xi∈(0,1), it can be shown that

1−∑i=1κxi4≤∏i=1κ(1+xi4)≤1+∑i=1κxi

Since event ℰ3 occurs,

∏i=1κpi⋅(1−ε36)≤∏i=1κp^i≤∏i=1κpi⋅(1+ε9)

Using the fact that for any ε∈(0,1/3), we have 1−3⁢ε≤(1+ε)−1 and (1−ε)−1≤1+3⁢ε. We get,

(1−ε3)⋅1∏i=1κpi≤1∏i=1κp^i≤1∏i=1κpi⋅(1+ε12) (7)

Since ℰ1 occurs, i.e., ℰbir occurs, m^b satisfies the following:

(1−ε3)⋅m⁢(Uκ)≤m^b≤(1+ε3)⋅m⁢(Uκ) (8)

Combining (7) and (8), we get,

(1−ε3)2⋅m⁢(Uκ)∏i=1κpi≤m^=m^b∏i=1κp^i≤(1+ε12)⁢(1+ε3)⋅m⁢(Uκ)∏i=1κpi

Since, pi=m⁢(Ui)m⁢(Ui−1) for each i∈[κ] and U0=V, m⁢(Uκ)∏i=1κpi=m⁢(U0)=m. So, simplifying the above expression, we have

(1−ε)⁢m≤m^≤(1+ε)⁢m.

◀

References

  • [1] Tomer Adar, Yahel Hotam, and Amit Levi. When Local and Non-Local Meet: Quadratic Improvement for Edge Estimation with Independent Set Queries, 2026. arXiv:2601.21457. doi:10.48550/arXiv.2601.21457.
  • [2] Raghavendra Addanki, Andrew McGregor, and Cameron Musco. Non-Adaptive Edge Counting and Sampling via Bipartite Independent Set Queries. In Proceedings of the 30th Annual European Symposium on Algorithms, ESA, pages 2:1–2:16, 2022. doi:10.4230/LIPIcs.ESA.2022.2.
  • [3] Matthew Aldridge, Oliver Johnson, and Jonathan Scarlett. Group Testing: An Information Theory Perspective. Foundations and Trends in Communications and Information Theory, 15(3-4):196–392, 2019. doi:10.1561/0100000099.
  • [4] 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. doi:10.1007/S00453-017-0287-3.
  • [5] Sepehr Assadi, Deeparnab Chakrabarty, and Sanjeev Khanna. Graph Connectivity and Single Element Recovery via Linear and OR Queries. In Proceedings of the 29th Annual European Symposium on Algorithms (ESA), pages 7:1–7:19, 2021. doi:10.4230/LIPIcs.ESA.2021.7.
  • [6] Paul Beame, Sariel Har-Peled, Sivaramakrishnan Natarajan Ramamoorthy, Cyrus Rashtchian, and Makrand Sinha. Edge Estimation with Independent Set Oracles. ACM Transactions on Algorithms, 16(4):52:1–52:27, 2020. preliminary version of this paper appeared as an extended abstract in the proceedings of ITCS 2018. doi:10.1145/3404867.
  • [7] Lorenzo Beretta, Deeparnab Chakrabarty, and C. Seshadhri. Faster Estimation of the Average Degree of a Graph Using Random Edges and Structural Queries. In Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 939–971, 2026. doi:10.1137/1.9781611978971.38.
  • [8] Anup Bhattacharya, Arijit Bishnu, Arijit Ghosh, and Gopinath Mishra. Faster Counting and Sampling Algorithms using Colorful Decision Oracle. ACM Transactions on Computation Theory, 16(2):12:1–12:19, 2024. A preliminary version of this paper appeared as an extended abstract in the proceedings of STACS 2022. doi:10.1145/3657605.
  • [9] Rishiraj Bhattacharyya and Sourav Chakraborty. Property Testing of Joint Distributions using Conditional Samples. ACM Transactions on Computation Theory, 10(4):16:1–16:20, 2018. doi:10.1145/3241377.
  • [10] Rishiraj Bhattacharyya, Sourav Chakraborty, Yash Pote, Uddalok Sarkar, and Sayantan Sen. Testing Self-Reducible Samplers. In Proceedings of the Thirty-Eighth AAAI Conference on Artificial Intelligence (AAAI), pages 7952–7960, 2024. doi:10.1609/AAAI.V38I8.28632.
  • [11] Arijit Bishnu, Debarshi Chanda, Buddha Dev Das, Arijit Ghosh, and Gopinath Mishra. Optimal non-adaptive algorithm for edge estimation. CoRR, abs/2512.11994, 2025. doi:10.48550/arXiv.2512.11994.
  • [12] Arijit Bishnu, Debarshi Chanda, and Gopinath Mishra. Towards tight bounds for estimating degree distribution in streaming and query models. CoRR, abs/2507.21784, 2025. doi:10.48550/arXiv.2507.21784.
  • [13] Arijit Bishnu, Arijit Ghosh, and Gopinath Mishra. On the Complexity of Triangle Counting Using Emptiness Queries. In Proceedings of the 27th International Conference on Randomization and Computation (RANDOM), volume 275, pages 48:1–48:22, 2023. doi:10.4230/LIPIcs.APPROX/RANDOM.2023.48.
  • [14] Clément L. Canonne, Xi Chen, Gautam Kamath, Amit Levi, and Erik Waingarten. Random Restrictions of High Dimensional Distributions and Uniformity Testing with Subcube Conditioning. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 321–336, 2021. doi:10.1137/1.9781611976465.21.
  • [15] Clément L. Canonne, Dana Ron, and Rocco A. Servedio. Testing equivalence between distributions using conditional samples. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1174–1192, 2014. doi:10.1137/1.9781611973402.87.
  • [16] Clément L. Canonne, Dana Ron, and Rocco A. Servedio. Testing Probability Distributions using Conditional Samples. SIAM Journal on Computing, 44(3):540–616, 2015. An extended abstract of this work appeared in SODA 2014. doi:10.1137/130945508.
  • [17] Diptarka Chakraborty, Sourav Chakraborty, Gunjan Kumar, and Kuldeep S. Meel. Approximate Model Counting: Is SAT Oracle More Powerful Than NP Oracle? In Proceedings of the 50th International Colloquium on Automata, Languages, and Programming (ICALP), volume 261, pages 123:1–123:17, 2023. doi:10.4230/LIPIcs.ICALP.2023.123.
  • [18] Sourav Chakraborty, Eldar Fischer, Yonatan Goldhirsh, and Arie Matsliah. On the power of conditional samples in distribution testing. In Proceedings of the 4th Conference on Innovations in Theoretical Computer Science (ITCS), pages 561–580, 2013. doi:10.1145/2422436.2422497.
  • [19] Debarshi Chanda. Improved Bounds with a Simple Algorithm for Edge Estimation for Graphs of Unknown Size. CoRR, abs/2511.03650, 2025. doi:10.48550/arXiv.2511.03650.
  • [20] Debarshi Chanda, Buddha Dev Das, Arijit Ghosh, and Gopinath Mishra. From decision to random certificates: Exponential separation for edge estimation with independent set queries, 2026. arXiv:2607.07483.
  • [21] Xi Chen, Amit Levi, and Erik Waingarten. Nearly Optimal Edge Estimation with Independent Set Queries. In Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2916–2935, 2020. doi:10.1137/1.9781611975994.177.
  • [22] Fan Chung and Linyuan Lu. Concentration Inequalities and Martingale Inequalities: A Survey. Internet Mathematics, 3(1):79–127, 2006.
  • [23] Holger Dell, John Lapinskas, and Kitty Meeks. Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle. SIAM Journal on Computing, 51(4):849–899, 2022. A preliminary version of this paper appeared as an extended abstract in the proceedings of SODA 2020. doi:10.1137/19M130604X.
  • [24] Holger Dell, John Lapinskas, and Kitty Meeks. Nearly Optimal Independence Oracle Algorithms for Edge Estimation in Hypergraphs. In Proceedings of the 51st International Colloquium on Automata, Languages, and Programming (ICALP), pages 54:1–54:17, 2024. doi:10.4230/LIPIcs.ICALP.2024.54.
  • [25] Robert Dorfman. The Detection of Defective Members of Large Populations. The Annals of Mathematical Statistics, 14(4):436–440, 1943.
  • [26] Talya Eden, Dana Ron, and C. Seshadhri. Sublinear Time Estimation of Degree Distribution Moments: The Arboricity Connection. SIAM Journal on Discrete Mathematics, 33(4):2267–2285, 2019. doi:10.1137/17M1159014.
  • [27] Talya Eden and Will Rosenbaum. Lower Bounds for Approximating Graph Parameters via Communication Complexity. In Proceedings of the 21st International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), pages 11:1–11:18, 2018. doi:10.4230/LIPIcs.APPROX-RANDOM.2018.11.
  • [28] 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. An extended abstract of this paper appeared in the proceedings of STOC 2004. doi:10.1137/S0097539704447304.
  • [29] Oded Goldreich and Dana Ron. Approximating Average Parameters of Graphs. Random Structures & Algorithms, 32(4):473–493, 2008. An extended abstract of this paper appeared in the proceedings of RANDOM 2006. doi:10.1002/RSA.20203.
  • [30] Michael Mitzenmacher and Eli Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, Cambridge, 2005. doi:10.1017/CBO9780511813603.
  • [31] 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, 8(4), 2016. doi:10.1145/2930657.
  • [32] Larry J. Stockmeyer. The Complexity of Approximate Counting (Preliminary Version). In Proceedings of the 15th Annual ACM Symposium on Theory of Computing (STOC), pages 118–126, 1983. doi:10.1145/800061.808740.
  • [33] Larry J. Stockmeyer. On Approximation Algorithms for #P. SIAM Journal on Computing, 14(4):849–861, 1985. doi:10.1137/0214060.
  • [34] Jakub Tětek and Mikkel Thorup. Edge Sampling and Graph Parameter Estimation via Vertex Neighborhood Accesses. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 1116–1129, 2022.

Appendix A Concentration Inequalities

We use the following concentration bounds.

Lemma 17 (Markkov’s inequlaity, see [30]).

Let X be a random variable that assumes only nonnegative values. Then, for all a>0

Pr⁡[X≥a]≤𝔼[X]a.
Lemma 18 (Chebyshev’s inequality, see [30]).

Let X be a random variable and a>0, Then

Pr⁡[|X−𝔼[X]|>a]≤Var(X)a2.
Lemma 19 (Multiplicative Chernoff bound, see [30]).

Let X1,X2,…,Xt be i.i.d. random variables where Pr⁡[Xi=1]=p and Pr⁡[Xi=0]=1−p for all i∈[t], and X=∑i∈[t]Xi. Then, we have

Pr⁡[X≤(1−ε)⁢𝔼[X]] ≤exp⁡(−ε2⁢𝔼[X]3) 0≤ε<1
Pr⁡[X≥(1+ε)⁢𝔼[X]] ≤exp⁡(−ε2⁢𝔼[X]2) ε≥0
Lemma 20 (Hoeffding’s bound, see [30]).

Let X1,X2,…,Xt be independent random variables such that for all i∈[t], 𝔼[X]=μ and Pr⁡[a≤Xi≤b]=1. Then

Pr⁡[|1t⁢∑i=1tXi−μ|≥ε]≤2⁢exp⁡(−2⁢t⁢ε2(b−a)2).
Lemma 21 (See [22]).

Let f be any function of t independent random variables Y1,…,Yt and let Xi=𝔼[f⁢(Y1,…,Yt)|Y1,…,Yi] for i∈[t] and X0=𝔼[f⁢(Y1,…,Yt)]. Let ℬ be the event that there exists i∈[t] such that |Xi−Xi−1|>ci where c1,…,ct are some non negative numbers. Let S=∑i=1tci2, then

Pr⁡[|Xt−X0|>s]≤2⁢exp⁡(−s22⁢S)+Pr⁡[ℬ].