Title: Edge Estimation with Independent Set Oracles,
Abstract: We study the task of estimating the number of edges in a graph with access to
only an independent set oracle. Independent set queries draw motivation from
group testing and have applications to the complexity of decision versus
counting problems. We give two algorithms to estimate the number of edges in an
$n$-vertex graph, using (i) $\mathrm{polylog}(n)$ bipartite independent set
queries, or (ii) ${n}^{2/3} \cdot\mathrm{polylog}(n)$ independent set queries.