  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 $S\subseteq [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+\epsilon)$-approximation of the number of
edges $m$ of the graph using $\min(\sqrt{m},n /
\sqrt{m})\cdot\textrm{poly}(\log n,1/\epsilon)$ independent set queries. This
improves the upper bound of $\min(\sqrt{m},n^2/m)\cdot\textrm{poly}(\log
n,1/\epsilon)$ by Beame et al. \cite{BHRRS18}. Our second main result shows
that ${\min(\sqrt{m},n/\sqrt{m}))/\textrm{polylog}(n)}$ independent set queries
are necessary, thus establishing that our algorithm is optimal up to a factor
of $\textrm{poly}(\log n, 1/\epsilon)$.
