  There is a trivial $\tilde{O}(\frac{n^3}{T})$ algorithm for approximate
triangle counting where $T$ is the number of triangles in the graph and $n$ the
number of vertices. At the same time, one may count triangles exactly using
fast matrix multiplication in time $\tilde{O}(n^\omega)$. Is it possible to get
a negative dependency on the number of triangles $T$ while retaining the
$n^\omega$ dependency on $n$? We answer this question positively by providing
an algorithm which runs in time $O\big(\frac{n^\omega}{T^{\omega - 2}}\big)
\cdot \text{poly}(n^{o(1)}/\epsilon)$. This is optimal in the sense that as
long as the exponent of $T$ is independent of $n, T$, it cannot be improved
while retaining the dependency on $n$, as follows from the lower bound of Eden
and Rosenbaum [APPROX/RANDOM 2018].
  We also consider the problem of approximate triangle counting in sparse
graphs, parameterizing by the number of edges $m$. The best known algorithm
runs in time $\tilde{O}\big(\frac{m^{3/2}}{T}\big)$ [Eden et al., SIAM Journal
on Computing, 2017]. There is also a well known algorithm for exact triangle
counting that runs in time $\tilde{O}(m^{2\omega/(\omega + 1)})$. We again get
an algorithm that retains the exponent of $m$ while running faster on graphs
with larger number of triangles. Specifically, our algorithm runs in time
$O\Big(\frac{m^{2\omega/(\omega+1)}}{ T^{2(\omega-1)/(\omega+1)}}\Big) \cdot
\text{poly}(n^{o(1)}/\epsilon)$. This is again optimal in the sense that if the
exponent of $T$ is to be constant, it cannot be improved.
