Nearly optimal edge estimation with independent set queries

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/ε).