{"ID":2829975,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2512.11994","arxiv_id":"2512.11994","title":"Optimal non-adaptive algorithm for edge estimation","abstract":"We present a simple nonadaptive randomized algorithm that estimates the number of edges in a simple, unweighted, undirected graph, possibly containing isolated vertices, using only degree and random edge queries. For an $n$-vertex graph, our method requires only $\\widetilde{O}(\\sqrt{n})$ queries, achieving sublinear query complexity. The algorithm independently samples a set of vertices and queries their degrees, and also independently samples a set of edges, using the answers to these queries to estimate the total number of edges in the graph. We further prove a matching lower bound, establishing the optimality of our algorithm and resolving the non-adaptive query complexity of this problem with respect to degree and random-edge queries.","short_abstract":"We present a simple nonadaptive randomized algorithm that estimates the number of edges in a simple, unweighted, undirected graph, possibly containing isolated vertices, using only degree and random edge queries. For an $n$-vertex graph, our method requires only $\\widetilde{O}(\\sqrt{n})$ queries, achieving sublinear qu...","url_abs":"https://arxiv.org/abs/2512.11994","url_pdf":"https://arxiv.org/pdf/2512.11994v1","authors":"[\"Arijit Bishnu\",\"Debarshi Chanda\",\"Buddha Dev Das\",\"Arijit Ghosh\",\"Gopinath Mishra\"]","published":"2025-12-12T19:18:03Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"math.CO\"]","methods":"[]","has_code":false}