From Decision to Random Certificates: Exponential Separation for Edge Estimation with Independent Set Queries
July 08, 2026
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 \pm \varepsilon)\)-approximation to the number of edges with constant success probability using \(\widetilde{O}(\log^{2} 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 \(\widetilde{\Theta}\!\left(\min\left\{\sqrt{m},\, \frac{n}{\sqrt{m}}\right\}\right)\) queries, while direct random edge-sample access requires \(\widetilde{\Theta}(\sqrt{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.
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,\dots,n\}\) vertices and \(\left|{E}\right| = m\) edges. Given query access to \(G\) and an approximation parameter \(\varepsilon\in (0,1)\), the objective is to output an estimate \(\widehat{m}\) such that \[(1-\varepsilon)m \;\le\; \widehat{m} \;\le\; (1+\varepsilon)m\] with success probability at least \(2/3\).
1.0.0.1 Query model and our result.
We work in a query model built on Independent Set (IS) queries, introduced by [1]. The IS query takes a subset of
vertices \(U \subseteq V\) and returns whether \(U\) is an independent set.
We consider the Independent Set with Certificate query, denoted by \(\texttt{ISC}{}\), which takes as input a subset of vertices \(U \subseteq V\) and returns \[\texttt{ISC}(U) = \begin{cases} e\sim \mathrm{Unif}(E(U)), & \text{if } E(U) \neq \emptyset,\\[4pt] 0, & \text{otherwise}, \end{cases}\] where \(E(U)\) denotes the set of edges in the subgraph of \(G\) induced by \(U\), and \(\mathrm{Unif}(S)\) denotes the uniform distribution over a (nonempty) set \(S\).
Importantly, the \(\texttt{ISC}{}\) query preserves the structural constraint of a standard \(\texttt{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.
[1] showed that the number of edges in a graph can be estimated using \[\widetilde{O}\!\left( \min\!\left\{ \frac{n^{2}}{m}, \sqrt{m} \right\} \right) \;=\; \widetilde{O}(n^{2/3})\] \(\texttt{IS}{}\) queries, establishing a polynomial separation from local query based algorithms that require \(\Theta(n)\) queries in the worst case [2]. In a subsequent work, [3] nearly resolved the query complexity of edge estimation using IS queries by showing that \[\widetilde{\Theta}\!\left( \min\!\left\{ \frac{n}{\sqrt{m}}, \sqrt{m} \right\} \right)\] queries are both necessary and sufficient. In particular, this implies a worst-case complexity of \(\widetilde{\Theta}(\sqrt{n})\) \(\texttt{IS}{}\) queries.
Our main result shows that the natural enrichment of \(\texttt{IS}{}\) queries with random certificates yields an exponential separation from standard \(\texttt{IS}{}\) queries for edge estimation, achieving polylogarithmic query complexity in \(m\).
theoremMainUB There exists a randomized algorithm that, given access to a graph \(G\) through \(\texttt{ISC}{}\) queries and an approximation parameter \(\varepsilon\in (0,1/3)\), outputs an estimate \(\widehat{m}\) of the number of edges \(m\) in \(G\) such that, with probability at least \(\frac{2}{3}\), \[(1-\varepsilon)m \;\le\; \widehat{m} \;\le\; (1+\varepsilon)m.\] The algorithm uses \(O(\varepsilon^{-2}\log^{2}m\cdot \log\log m)\) \(\texttt{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.
[Thm:32Main32Upper32Bound] not only demonstrates the power gained by augmenting \(\texttt{IS}{}\) access with random certificates over standard \(\texttt{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 \(\widetilde{\Theta}(\sqrt{m})\) samples [4]. 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 models, achieving query complexity \(\widetilde{O}(\log^2 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.
1.0.0.2 Group testing perspective.
The introduction of \(\texttt{IS}{}\) queries in graph algorithms was originally motivated by ideas from group testing. In classical group testing, introduced by [5] 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 [6]. 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. [1] introduced both \(\texttt{IS}{}\) and Bipartite Independent Set (\(\texttt{BIS}{}\)) queries through this lens. A \(\texttt{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, [7] and [8] introduced the Edge Emptiness query \(\mathrm{EE}\) to study triangle estimation and connectivity in graphs, respectively. An \(\mathrm{EE}\) query specifies a set of candidate edges and reports whether at least one of them exists in the graph.
1.0.0.3 Decision versus counting.
In a series of seminal works, [9], [10] 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 \(\texttt{IS}{}\) queries with a random certificate enables efficient approximate counting of edges in a graph.
1.0.0.4 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 [11], [12] 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 [13]–[16].
In our setting, the \(\texttt{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, \(\texttt{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.
1.0.0.5 Power of a random certificate.
Studying the power of random certificates for approximate counting is an important question across a variety of query models [17], [18]. 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 \(\texttt{IS}{}\) and \(\texttt{BIS}{}\), introduced by [1] for estimating the number of edges. Our \(\texttt{ISC}{}\) query fits naturally within this framework: it preserves the structure of \(\texttt{IS}{}\) while adding a random certificate. In particular, our algorithm achieves substantially lower query complexity compared to algorithms using only \(\texttt{IS}{}\) access, and also improves over the best known \(\widetilde{O}(\log^{5} n)\)-query algorithm based on \(\texttt{BIS}{}\) access due to [19].
The main difference between the power of random certificates studied in [17], [18] and our setting is that our query oracles are group graph queries that retain the structural properties of the underlying graph.
1.0.0.6 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 [2], [20]–[22], 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 [23]–[25] 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 [25]–[28].
Another line of work studies structured global queries, notably \(\texttt{IS}{}\) and \(\texttt{BIS}{}\) [1], [3], [19]. These queries provide decision-only access over vertex subsets while preserving graph structure, and have been extended to hypergraphs [29]–[31]. We discussed their known upper and lower bounds earlier in the Introduction.
Finally, [32] showed that augmenting \(\texttt{IS}{}\) queries with
additional local queries yields a quadratic separation from using \(\texttt{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 \(\widetilde{O}(f)\), suppress factors polynomial in \(1/ \varepsilon\) and \(\log f\). For an integer \(k\), we define \([k] = \left\{{1,\dots,k}\right\}\). We write \(a = (1 \pm \varepsilon) b\) to indicate that \(a\) is a \((1 \pm \varepsilon)\)-approximation of \(b\).
Throughout, we use \(G = (V, E)\) to denote the input graph with \(m= \left|{E}\right|\) number of edges and \(V= \left|{V}\right|\) vertices. For a subset \(U \subseteq 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.
2.0.0.1 Outline of the Algorithm.
At a high level, our algorithm maintains a nested sequence of vertex subsets \[V= U_0 \supseteq U_1 \supseteq \cdots \supseteq U_\kappa,\] where each \(U_j\) contains a constant fraction of the edges of \(U_{j-1}\). The algorithm alternates between two modes:
If the current induced subgraph is “small” (that is, has fewer than \(\tau\) 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_\kappa\) whose edge count is small enough to estimate accurately; we set the threshold for \(U_\kappa\) to be a sufficiently large constant. The final estimate of \(m\) is then reconstructed by multiplying the relative edge losses across all steps.
2.0.0.2 Where the \(\widetilde{O}(\log^2 m)\) 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 \(\texttt{IS}{}\) or \(\texttt{BIS}{}\) based algorithms:
Random certificates enable output-sensitive sparsification: Unlike decision-only \(\texttt{IS}{}\) or \(\texttt{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 \(U_0 \supseteq U_1 \supseteq \cdots \supseteq U_\kappa\) such that each \(U_j\) retains a constant fraction of edges of \(U_{j-1}\). Crucially, we establish \(\kappa\) to be \(O(\log m)\) in expectation, independent of \(n\). We also bound the number of queries required to construct this sequence as \(O(\kappa^2)\) and bound its expectation.
Local multiplicative reconstruction: We only need to estimate the ratios \(p_j = \frac{m(U_j)}{m(U_{j-1})}\), each of which is \(\Omega(1)\) due to the \(U_0,\ldots,U_\kappa\) being an approximation preserving subsequence. This keeps the per-level query complexity small and makes the overall cost in expectation \(\widetilde{O}(\kappa^2) = \widetilde{O}(\log^2 m)\).
2.0.0.3 Estimating Small Edge Counts.
Fix a threshold \(\tau\). One can design an algorithm that makes \(O(\sqrt{\tau})\) ISC queries and guarantees the following with desired probability about a given subset
\(U \subseteq V\). If \(m(U)\leq \tau\), then the algorithm reports an approximation of \(m(U)\). Moreover, if \(m(U) \geq
8\tau\), the algorithm reports that \(m(U)\) is large. The proof is based on the birthday paradox. The details can be found in 3 and Appendix 7.
2.0.0.4 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 \(U^1\) and \(U^2\). A graph sparsification lemma, along the result of [1], shows that with desired probability,
\[\left| \frac{m(U)}{2} - \sum_{i=1}^{2} m(U^i) \right| \leq c \sqrt{m(U)} \log m(U).\]
We provide the proof in 4. Intuitively, this means that the total number of edges inside \(U^1\) and \(U^2\) 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 \(U^1\) or \(U^2\) must contain a constant fraction of the edges of \(U\). More precisely, there exists an absolute constant \(\zeta_\mathrm{sp}\) such that if \(m(U)\ge \zeta_\mathrm{sp}\), then with probability at least \(1-1/m(U)\), at least one of \(m(U^1)/m(U)\) and \(m(U^2)/m(U)\) is at least \(1/8\), and both \(m(U^1)/m(U)\) and \(m(U^2)/m(U)\) are at most \(3/4\).
2.0.0.5 Choosing the Good Part.
After partitioning \(U\) into \(U^1\) and \(U^2\), we must identify which part retains an appropriate fraction of the edges. Note that this step is fundamentally enabled by the \(\texttt{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 \(U^1\) or \(U^2\).
To do this, we draw random edges from \(U\) via ISC queries. Let \(\widehat{p}(U^i)\) be the fraction of sampled edges that fall inside \(U^i\), for \(i \in [2]\). If \(\widehat{p}(U^i) \ge 1/16\), we select \(U^i\) as the next subset; otherwise, we pick an
arbitrary part. A Chernoff bound guarantees that, with desired probability, we correctly identify a subset satisfying \[\frac{1}{32}\leq \frac{m(U^i)}{m(U)} \le \frac{3}{4}.\] 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.
2.0.0.6 Constructing an Approximation Preserving Sequence.
Starting with \(U_0=V\), we iterate:
Run threshold checking on \(U_j\).
If \(m(U_j) < \tau\), stop and set \(U_\kappa = U_j\).
Otherwise, sparsify \(U_j\) and select an approximation preserving subset \(U_{j+1}\).
This yields a sequence \[V= U_0 \supseteq U_1 \supseteq \cdots \supseteq U_\kappa,\] where, with probability at least \(4/5\), each \(U_j\) satisfies \[\frac{1}{32}\leq \frac{m(U_j)}{m(U_{j-1})} \le \frac{3}{4}.\]
2.0.0.7 Final Estimation.
For each \(j\in [\kappa]\), define \[p_j = \frac{m(U_j)}{m(U_{j-1})}.\] Then we have the identity \[m= \frac{m(U_\kappa)}{\prod_{j=1}^{\kappa} p_j}.\] Instead of estimating each \(m(U_j)\) from scratch, we estimate only the ratios \(p_j\). Because each \(p_j = \Omega(1)\) by construction of the approximation preserving sequence, we can estimate each \(p_j\) using small number of queries, independent of \(n\) or \(m(U_j)\). This yields an estimate \(\widehat{p}_j\) satisfying the following with desired probability. \[\widehat{p}_j = (1\pm \varepsilon/O( \sqrt{\kappa}))\,p_j\]
Note that the entire approximation preserving subsequence is constructed a priori. Hence, we know \(\kappa\) during the final estimation phase that we use to fix the approximation parameters appropriately for the multiplicative estimation for each \(p_j, j \in [\kappa]\). Let \(\widehat{m}(U_\kappa)\) be the estimate obtained via the birthday-based estimator. Our final output is \[\widehat{m} = \frac{\widehat{m}(U_\kappa)}{\prod_{j=1}^{\kappa} \widehat{p}_j}.\] A careful multiplicative error analysis shows that this is a \((1\pm \varepsilon)\)-approximation to \(m\).
2.0.0.8 Proof Roadmap.
The correctness proof proceeds in the following stages:
Threshold correctness: We show that the collision-based test reliably distinguishes between \(m(U)<\tau\) and \(m(U)\ge 8\tau\), and that the birthday-paradox estimator is accurate when \(m(U)<\tau\).
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 \(p_j\) with appropriately scaled approximation error. Then, we bound the cumulative error from estimating all \(p_j\) and show that the product estimator preserves a global \((1\pm \varepsilon)\) approximation.
Complexity analysis: We show that \(\mathbb{E}[\kappa] = O(\log m)\) and that the total query complexity is dominated by estimating the \(p_j\)’s, yielding an overall expected complexity of \(\widetilde{O}(\log^2 m/\varepsilon^2)\).
2.0.0.9 Outline
We begin in 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 4, we describe the algorithm for constructing an approximation-preserving subsequence. In 4.1, we establish how graph sparsification yields an approximation-preserving subset, and use this result in 4.2 to construct an approximation-preserving subsequence. Finally, in 5, we present the complete algorithm for edge estimation.
3 Threshold checking↩︎
Let a fixed threshold (\(\tau\geq 1\)) be given. We consider the following threshold-checking problem: given a subset of vertices \(U \subseteq V\), determine whether \(m( U ) < \tau\). If this condition holds, the goal is to estimate the \((1 \pm \varepsilon)\) approximation of \(m( U )\).
To address this task, we present two algorithms IsCollision and BirthdayEstimate based on the birthday paradox techniques [4]. IsCollision distinguishes between the cases \(m( U ) < \tau\) or \(m( U ) \geq 8\tau\) ([lemma:32collision32detection]). BirthdayEstimate outputs an \((1 \pm \varepsilon)\) approximation of \(m( U )\), if \(m( U ) < \tau\) ([lemma:32birthdayestimate]). The
corresponding guarantees are stated below. For details, refer to Appendix 7.
lemmaisollison For a subset \(U \subseteq V\) and a threshold \(\tau\geq 1\), the following statements hold for IsCollision with probability at least \(1 - \delta\):
If \(m( U ) \leq \tau\), then \(\texttt{IsCollision}{}\) outputs \(1\).
If \(m( U ) \geq 8 \tau\), then \(\texttt{IsCollision}{}\) outputs \(0\).
The number of ISC queries made is \(O( \sqrt{ \tau} \log ( \delta^{ -1} ))\)
Suppose that a collision is detected, i.e., IsCollision outputs \(1\). We can obtain a \((1 \pm \varepsilon)\)-approximation of \(m(U)\)
using additional ISC queries. This estimation procedure is implemented in BirthdayEstimate.
lemmabirth For a subset \(U \subseteq V\), threshold \(\tau\geq 1\) and approximation error \(\varepsilon> 0\). If \(m( U ) \leq \tau\), then BirthdayEstimate outputs an \((1 \pm \varepsilon)\) estimate of \(m( U
)\) with probability at least \(\frac{ 15 }{ 16 }\). The number of ISC query made is \(\Theta\left({ \varepsilon^{-1} \sqrt{\tau} }\right)\).
4 Sparsification↩︎
In this section, we will describe a procedure to generate an approximation preserving sequence (formally defined below) \(U_0, \ldots, U_\kappa\) with probability at least \(7/8\). Moreover, the expected query complexity of the procedure is \(O(\log^2 m)\).
Definition 1 (Approximation preserving subset). For \(U,U' \subset V\) such that \(U' \subseteq U\), we say that \(U'\) is an approximation preserving subset of \(U\) if \[\frac{1}{32} \le \frac{m(U')}{m(U)}\le \frac{3}{4}.\]
Definition 2 (Approximation preserving sequence). For a sequence \(U_0, U_1, \ldots, U_\kappa \subseteq V\) with \(U_0 \supseteq U_1 \supseteq \ldots \supseteq U_\kappa\), We say that \(U_0, U_1, \ldots, U_\kappa\) is an approximation preserving sequence if \(U_{i-1}\) is an approximation preserving subset of \(U_i\) for all \(i \in [\kappa]\).
Formally, we will prove the following lemma in this section.
Lemma 1 (Approximate sequence lemma). There exists an algorithm that outputs an approximation preserving sequence \(U_0, U_1, \ldots, U_\kappa\) with probability at least \(\frac{4}{5}\). The expected value of \(\kappa\) is \(O(\log m)\), and the expected number of ISC queries made is \(O(
\log^2 m)\).
To prove the above lemma, we start with \(U_0 = V\), and find \(U_i\) iteratively. Informally speaking, we stop with \(U_\kappa\) when \(m(U_\kappa)\) is small enough. In 4.1, we discuss a procedure (ApproxSubset corresponding to 2) 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 4.2, we describe the procedure (ApproxSequence
corresponding to [lemma:32subsequence]) that uses IsCollision and ApproxSubset iteratively to generate an approximation
preserving subsequence \(U_0, \ldots, U_\kappa\). Essentially, IsCollision is used to determine whether the number of edges in the current subset \(U_i\) is small or large and
ApproxSubset is used to generate a good subset as long as \(m(U_i)\) is large.
4.1 Procedure to find approximate preserving subset↩︎
In this section, we describe the procedure ApproxSubset (see 1) for finding the approximation preserving subset \(U' \subseteq U\), for any given \(U\) and prove its guarantee.
Formally, we will prove the following.
Lemma 2 (Approximate subset lemma). Let \(\zeta_\mathrm{sp}\) be a suitably large constant. Consider ApproxSubset that takes \(U \subseteq V\) as input and produces
\(U' \subseteq U\) as the output.
\(\mathop{\mathrm{\mathbb{E}}}[m(U')] \leq m(U)/2\);
If \(m(U) \geq \zeta_\mathrm{sp}\), with probability \(1-\delta-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 \(U^1\) and \(U^2\) (see [lemma:32graph32sparsification32for32k3261322]). When \(m( U )\) is large enough, this partition guarantees the existence of \(U^i\) such that \(m( U^i )\) is a constant fraction of \(m( U )\) ([lemma:32spasification32k3261322]). In the second step, we identify such an approximation-preserving subset from \(U^1\) and \(U^2\) ([lemma:32addestimation]). Combining these results yields the proof of 2.
We prove the following variant of the graph sparsification result of Beame et al. [1].
lemmagraphsparsification For a given \(\delta\in (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 \(U^1\) and \(U^2\) be a uniformly random partition of \(V\). Then,
\(\mathop{\mathrm{\mathbb{E}}}[ m(U^1) + m(U^2)] = m(U)/2\);
\(\Pr\left[{ \left|{ m/2 - \sum_{ i = 1 }^{ 2 } m( U^i ) }\right| \geq c\sqrt{ m} \log \left({ m/ \delta}\right) }\right] \leq \delta\).
We will need the following lemma to prove the above graph sparsification lemma.
Lemma 3. Let \(A\) be a set of \(\ell\) elements. For every element \(t \in A\), one assigns a color independently and uniformly from \(\left\{{1, 2}\right\}\). Let \(C^{(i)}\) be the number of vertices in \(A\) with color \(i\), for any \(i \in \left\{{ 1, 2 }\right\}\). Then for \(\delta\in (0, 1)\), we have \[\Pr \left[{ \left|{ C^{(1)} - C^{(2)} }\right| \geq \sqrt{ { 6\ell\log (4\delta^{-1}) } }}\right] \leq \delta\text{ and } \mathop{\mathrm{\mathbb{E}}}\left[{ \left|{ C^{(1)} - C^{(2)} }\right| }\right] \leq \sqrt{ \ell }\]
Proof. For \(t \in A\), let \(X_t\) be the indicator random variable that is \(1\) if \(t\) is assigned color \(1\) and \(0\) otherwise. Then, \(C^{(1)} = \sum_{t \in A} X_t\) and \(\mathop{\mathrm{\mathbb{E}}}\left[{ C^{(1)} }\right] = \ell/2\). Using Chernoff’s inequality (Lemma 9) with \(\varepsilon= \sqrt{ (6 / \ell) \log (4 / \delta) }\), we have \[\label{ineq:32color321} \Pr \left[{ \left|{ C^{(1)} - \frac{ \ell }{ 2 } }\right| > \frac{\varepsilon\ell }{ 2 } }\right] \leq 2 \exp \left({ \frac{ 6 \log (4\delta^{-1})}{ \ell } \cdot \frac{ \ell }{ 6 } }\right) \leq \frac{ \delta}{ 2 }\tag{1}\] Similarly, we can have the same bound for color \(2\). \[\label{ineq:32color322} \Pr \left[{ \left|{ C^{(2)} - \frac{ \ell }{ 2 } }\right| > \frac{\varepsilon\ell }{ 2 } }\right] \leq \frac{ \delta}{ 2 }\tag{2}\] Observe that \(\left|{C^{(1)} - C^{(2)}}\right| \leq \left|{ C^{(1)} - (\varepsilon\ell/2) }\right| + \left|{ C^{(2)} - (\varepsilon\ell/2)}\right|\). Therefore \[\Pr \left[{ \left|{C^{(1)} - C^{(2)}}\right| > \varepsilon\ell }\right] \leq \delta\]
For \(t \in A\), let \(Y_t\) be a random variable that is \(1\) if \(t\) is assigned the color \(1\) and \(-1\) otherwise. Then \(C^{(1)} - C^{(2)} = \sum_{ t \in A} Y_t = Y\). We have that \(\Pr \left[{ Y_t = 1 }\right] = \Pr \left[{ Y_t = 1 }\right] = 1/2\), then \[\mathop{\mathrm{\mathbb{E}}}[ Y_t ] = 0 \text{ and } \mathop{\mathrm{\mathbb{E}}}[ Y_t^2] = 1\] By the independence of \(Y_t\), we get \[\mathop{\mathrm{\mathbb{E}}}[ Y^2 ] = \sum_{ t \in A } \mathop{\mathrm{\mathbb{E}}}[ Y_t^2 ] + \sum_{ u \neq v} \mathop{\mathrm{\mathbb{E}}}[ Y_u Y_v ] = \ell\] Finally, we have \(\mathop{\mathrm{\mathbb{E}}}[ \left|{Y}\right| ] \leq \sqrt{ \mathop{\mathrm{\mathbb{E}}}[ \left|{ Y }\right|^2 ] } = \sqrt{ \mathop{\mathrm{\mathbb{E}}}[ { Y }^2 ] } \leq \sqrt{ \ell }\). ◻
We now prove [lemma:32graph32sparsification32for32k3261322].
Proof of Lemma [lemma:32graph32sparsification32for32k3261322]. Let each vertex \(t \in V\) be associated with a random variable \(Y_t \in \left\{{1,2}\right\}\) such that \(\Pr\left[{Y_t = 1}\right] = \frac{1}{2}\). For \(i \in \left\{{1,2}\right\}\), define \(U^i = \left\{{ t \in V\mid Y_t = i }\right\}\) and \[f\left({Y_1, \ldots, Y_{n}}\right) = m(U^1) + m(U^2).\] A fixed edge is counted by \(f\) if and only if both its endpoints are assigned the same label, which occurs with probability \(\frac{1}{2}\). Therefore, \(\mathop{\mathrm{\mathbb{E}}}[f] = m/ 2\).
Consider the Doob martingale \(X_0, X_1, \ldots, X_n\), where \(X_t = \mathop{\mathrm{\mathbb{E}}}[f(Y_1, \ldots, Y_n)|Y_1, \ldots, Y_t]\). For a fix values of \(Y_1, \ldots, Y_{t-1}\), we have, \[\begin{align} X_{t-1} = \frac{ g(1) + g(2) }{ 2 }, \text{ where } g(i) = \mathop{\mathrm{\mathbb{E}}}[f(Y_1, \ldots, Y_n)| (Y_1, \ldots, Y_{t-1}) \cap (Y_t = i)] \end{align}\] Since, \(X_t\) is either \(g(1)\) or \(g(2)\), we have \(\left|{X_t - X_{t-1}}\right| \leq \left|{g(1) - g(2)}\right|\). Let \(N(t)\) be the set of neighbours of the vertex \(t\) and \(\deg(t) = \left|{ N(t) }\right|\). Let \(N_{ < t} = N(t) \cap [t-1]\) and \(N_{ > t} = N(t) \cap \left\{{(t + 1), \ldots, n}\right\}\). Let \(C_{<t}^{(i)}\) and \(C_{>t}^{(i)}\) be the number of vertices in \(N_{ < t}\) and \(N_{ > t}\) respectively. So, \[\Delta_t = \left|{g(1) - g(2)}\right| = \left|{ C_{<t}^{(1)} + \mathop{\mathrm{\mathbb{E}}}\left[{ C_{>t}^{(1)} \mid Y_t = 1}\right] - C_{<t}^{(2)} - \mathop{\mathrm{\mathbb{E}}}\left[{ C_{>t}^{(2)} \mid Y_t = 2}\right] }\right|\] 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 \(\left\{{(t + 1), \ldots, n}\right\}\) or both of its vertices in \(\left\{{(t + 1), \ldots, n}\right\}\) will have the same contribution. Using Lemma 3, we have with probability at least \(1 - \delta'\), \[\Delta_t \leq \sqrt{ 6 { \deg(t) } \log \frac{ 4 }{ \delta' } } + \sqrt{ \deg(t) } \leq 2c\sqrt{ \deg(t) \log \frac{ 1 }{ \delta' } } = c_t\] Let \(\mathcal{B}\) be the event that there exits a \(t\) such that \(\Delta_t > c_t\). Let \(n_a\) be the set of active vertices (vertices with degree at least \(1\)). Therefore, using union bound \(\Pr[\mathcal{B}] \leq 4 n_a \delta' \leq 4 m\delta'\).
Let \(S = \sum_{ t = 1}^nc_t^2 = \sum_{ t = 1}^n4 c^2 \deg(t) \log( 4 / \delta') = O( m\log( 1 / \delta' ) )\) and \(s = c\sqrt{m} \log( 1 / \delta' )\). Using 11, we have \[\Pr \left[{ \left|{ f - \frac{ m}{ 2 }}\right| > s }\right] \leq 2 \exp \left({ - \frac{ s^2 }{ 2S } }\right) + \Pr \left[{ \mathcal{ B } }\right] \leq \delta' + 4 m\delta'\] Replacing \(\delta'\) with \(\delta/ cm\) for a sufficiently large constant, we obtain \[\Pr\left[{ \left|{ \frac{ m}{ 2 } - \sum_{ i = 1 }^{ 2 } m( U^i ) }\right| \geq c\sqrt{ m} \log \left({\frac{ m}{ \delta}}\right) }\right] \leq \delta\] which completes the proof. ◻
corollary For a subset \(U \subseteq V\), suppose there exists a sufficiently large absolute constant \(\zeta_\mathrm{sp}\) such that \(m(U) \ge \zeta_\mathrm{sp}\). Let \(U^1\) and \(U^2\) be a uniformly random partition of \(U\). Then, with probability at least \(1 - \frac{1}{m(U)}\), the following hold.
\(\frac{ m( U^1 ) }{ m( U ) } \geq 1/8\) or \(\frac{ m( U^2 ) }{ m( U )} \geq 1/8\);
\(\frac{ m( U^1 ) }{ m( U ) } \leq 3/4\) and \(\frac{ m( U^2 ) }{ m( U )} \leq 3/4\).
Proof. Taking \(\zeta_\mathrm{sp}\) to be sufficiently large, we have \(c \sqrt{m(U)} \log m(U) \leq \frac{m(U)}{4}\). So, by taking \(\delta=1/m(U)\) in Lemma [lemma:32graph32sparsification32for32k3261322], we
\[\Pr\!\left[{ \frac{m(U)}{4} \le \sum_{i=1}^{2} m(U^i) \le \frac{3\,m(U)}{4} }\right] \ge 1 - \frac{1}{m(U)} \, .\]
This implies that, with probability at least \(1 - 1/m(U)\), at least one of \(m( U^1 ) / m( U )\) and \(m( U^2 ) / m( U )\) is at least \(1/8\), and both \(m( U^1 ) / m( U )\) and \(m( U^2 ) / m( U )\) are at most \(3/4\). ◻
To prove the guarantees of ApproxSubset described in 1, we need [lemma:32addestimation].
lemmaaddest With probability at least \(1 - \delta\), the following statements hold for ApproxSubset
If \(\frac{ m( U^i ) }{ m( U ) } \geq \frac{ 1 }{ 8 }\), then \(\widehat{p}( U^i ) \geq \frac{ 1 }{ 16 }\).
If \(\frac{ m( U^i ) }{ m( U ) } < \frac{ 1 }{ 32 }\), then \(\widehat{p}( U^i ) < \frac{ 1 }{ 16 }\).
The number of \(\texttt{ISC}\) queries made is \(O\left({ \log ( \delta^{-1} ) }\right)\).
Proof. Consider a subset \(U^i \subseteq U\) for any \(i \in \{1,2\}\). For each sampled edge, define the indicator random variable \[X_j = \begin{cases} 1 & \text{if thej^{\text{th}}sampled edge lies inU^i ,} \\ 0 & \text{otherwise.} \end{cases}\] Observe that \(\mathop{\mathrm{\mathbb{E}}}[X_j] = \frac{m(U^i)}{m(U)}\).
Define the fraction of sampled edges that belong to \(U^i\) by \(X = \frac{1}{\left|{S}\right|}
\sum_{j \in [\left|{S}\right|]} X_j.\) where \(S\) is the multiset of sampled edges (Line [addestimation:32line322]) obtained via ISC queries on \(U\). Note that \(X = \widehat{p}(U^i)\) and hence \[\mathop{\mathrm{\mathbb{E}}}[\widehat{p}(U^i)]
= \frac{1}{\left|{S}\right|}
\sum_{j \in [\left|{S}\right|]}\mathop{\mathrm{\mathbb{E}}}[X_j]
= \frac{m(U^i)}{m(U)}
= \frac{m(U^i)}{m(U)}.\]
Applying Hoeffding’s bound (10), we get \[\Pr\!\left( \left| \widehat{p}(U^i) - \frac{m(U^i)}{m(U)} \right| \ge \tfrac{1}{32} \right) \le \exp\!\left( -\frac{\left|{S}\right|}{2}\cdot (1/32)^2 \right) \le \delta/2.\] The last inequation holds since \(\left|{S}\right|=O(\log 1/\delta)\). Using the union bound over \(i\in \{1,2\}\), we get the desired result. ◻
We now give the proof of 2, using [lemma:32graph32sparsification32for32k3261322], [lemma:32spasification32k3261322] and [lemma:32addestimation]
Proof of 2. In ApproxSubset, the set \(U\) is partitioned uniformly at
random into \(U^1\) and \(U^2\). From [lemma:32graph32sparsification32for32k3261322](i), \[\mathop{\mathrm{\mathbb{E}}}[m(U^1)+m(U^2)] = m(U)/2.\] Since \(U'\) is either \(U^1\) or \(U^2\), it follows that \(\mathop{\mathrm{\mathbb{E}}}[m(U')] \le m(U)/2\), proving
part (i).
We now prove part (ii). Let \(\mathcal{E}_{\text{apx}}\) denote the event that \(U'\) is an approximation-preserving subset of \(U\), that is, \(1/32 \leq m(U')/m(U)\leq 3/4\). Let \(\mathcal{E}\) be the event that at least one of \(m( U^1 ) / m( U )\) and \(m( U^2 ) / m( U )\) is at least \(1/8\), and both \(m( U^1 ) / m( U )\) and \(m( U^2 ) / m( U )\) are at most \(3/4\). By [lemma:32spasification32k3261322], \[\Pr[\mathcal{E}] \ge 1 - \frac{1}{m(U)}.\]
Let us condition on the event \(\mathcal{E}\). It suffices to bound \(\Pr[\mathcal{E}_{\text{apx}} \mid \mathcal{E}]\). Then both \(m( U^1 ) / m( U )\) and \(m( U^2 ) / m( U )\) are at most \(3/4\), and at least one of \(m( U^1 ) / m( U )\) and \(m( U^2 ) / m( U )\) is at least \(1/8\); w.l.o.g.assume \(m( U^1 ) / m( U ) \ge 1/8\). If \(m( U^2) / m( U ) \ge 1/32\), then since \(U'\in\{U^1,U^2\}\) we immediately have \(1/32 \le m(U')/m(U) \le 3/4\), that is, \(\Pr[\mathcal{E}_{\text{apx}}\mid\mathcal{E}]=1\). Otherwise \(m( U^2) / m( U )<1/32\). By [lemma:32addestimation], with probability at least \(1-\delta\), we obtain \(\widehat{p}(U^1)\ge 1/16\) and \(\widehat{p}(U^2)<1/16\), implying \(U'=U^1\). Consequently \(1/32 \le m(U')/m(U) \le 3/4\) holds with probability at least \(1-\delta\) conditioned on \(\mathcal{E}\). Thus in all cases \[\Pr[\mathcal{E}_{\text{apx}}\mid\mathcal{E}] \ge 1-\delta.\]
Therefore, \[\Pr[\mathcal{E}_{\text{apx}}] \ge \Pr[\mathcal{E}] \cdot \Pr[\mathcal{E}_{\text{apx}}\mid\mathcal{E}] \ge 1 - \frac{1}{m(U)} - \delta.\] ◻
4.2 Procedure to find approximate preserving sequence↩︎
We now describe the algorithm ApproxSequence (see 2), which constructs the sparsification sequence used by the main estimator.
lemma Consider ApproxSequence as described in 2. With probability at least \(\frac{4}{5}\), it
outputs an approximation preserving sequence \(U_1, U_2, \ldots, U_\kappa\) such that \(m(U_{\kappa})\leq 8\zeta_\mathrm{sp}\). Here \(\zeta_\mathrm{sp}\) is
given large constant. The number of \(\texttt{ISC}\) queries made is \(O( \kappa^2 )\).
Proof. Correctness: Let us consider the event \(\mathcal{E}_{\text{col}}\) that denotes
There does not exist a \(j\) such that the algorithm goes to the next iteration if \(m(U_j) \leq \zeta_\mathrm{sp}.\)
For any \(j\) such that the algorithm goes to the next iteration if \(m(U_j) \geq 8\zeta_\mathrm{sp}.\)
The probability of \(\mathcal{E}_{\text{col}}\) is lower bounded by IsCollision succeeds in all iterations during the run of the algorithm. Using the union bound, we have \[\Pr[\mathcal{E}_{\text{col}}]
\ge 1 - \sum_{i = 1}^{\infty} \frac{1}{2^{i+5}}
\ge 1 - \frac{1}{2^5} \sum_{i = 1}^{\infty} \frac{1}{2^{i}}
\ge 1 - \frac{1}{16}
= \frac{15}{16}.\]
Let us continue the argument under the conditional space that \(\mathcal{E}_{\text{col}}\) has occurred.
We assume \(m(U_0) = m\) is sufficiently large; hence, the algorithm does not terminate in the first iteration, given that \(\mathcal{E}_{\mathrm{col}}\) has occurred. Let \(U_0,\ldots, U_\kappa\) be the output of the algorithm, where \(\kappa\) is a positive integer. Conditioned on the event \(\mathcal{E}_{\text{col}}\), we have \(m(U_j) \geq \zeta_\mathrm{sp}\) for every \(j \leq \kappa - 1\).
We prove the claim by induction on \(\kappa\). For each \(j \ge 0\), let \(\mathcal{E}_j\) denote the event which is that the algorithm executes iteration \(j\) and either terminates with, \(m(U_j) \leq 8\zeta_\mathrm{sp}\), or it produces an approximation preserving subset \(U_{j+1}\) such that \(m(U_{j+1}) \leq \frac{3m(U_j)}{4}\).
Let \(\mathcal{E}_{\le j}\) denote the event that \(\mathcal{E}_i\) occurs for all \(i \in [j]\), that is, \[\mathcal{E}_{\le j} \;=\; \bigcap_{i=1}^{j} \mathcal{E}_i .\] Equivalently, \(\mathcal{E}_{\le j}\) is the event that the algorithm runs for \(j\) iterations, such that \(U_0, \ldots, U_{j}\) is an approximation preserving sequence, and at iteration \(j\) either it produces \(U_{j+1}\), an approximation preserving subset of \(U_{j}\) such that \(m(U_{j+1}) \leq \frac{3m(U_j)}{4}\), or the algorithm terminates with \(m(U_j) \leq 8\zeta_\mathrm{sp}\).
The induction hypothesis is that \[\Pr[\mathcal{E}_{\le j}] \;\ge\; 1 - \delta_{\leq j},\] where \[\delta_i \;=\; \frac{1}{m(U_i)} + \frac{1}{2^{i+5}} , \qquad \text{and} \qquad \delta_{\le j} \;=\; \sum_{i=0}^{j} \delta_i .\]
We first prove the base case. That is, \(\Pr[\mathcal{E}_{0}]\geq 1-\delta_0\). Recall that we assume that \(m(U_0) = m\) is sufficiently large. Moreover, we assume that event \(\mathcal{E}_{\text{col}}\) has occurred and algorithm produced a sequence \(U_0, \ldots,U_\kappa\) with \(\kappa\geq 1\). So, \(\mathcal{E}_0\) occurs if ApproxSubset reports an approximate preserving subset \(U_{j+1}\). By 2, this occurs with probability at least \(1-\delta_0\).
For the inductive step, we mainly show that \(\Pr[\mathcal{E}_j~|~\mathcal{E}_{\leq j-1}] \geq 1-\delta_j\) for \(j\geq 1\). Let us argue that it is sufficient. Note that \(\delta_{\le j} = \delta_{\le j-1} + \delta_j\) for \(j\geq 1\) and \[\Pr[\mathcal{E}_{\le j}] = \Pr[\mathcal{E}_{\le j-1} \cap \mathcal{E}_j] = \Pr[\mathcal{E}_{\le j-1}]\cdot \Pr[\mathcal{E}_j \mid \mathcal{E}_{\le j-1}] .\]
By the induction hypothesis, \(\Pr[\mathcal{E}_{\le j-1}] \ge 1 - \delta_{\le j-1}.\) We will show that \[\label{eqn:ind} \Pr[\mathcal{E}_j \mid \mathcal{E}_{\le j-1}] \ge 1 - \delta_j .\tag{3}\]
Therefore, \[\begin{align} \Pr \left[ \mathcal{E}_{\le j} \right] &= \Pr \left[ \mathcal{E}_{\le j-1} \right] \cdot \Pr \left[ \mathcal{E}_j \mid \mathcal{E}_{\le j-1} \right] \\ &\ge (1-\delta_{\le j-1})(1-\delta_j) \\ &\ge 1-\delta_{\le j-1}-\delta_j \\ &= 1-\delta_{\le j}. \end{align}\]
Consider any \(j\) with \(1\leq j \leq \kappa-1\). Under the conditional space \(\mathcal{E}_{\text{col}}\) and along with the fact that we assume \(m(U_0) = m\) is sufficiently large, \(m(U_j) \geq \zeta_\mathrm{sp}\) for each \(j \leq \kappa-1\).
We consider two cases: \(m(U_j) \geq 8\zeta_\mathrm{sp}\), and \(\zeta_\mathrm{sp}\leq m(U_j) \leq 8\zeta_\mathrm{sp}\), and analyse them individually.
4.2.0.1 Case \(1\): \((m(U_j) > 8\zeta_\mathrm{sp})\).
Recall that we are assuming that the event \(\mathcal{E}_{\text{col}}\) has occurred. So, ApproxSequence does not terminate after executing IsCollision and execute ApproxSubset.
Moreover it produces an approximate preserving subset \(U_{j+1}\) with \(m(U_{j+1}) \leq \frac{3m(U_j)}{4}\), that is event \(\mathcal{E}_j\) occurs, when
ApproxSubset reports an approximate preserving subset \(U_{j+1}\) with \(m(U_{j+1}) \leq \frac{3m(U_j)}{4}\). By 2 and Line 7 of ApproxSequence, this occurs with probability at least \(1-\delta_j\) where,
\[\delta_j = \frac{1}{m(U_j)} + \frac{1}{2^{j+5}}\]
Hence, \[\Pr[\mathcal{E}_j \mid \mathcal{E}_{\le j-1}] \ge 1-\delta_j^{(1)},\]
4.2.0.2 Case \(2\): \(( \zeta_\mathrm{sp}\leq m(U_j) \leq 8\zeta_\mathrm{sp})\).
In this case, we show that \[\Pr\!\left[\mathcal{E}_j \mid \mathcal{E}_{\le j-1} \right] \ge 1-\delta_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 \(\mathcal{E}_j\) together with the fact that \(m(U_j) \le 8\zeta_\mathrm{sp}\). In the latter case,
ApproxSequence produces an approximate preserving subset \(U_{j+1}\) of \(U_j\) provided that ApproxSubset returns an approximate preserving subset \(U_{j+1}\). By 2, this occurs with probability at least \(1-\delta_j\), where \[\delta_j
\le
\frac{1}{m(U_j)} + \frac{1}{2^{j+5}
}.\]
Hence, \[\Pr\!\left[ \mathcal{E}_j \mid \mathcal{E}_{\le j-1} \right] \ge 1 - \delta_j .\]
We are done with the proof of the inductive step. We summarize the above discussion as follows. \(\Pr[\mathcal{E}_{\text{col}}]\geq 15/16\). When the event \(\mathcal{E}_{\text{col}}\) occurs, \(\Pr[\mathcal{E}_{j}~|~\mathcal{E}_{j-1}] \geq 1-\delta_j\) for all \(j \geq 0\). Moreover, \(\Pr[\mathcal{E}_{\leq j}] \geq 1-\delta_{\leq j}\) for all \(j \geq 0\). Recall that the algorithm outputs a sequence \(U_0, \ldots, U_{\kappa-1}\). The events \(\mathcal{E}_{\text{col}}\) and \(\mathcal{E}_{\leq \kappa-1}\) occur with probability at least \[\Pr[\mathcal{E}_{\text{col}}] - \delta_{\leq \kappa-1}.\] Hence, the following facts hold with the same probability:
\(U_0, \ldots, U_\kappa\) is an approximate preserving sequence, that is, \[\frac{1}{32} \leq \frac{m(U_{i})}{m(U_{i-1})} \leq \frac{3}{4},~where~i \in [\kappa].\]
\(m(U_j) \geq \zeta_\mathrm{sp}\) for each \(j \leq \kappa- 1\), and \(m(U_\kappa) \leq 8\zeta_\mathrm{sp}\).
Note that ApproxSequence produces an approximation-preserving sequence \(U_1, U_2, \cdots, U_\kappa\) such that \(m(U_{\kappa}) \leq 8\zeta_\mathrm{sp}\) whenever both of the
above conditions hold. This occurs with probability at least \(1/5\), provided \(\delta_{\kappa-1} \leq 1/10\), since \(\Pr[\mathcal{E}_{\text{col}}] \geq
15/16\).
We complete the proof of correctness of ApproxSequence by showing that \(\delta_{\kappa-1} \leq 1/10\).
\[\begin{align} \delta_{\leq \kappa- 1} = \sum_{i=0}^{\kappa- 1} \frac{1}{m(U_j)} + \frac{1}{2^{j+5}} \leq \sum_{i=0}^{\infty} \frac{1}{2^{j+4}} + \sum_{i=0}^{\kappa- 1} \frac{1}{m(U_j)} \leq \frac{1}{16} + \sum_{i=0}^{\kappa- 1} \frac{3^{\kappa- 1 - i}}{4^{\kappa- 1 - i}\zeta_\mathrm{sp}}. \end{align}\]
The last inequation holds since \(m(U_{\kappa- 1}) \geq \zeta_\mathrm{sp}\) and \(m(U_i) \leq \frac{3m(U_{i-1})}{4}\) for all \(i \in [\kappa- 1]\). We obtain the bound of \(\delta_{\leq \kappa- 1}\) as below: \[\begin{align} \delta_{\leq \kappa- 1} = \frac{1}{16} + \frac{1}{\zeta_\mathrm{sp}} \sum_{i=0}^{\kappa- 1} \frac{3^{\kappa- 1 - i}}{4^{\kappa- 1 - i}} = \frac{1}{16} + \frac{1}{\zeta_\mathrm{sp}} \sum_{i=0}^{\kappa- 1} \frac{3^{i}}{4^{i}} \leq \frac{1}{16} + \frac{2}{\zeta_\mathrm{sp}}\leq \frac{1}{10}. \end{align}\] Here we have used the fact that \(\zeta_\mathrm{sp}\) is a large constant.
4.2.0.3 Query Complexity:
From Lemma [lemma:32collision32detection] and [lemma:32addestimation], the number of ISC queries made by IsCollision (for a constant threshold \(\tau= \zeta_\mathrm{sp}\)) and
ApproxSubset over \(\kappa\) iterations is, \[\begin{align} O\left({\sum_{ j = 1 }^{\kappa} \log( 2^{ \kappa+ 5 } ) }\right) = O\left({\kappa^2}\right)
\end{align}\] ◻
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 5 (that uses ApproxSequence as a subroutine), we show that the query complexity of the full algorithm is \(O(\kappa^2 \cdot \log \kappa)\), where \(\kappa\) is the number of iterations of ApproxSequence. The following lemmas will be useful in establishing the final query complexity in 5.
Lemma 4. \(\mathop{\mathrm{\mathbb{E}}}[\kappa]=O(\log m)\), \(\mathop{\mathrm{\mathbb{E}}}[\kappa^2]=O(\log^2 m)\), and \(\mathop{\mathrm{\mathbb{E}}}[\kappa^2 \log \kappa]=O(\log^2 m\cdot \log \log m)\).
From [lemma:32subsequence] and 4, 1 follows. In the rest of the section, we prove [lemma:32subsequence] and 1.
Proof. Here, we prove that \[\mathop{\mathrm{\mathbb{E}}}\left[{ \kappa^2 \log \kappa}\right] = O( \log^2 m\log \log m)\] The remaining bounds follow similarly.
We want to analyse \(\mathop{\mathrm{\mathbb{E}}}[\kappa^2 \log \kappa]\) where the expectation is over the distribution of \(\kappa\) 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 \(\zeta_\mathrm{sp}\) edges. Formally, we define \(t^*\) as the time \(t\) such that \(m(U_{t}) \leq \zeta_\mathrm{sp}\), and \(m(U_{t-1}) > \zeta_\mathrm{sp}\). If this is not the case, i.e. when \(m(U_t) > \zeta_\mathrm{sp}\) holds throughout the algorithm, we show that \(\kappa= O( \log m)\).
First, we bound the expectation of \(m(U_t)\) for some \(t \in [\kappa]\). By 2, we have \[\begin{align} \mathop{\mathrm{\mathbb{E}}}\left[m(U_t)~|~m(U_{t-1})\right] \leq \frac{m(U_{t-1})}{2}. \end{align}\] By a inductive argument, and the fact that \(m(U_0) = m\), we have \[\begin{align} \mathop{\mathrm{\mathbb{E}}}[m(U_t)]=\mathop{\mathrm{\mathbb{E}}}[\mathop{\mathrm{\mathbb{E}}}[m(U_{t})~\mid~m(U_{t-1})]] \leq \frac{\mathop{\mathrm{\mathbb{E}}}[m(U_{t-1})]}{2} \leq \ldots \leq \frac{m}{2^t} \label{Eq:32Edge32bound32at32step32t} \end{align}\tag{4}\] Now, when \(m(U_j) > \zeta_\mathrm{sp}\) holds throughout the algorithm, we have \[\zeta_\mathrm{sp}< \mathop{\mathrm{\mathbb{E}}}\left[{ m( U_\kappa) }\right] \leq \frac{ m}{ 2^{\kappa} } \implies \kappa= O ( \log m)\]
Hence, we now focus on the case when there exists a \(t^*\leq \kappa\). 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 \(\kappa^2 \log \kappa\)
given \(t^*\). \[\begin{align} \nonumber\mathop{\mathrm{\mathbb{E}}}\left[{ \kappa^2 \log \kappa\mid t^*}\right] &= \sum_{ j = 1
}^\infty j^2 \log j \Pr \left[{ \kappa= j \mid t^*}\right]\\\nonumber &= \sum_{ j = 1}^{t^*-1} j^2 \log j \Pr \left[{ \kappa= j \mid t^*}\right] + \sum_{ j = t^*}^\infty j^2\log j \Pr \left[{ \kappa= j \mid t^*}\right] \\\nonumber &= \sum_{ j =
t^*}^\infty j^2 \log j \Pr \left[{ \kappa= j \mid t^*}\right] &\text{(As t^*\leq \kappa)}\\\nonumber & \leq\sum_{ j = t^*}^\infty j^2 \log j \Pr \left[{ \kappa\geq j \mid t^*}\right]\\\nonumber & \leq \sum_{ j = t^*}^\infty \frac{ j^2 \log j
}{2^{j + 5}}\\ & = O\left({{{t^*}^2 \log t^*}}\right)\label{Eq:32Conditional32iteration32bound}
\end{align}\tag{5}\]
Now, we analyse the distribution of \(t^*\). We use 4 to obtain a bound on the probabilities of different values of \(t^*\). \[\begin{align} \nonumber\Pr \left[{ t^*= t }\right] \leq \Pr \left[{ t^*\geq t }\right] &\leq \Pr \left[{ m( U_{ t } ) > \zeta_\mathrm{sp}}\right]\\\nonumber &\leq \frac{ \mathop{\mathrm{\mathbb{E}}}[ m( U_{ t } ) ] }{ \zeta_\mathrm{sp}} &\text{Markov's Inequality (Lemma~\ref{Markov39s32Inequality})}\\ &\leq \frac{ m}{2^t \zeta_\mathrm{sp}} &\text{\Cref{Eq:32Edge32bound32at32step32t}}\label{Eq:32Markov32Edge32bound} \end{align}\tag{6}\] Now, we bound the expectation of \(\kappa^2 \log \kappa\). \[\begin{align} \mathop{\mathrm{\mathbb{E}}}[ \kappa^2 \log \kappa] &= \mathop{\mathrm{\mathbb{E}}}\left[{\mathop{\mathrm{\mathbb{E}}}\left[{ \kappa^2 \log \kappa\mid t^*}\right] }\right]\\ &= \mathop{\mathrm{\mathbb{E}}}[ {t^*}^2 \log t^*] &\text{(\Cref{Eq:32Conditional32iteration32bound})}\\ &= \sum_{j = 1}^\infty j^2 \log j \Pr[t^*= j]\\ &= \sum_{j = 1}^{2\log m} j^2 \log j \Pr[t^*= j] + \sum_{j = 2\log m+ 1}^\infty j^2 \log j \Pr[t^*= j]\\ &\leq 8\log^2m\log \log m\sum_{j = 1}^{2\log m} \Pr[t^*= j] + \sum_{2\log m}^\infty \frac{mj^2 \log j}{2^j\zeta_\mathrm{sp}} \\ &= O\left({{\log^2 m\log \log m}}\right) \end{align}\] which proves the desired result. ◻
1 follows from the algorithm ApproxSequence (2) along with [lemma:32subsequence] and 4.
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.
EdgeEstimation (4) begins by calling ApproxSequence which outputs an approximation preserving sequence \(U_1 , \ldots, U_\kappa\), where each \(p_i = m( U_i ) / m( U_{i-1} )\) is bounded below by a constant. This ensures that each ratio can be estimated efficiently. To estimate each \(p_i\), we use the subroutine
MulEstimation which returns an \((1 \pm \varepsilon)\)-approximation of \(p_i\) . The procedure MulEstimation is described in 3 and its guarantee is established in [lemma:32mulestimation].
lemmamulest For subsets \(U' \subseteq U \subseteq V\) and \(\varepsilon> 0\) , If \(p( U' ) = \frac{ m( U' ) }{ m( U ) } \geq \frac{ 1 }{ 32 }\), then MulEstimation outputs \(\widehat{p}( U' ) = ( 1 + x ) p( U' )\), where \(\mathop{\mathrm{\mathbb{E}}}[x] = 0\) and \(x \in (-\varepsilon, \varepsilon)\) with probability at least \(1 - \delta\). The number of ISC queries
made is \(O\left({ \log ( \delta^{-1} ) / \varepsilon^2 }\right)\).
Proof. Let \(X_j\) be the indicator random variable such that, \[X_j = \begin{cases} 1 & \text{If thej^{th}sampled edge is inU' } \\ 0 & \text{Otherwise } \end{cases}\] Define number of edges sampled that belong to \(U'\) is \(X = \sum_{ j \in [\left|{ S}\right|] } X_j\), where \(S\) is the multi-set of sampled edges (Line [addestimation:32line322]) and the expected size of \(X\) is \[\mathop{\mathrm{\mathbb{E}}}\left[{ X }\right] = \sum_{ j \in [\left|{S}\right|] } \mathop{\mathrm{\mathbb{E}}}\left[{ X_j }\right] = \left|{ S }\right| \cdot \frac{ m{ (U') }}{ m{ (U) } } = \left|{ S }\right| \cdot p( U' ) \geq \frac{ \left|{ S}\right| }{ 32 }\] Therefore, \[\begin{align} \mathop{\mathrm{\mathbb{E}}}[x] = \mathop{\mathrm{\mathbb{E}}}\left[{ \frac{\widehat{p}( U' )}{p( U' )}}\right] -1 = \frac{\mathop{\mathrm{\mathbb{E}}}[X]}{\left|{ S }\right| p( U' )} -1 = 0 \end{align}\] By the Chernoff Bound (see Lemma 9), we have \[\Pr[x \in (-\varepsilon, \varepsilon)] = \Pr\left[{ \widehat{p}(U') \in (1\pm\varepsilon)p(U') }\right] = \Pr\left[{ X \in (1\pm\varepsilon)\mathop{\mathrm{\mathbb{E}}}[X] }\right] \ge 1 - 2\exp\left({ - \frac{\varepsilon^2 \left|{S}\right|}{96} }\right) \ge 1 - \delta,\] where the last step uses \(\left|{S}\right|=O\left(\log (\delta^{-1})/\varepsilon^2\right)\). ◻
Now, we prove the guarantees of EdgeEstimation In particular, we prove the correctness of EdgeEstimation and its query complexity in 6 and 5, respectively.
Lemma 5. The expected query complexity of EdgeEstimation is \(O(\log^2 m \cdot \log \log m)\).
Proof. From Lemma [lemma:32mulestimation], the number of ISC queries made by MulEstimation in \(j\)-th iteration is \[\begin{align} O\left({ \frac{\log(16 \kappa)}{ \varepsilon'^2 } }\right) \text{where } \varepsilon' = \frac{ \varepsilon}{ 200 \sqrt{\kappa} }
\end{align}\] Summing over \(\kappa\) iterations, we get \[\begin{align} O\left({ \sum_{ j = 1 }^{ \kappa} \frac{ \log( \kappa) }{ \varepsilon'^2 } }\right) = O\left({\kappa^2 \frac{
\log \kappa}{ \varepsilon^2 } }\right)
\end{align}\] From Lemma [lemma:32subsequence], the number of ISC queries made by ApproxSequence is \(O( \kappa^2 )\). Finally, from Lemma [lemma:32birthdayestimate], the number of ISC queries made by
BirthdayEstimate is \(O\left({ { \sqrt{8\zeta_\mathrm{sp}} }/{ \varepsilon}}\right)= O(1/\varepsilon)\). Combining all contributions, the total number of ISC queries made by
EdgeEstimation is dominated by MulEstimation, and hence is, \(O( \kappa^2 \log \kappa/ \varepsilon^2)\). From 4, \[\mathop{\mathrm{\mathbb{E}}}[\kappa^2 \log \kappa] = O(\log^2 m\log \log m)\] which bounds the expected query complexity. ◻
Lemma 6. In EdgeEstimation, the estimate \(\widehat{m}\) is an \((1 \pm \varepsilon)\)-approximation to \(m\) with probability at
least \(3/4\).
Proof. Let \(\mathcal{E}_1 = \mathcal{E}_\mathrm{sub}\cap \mathcal{E}_\mathrm{bir}\), where \(\mathcal{E}_\mathrm{sub}\) be the event that ApproxSequence outputs an
approximation-preserving sequence \(U_1, U_2, \ldots, U_\kappa\) with \(m( U_\kappa) \leq 8 \zeta_\mathrm{sp}\). From [lemma:32subsequence] we have \(\Pr[\mathcal{E}_\mathrm{sub}] \geq 4/5\).
\(\mathcal{E}_\mathrm{bir}\) be the event that BirthdayEstimate outputs an \((1 \pm \varepsilon/3)\) approximation of \(m( U_\kappa)\) from
[lemma:32birthdayestimate]. Also, from [lemma:32birthdayestimate], we have \(\Pr[\mathcal{E}_\mathrm{bir}\mid \mathcal{E}_\mathrm{sub}] \geq 15/16\). Therefore, \[\Pr[\mathcal{E}_1] =
\Pr[\mathcal{E}_\mathrm{sub}]\Pr[\mathcal{E}_\mathrm{bir}\mid \mathcal{E}_\mathrm{sub}] \geq 1 - \left({ \frac{1}{5} + \frac{1}{16} }\right) \geq \frac{59}{80}\]
Let \(\mathcal{E}_2\) be the event that MulEstimation\(\left( U_i, U_{i - 1}, \varepsilon', { 1 }/{ 16 \kappa}\right)\) outputs \(\widehat{p_i}=(1 \pm x_i/4)p_i\) such that \(\mathop{\mathrm{\mathbb{E}}}[x_i]=0\) and \(x_i \in \left({ -4{\varepsilon'}, 4\varepsilon'}\right)\) for
all \(i \in [\kappa]\), where \(\varepsilon' = \frac{ \varepsilon}{ 200 \sqrt{ \kappa}}\) . Therefore, using Lemma [lemma:32mulestimation] and applying the union bound over all \(i \in [\kappa]\), \[\Pr[\mathcal{E}_2 \mid \mathcal{E}_1] = 1 - \sum_{ j = 1 }^{ \kappa}
\frac{ 1 }{ 16 \kappa} \geq \frac{15}{16}.\]
Let \(\mathcal{E}_3\) be the event that \(\left|{\sum_{i = 1 }^\kappa x_i}\right| \leq \varepsilon/9\). By Hoeffding’s bound (Lemma 10), \[\begin{align} \Pr\!\left[ \mathcal{E}_3 \mid \mathcal{E}_1 \cap \mathcal{E}_2 \right] &= 1-\Pr\!\left[ \left| \sum_{i=1}^{\kappa} x_i \right| > \frac{\varepsilon}{9} \,\middle|\, \mathcal{E}_1 \cap \mathcal{E}_2 \right] \nonumber \\ &\ge 1- 2\exp\!\left( - \frac{ 2\varepsilon^2 }{ 81 \sum_{i=1}^{\kappa} \left( \frac{2\varepsilon}{50\sqrt{\kappa}} \right)^2 } \right) \ge 1-\frac{1}{e^{12}}. \label{ineq:32hoeff} \end{align}\tag{7}\]
Hence, \[\begin{align} \Pr[ \mathcal{E}_1 \cap \mathcal{E}_2 \cap \mathcal{E}_3] &= \Pr[\mathcal{E}_1] \cdot \Pr[\mathcal{E}_2 | \mathcal{E}_1] \cdot \Pr[\mathcal{E}_3 \mid \mathcal{E}_1 \cap \mathcal{E}_2] \geq 1 -
\left({ \frac{21}{80} + \frac{ 1 }{ 16 } + \frac{ 1 }{ e^{12} } }\right) \geq \frac{2}{3}
\end{align}\] In what follows, we assume that all of the events \(\mathcal{E}_1\), \(\mathcal{E}_2\) and \(\mathcal{E}_3\) occur. Since, \(\Pr[ \mathcal{E}_1 \cap \mathcal{E}_2 \cap \mathcal{E}_3] \geq 2/3\), it is enough to argue that EdgeEstimation returns an \((1 \pm \varepsilon)\)-approximation to \(m\) when all \(\mathcal{E}_1\), \(\mathcal{E}_2\) and \(\mathcal{E}_3\) holds.
Combining the output of MulEstimation over the \(\kappa\) iterations, we get, \[\begin{align} \prod_{i = 1}^{ \kappa} \widehat{p}_i = \prod_{i = 1 }^{ \kappa} p_i \cdot \prod_{i =
1}^{ \kappa} \left({ 1 + \frac{x_i}{4} }\right)
\end{align}\] Using the fact that for each \(x_i \in (0,1)\), it can be shown that \[\begin{align} 1 - \frac{ \sum_{i = 1}^{ \kappa} x_i }{ 4 } \leq \prod_{i = 1}^{ \kappa} \left({ 1 +
\frac{x_i}{4} }\right) \leq 1 + \sum_{i = 1}^{ \kappa} x_i
\end{align}\]
Since event \(\mathcal{E}_3\) occurs, \[\begin{align} \prod_{i = 1 }^{ \kappa} p_i \cdot \left({1 - \frac{\varepsilon}{36}}\right) \leq \prod_{i = 1}^{ \kappa} \widehat{p}_i \leq \prod_{i = 1 }^{ \kappa} p_i \cdot \left({1 + \frac{\varepsilon}{9}}\right) \end{align}\] Using the fact that for any \(\varepsilon\in (0, 1/3)\), we have \(1 - 3\varepsilon\leq (1 + \varepsilon)^{-1}\) and \((1 - \varepsilon)^{-1} \leq 1 + 3\varepsilon\). We get, \[\begin{align} \label{ineq:32xyz} \left({1 - \frac{\varepsilon}{3}}\right) \cdot \frac{1}{\prod_{i = 1 }^{ \kappa} p_i} \leq \frac{1}{\prod_{i = 1}^{ \kappa} \widehat{p}_i} \leq \frac{1}{\prod_{i = 1 }^{ \kappa} p_i} \cdot \left({1 + \frac{\varepsilon}{12}}\right) \end{align}\tag{8}\]
Since \(\mathcal{E}_1\) occurs, i.e., \(\mathcal{E}_\mathrm{bir}\) occurs, \(\widehat{m}_b\) satisfies the following: \[\begin{align} \label{ineq:32birthdayest} \left({ 1 - \frac{\varepsilon}{3} }\right) \cdot m( U_\kappa) \leq \widehat{m}_b \leq \left({ 1 + \frac{\varepsilon}{3} }\right) \cdot m( U_\kappa) \end{align}\tag{9}\] Combining 8 and 9 , we get, \[\begin{align} \left({ 1 - \frac{\varepsilon}{3} }\right)^2 \cdot \frac{ m( U_\kappa) }{ \prod_{i = 1 }^{ \kappa} p_i} \leq \widehat{m}=\frac{ \widehat{m}_b }{ \prod_{i = 1}^{ \kappa} \widehat{p}_i} \leq \left({ 1 + \frac{\varepsilon}{12}}\right)\left({ 1 + \frac{\varepsilon}{3}}\right) \cdot \frac{ m( U_\kappa) }{ \prod_{i = 1}^{ \kappa} p_i} \end{align}\]
Since, \(p_i = \frac{ m( U_i) }{ m( U_{i - 1} )}\) for each \(i \in [\kappa]\) and \(U_0 = V\), \(\frac{ m( U_\kappa) }{ \prod_{i = 1 }^{ \kappa} p_i} = m( U_0 ) = m\). So, simplifying the above expression, we have \[\begin{align} \left({ 1 - \varepsilon}\right) m\leq \widehat{m}\leq \left({ 1 + \varepsilon}\right) m \end{align}\] ◻
5.0.0.1 Acknowledgments:
We thank an anonymous reviewer for their suggestions in improving the query complexity from \(\log^3 m\) (in an earlier version) to \(\log^2 m\). 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.
6 Concentration Inequalities↩︎
We use the following concentration bounds.
Lemma 7 (Markkov’s inequlaity, see [4]). Let \(X\) be a random variable that assumes only nonnegative values. Then, for all \(a > 0\) \[\Pr \left[{ X \geq a}\right] \leq \frac{ \mathop{\mathrm{\mathbb{E}}}[ X ] }{ a }.\]
Lemma 8 (Chebyshev’s inequality, see [4]). Let \(X\) be a random variable and \(a > 0\), Then \[\Pr[ \left|{X - \mathop{\mathrm{\mathbb{E}}}[X]}\right| > a] \leq \frac{ \mathop{\mathrm{\mathrm{Var}}}( X ) }{ a^2 }.\]
Lemma 9 (Multiplicative Chernoff bound, see [4]). Let \(X_1,X_2,...,X_t\) be i.i.d. random variables where \(\Pr[X_i = 1] = p\) and \(\Pr[X_i = 0] = 1-p\) for all \(i \in [t]\), and \(X = \sum_{i \in [t]} X_i\). Then, we have \[\begin{align} \Pr \left[ X \leq (1-\varepsilon) \mathop{\mathrm{\mathbb{E}}}\left[{X}\right] \right] &\leq \exp{\left({-\frac{\varepsilon^2\mathop{\mathrm{\mathbb{E}}}\left[{X}\right]}{3}}\right)} & 0 \leq \varepsilon<1\\ \Pr \left[ X \geq (1+\varepsilon) \mathop{\mathrm{\mathbb{E}}}\left[{X}\right] \right] &\leq \exp{\left({-\frac{\varepsilon^2\mathop{\mathrm{\mathbb{E}}}\left[{X}\right]}{2}}\right)} & \varepsilon\geq 0 \end{align}\]
Lemma 10 (Hoeffding’s bound, see [4]). Let \(X_1, X_2, \ldots, X_t\) be independent random variables such that for all \(i \in [t]\), \(\mathop{\mathrm{\mathbb{E}}}[X] = \mu\) and \(\Pr[a \leq X_i \leq b] = 1\). Then \[\Pr \left[{ \left|{ \frac{ 1 }{ t } \sum_{i = 1}^t X_i - \mu }\right| \geq \varepsilon}\right] \leq 2 \exp{ \left({ - \frac{ 2t\varepsilon^2 }{ (b - a)^2 } }\right) }.\]
Lemma 11 (See [33]). Let f be any function of \(t\) independent random variables \(Y_1, \ldots, Y_t\) and let \(X_i = \mathop{\mathrm{\mathbb{E}}}[f(Y_1, \ldots, Y_t)|Y_1, \ldots, Y_i]\) for \(i \in [t]\) and \(X_0 = \mathop{\mathrm{\mathbb{E}}}[f(Y_1, \ldots, Y_t)]\). Let \(\mathcal{B}\) be the event that there exists \(i \in [t]\) such that \(\left|{X_i - X_{i-1}}\right| > c_i\) where \(c_1, \ldots, c_t\) are some non negative numbers. Let \(S = \sum_{i = 1}^t c_i^2\), then \[\Pr \left[{\left|{X_t - X_0}\right| > s }\right] \leq 2\exp{ \left({-\frac{s^2}{2S}}\right)} + \Pr[ \mathcal{B}].\]
7 Threshold checking↩︎
In this section, we present the algorithms IsCollision, BirthdayEstimate and the proofs of [lemma:32collision32detection] and [lemma:32birthdayestimate].
Proof. Fix an iteration \(i\) of IsCollision (Line [alg:32collision32line321]). The
probability that no collision occurs in the \(i\)-th iteration is \[\begin{align} \Pr[k_i = 0] = \prod_{j=0}^{t- 1} \left(1 - \frac{j}{m(U)}\right).
\end{align}\]
If \(m(U) \leq \tau\), We upper bound the probability of no collision as follows: \[\begin{align} \Pr[k_i = 0] &\leq \exp\left( - \sum_{j=0}^{t- 1} \frac{j}{m(U)} \right) && \text{(1 + x \leq e^{x} for all x \in \mathbb{R})} \\ &= \exp\left( - \frac{t(t- 1)}{2 m(U)} \right) \\ &\leq \exp\left( - \frac{t(t- 1)}{2 \tau} \right) && \text{(since m(U) \leq \tau)} \\ &\leq \frac{1}{e} && \text{(using t= \sqrt{2\tau})}. \end{align}\]
If \(m(U) \geq 8\tau\), we lower bound the probability of no collision: \[\begin{align} \Pr[k_i = 0] &\geq \exp\left( - \sum_{j=0}^{t- 1} \left( \frac{j}{m(U)} + \frac{j^2}{m(U)^2} \right) \right) && \text{(1 - x \geq e^{-x - x^2} for x \in [0, 2/3])} \\ &\geq \exp\left( - \frac{t(t- 1)}{16 \tau} + \Theta\!\left(\frac{1}{\sqrt{\tau}}\right) \right) \\ &\geq \frac{1}{2} && \text{(using t= \sqrt{2\tau})}. \end{align}\]
If \(m( U ) \leq \tau\), \(\Pr[ k_i = 0 ] \leq \frac{ 1 }{ e }\). IsCollision outputs \(0\) when more than half of \(k_i = 0\). Over \(\log ( \delta^{-1} )\) parallel runs, using the upper tail estimate of the Chernoff Bound (see Lemma 9), the probability that IsCollision outputs \(0\) is at most \(\exp ( - \log ( \delta^{-1} ) ) =
\delta\). Similarly, if \(m( U ) \geq 8\tau\), the probability that IsCollision outputs \(1\) is at most \(\delta\). ◻
Proof. Let \(\left\{{e_1, e_2, \ldots, e_{s}}\right\}\) be the sampled edges. or \(1 \le i < j \le s\), define the indicator random variable \(X_{ij}\) to be \(1\) if \(e_i = e_j\) and \(0\) otherwise . Then, \[\Pr[X_{ij}=1] = \frac{1}{ m( U ) } \text{ and } \mathop{\mathrm{\mathbb{E}}}[X_{ij}] = \frac{1}{ m( U ) }\] Define the total number of collisions by \(X = \sum_{1 \le i < j \le s} X_{ij}\). By the linearity of expectation \[\begin{align} \mathop{\mathrm{\mathbb{E}}}[X] = \binom{s}{2} \frac{1}{ m( U ) } \end{align}\] Since the random variables \(X_{ij}\) are not independent. We will bound the variance using \[\begin{align} \label{eq:32variance32equation} \mathop{\mathrm{\mathrm{Var}}}(X) &= \sum_{i < j } \mathop{\mathrm{\mathrm{Var}}}(X_{ij}) + 2\sum_{i < j, k < \ell} \mathrm{Cov}(X_{ij},X_{k\ell}) \end{align}\tag{10}\] Let us bound the first term \(\mathop{\mathrm{\mathrm{Var}}}(X_{ij})\) in 10 \[\begin{align} \sum_{i < j } \mathop{\mathrm{\mathrm{Var}}}(X_{ij}) \leq \sum_{ i < j } \mathop{\mathrm{\mathbb{E}}}[X_{ij}^2] \leq \binom{s}{2} \frac{1}{ m( U ) } = \mathop{\mathrm{\mathbb{E}}}[X] \end{align}\] Next, consider the covariance terms in 10 . If \(X_{ij}\) and \(X_{k\ell}\) correspond to disjoint pairs, then they are independent and the covariance is zero. If they overlap in exactly one index (share exactly one index), then \[\begin{align} \mathrm{Cov}(X_{ij},X_{j\ell}) &= \mathop{\mathrm{\mathbb{E}}}[X_{ij}X_{j\ell}] - \mathop{\mathrm{\mathbb{E}}}[X_{ij}]\mathop{\mathrm{\mathbb{E}}}[X_{j\ell}]\\ &= \Pr[X_{ij} = X_{j\ell} = 1] - \frac{1}{ m( U )^2}\\ &= \Pr[e_i = e_j = e_\ell] - \frac{1}{ m( U )^2 } \\ &= 0 \end{align}\] So, the bound on the variance is \(\mathop{\mathrm{\mathrm{Var}}}(X) = \sum_{i < j } \mathop{\mathrm{\mathrm{Var}}}(X_{ij}) \leq \mathop{\mathrm{\mathbb{E}}}[X]\). Using Chebyshev’s Inequality (Lemma 8), we have \[\begin{align} \nonumber\Pr[\left|{X - \mathop{\mathrm{\mathbb{E}}}[X]}\right| > \frac{\varepsilon}{3} \mathop{\mathrm{\mathbb{E}}}[X]] &\leq \frac{9\mathop{\mathrm{\mathrm{Var}}}(X)}{\varepsilon^2 (\mathop{\mathrm{\mathbb{E}}}[X])^2}\\ \nonumber&\leq \frac{9}{\varepsilon^2\mathop{\mathrm{\mathbb{E}}}[X]} &\text{\left({\mathop{\mathrm{\mathrm{Var}}}(X) \leq \mathop{\mathrm{\mathbb{E}}}[X]}\right)}\\ \nonumber&= \frac{ 18m( U ) }{ \varepsilon^2s(s- 1) } &\text{\left({ \mathop{\mathrm{\mathbb{E}}}[X] = \binom{s}{2} \frac{ 1 }{ m( U ) } }\right)}\\ &\leq \frac{1}{ 16 } &\text{( m_U \leq \tau and s= \Theta ( \sqrt{ \tau} /{ \varepsilon} ))}\label{ineq:32collision32bound} \end{align}\tag{11}\] To complete the proof, we need to show with probability at least \(15/ 16\) \[\begin{align} \left({1 - \varepsilon}\right) m( U ) \leq \binom{s}{2} \frac{1}{X} \leq m( U ) \left({1 + \varepsilon}\right) \end{align}\] From 11 , with probability at least \(15/ 16\) \[\begin{align} \left({1 - \frac{\varepsilon}{3}}\right)\mathop{\mathrm{\mathbb{E}}}\left[{X}\right] \leq X \leq \left({1 + \frac{\varepsilon}{3}}\right) \mathop{\mathrm{\mathbb{E}}}\left[{X}\right] \end{align}\] This implies \[\begin{align} \Rightarrow \frac{ m( U ) }{\left({1 + \frac{\varepsilon}{3}}\right)}\leq \binom{s}{2} \frac{1}{X} \leq \frac{m( U ) }{\left({1 - \frac{\varepsilon}{3}}\right)} \end{align}\] For any \(\varepsilon\in (0, 1)\) \[1 - \varepsilon\leq \left({1 + \frac{\varepsilon}{3}}\right)^{-1} \text{ and } \left({1 - \frac{\varepsilon}{3}}\right)^{-1} \leq 1 + \varepsilon\] Since \(X\) is the number of collisions. we conclude that \[\begin{align} \left({1 - \varepsilon}\right) m( U ) \leq \binom{s}{2} \frac{1}{r} \leq m( U ) \left({1 + \varepsilon}\right) \end{align}\] which completes the proof. ◻