{"ID":6138300,"CreatedAt":"2026-07-09T01:07:32.349475501Z","UpdatedAt":"2026-07-11T14:35:24.647767831Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.07483","arxiv_id":"2607.07483","title":"From Decision to Random Certificates: Exponential Separation for Edge Estimation with Independent Set Queries","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Θ\\!\\left(\\min\\left\\{\\sqrt{m},\\, \\frac{n}{\\sqrt{m}}\\right\\}\\right)$ queries, while direct random edge-sample access requires $\\widetildeΘ(\\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.","short_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 rando...","url_abs":"https://arxiv.org/abs/2607.07483","url_pdf":"https://arxiv.org/pdf/2607.07483v1","authors":"[\"Debarshi Chanda\",\"Buddha Dev Das\",\"Arijit Ghosh\",\"Gopinath Mishra\"]","published":"2026-07-08T14:45:18Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}