# Nearly optimal edge estimation with independent set queries

arXiv: https://arxiv.org/abs/1907.04381 · HTML: https://mlsanity.com/paper/1907.04381/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Jul 2019.

## Built on by (most cited first, 2 of 2)

- [Clustering with Non-adaptive Subset Queries](https://mlsanity.com/paper/2409.10908/) (2024)
- [Prior Knowledge Makes It Possible: From Sublinear Graph Algorithms to LLM Test-Time Methods](https://mlsanity.com/paper/2510.16609/) (2025)

## Abstract (arXiv)

We study the problem of estimating the number of edges of an unknown, undirected graph G=([n],E) with access to an independent set oracle. When queried about a subset Ssubseteq [n] of vertices the independent set oracle answers whether S is an independent set in G or not. Our first main result is an algorithm that computes a (1+ε)-approximation of the number of edges m of the graph using min(√m,n / √m)·textrmpoly(log n,1/ε) independent set queries. This improves the upper bound of min(√m,n2/m)·textrmpoly(log n,1/ε) by Beame et al. citeBHRRS18. Our second main result shows that min(√m,n/√m))/textrmpolylog(n) independent set queries are necessary, thus establishing that our algorithm is optimal up to a factor of textrmpoly(log n, 1/ε).