Fastest approximate triangle counting algorithms in dense graphs One may compute the number of triangles in a graph by matrix multiplication in time $O(n^\omega)$. There is also a very simple algorithm that runs in time $O(n^3/(\epsilon^2 T))$ (where $T$ is the number of triangles) for $1\pm \epsilon$ approximate triangle counting. It works by repeatedly sampling triplets of vertices and using those sample to estimate the number of triangles.
Is there anything asymptotically faster than these two algorithms? I am aware of the sublinear-time algorithms for triangle counting. However, those that I am aware of are parameterized by the number of edges and not the number of vertices. I am only interested in results parameterized by the number of vertices.
I have written up an answer, it can be found here: https://arxiv.org/abs/2104.08501
The best known triangle counting algorithm runs in time $\tilde{O}(n^\omega)$. I was able to retain the exponent of $n$ while having negative dependence on $T$. In fact, the running time is $\tilde{O}_\epsilon(n^\omega/T^\delta)$ such that there is the is no such algorithm for any constant $\delta' &lt; \delta$. In this sense, the algorithm is optimal. (One could, however, imagine an algorithm with non-constant $\delta$.) The value of $\delta$ is $\omega - 2$. This degenerates to $0$, if there exists a quadratic matrix multiplication algorithm.
I have also done the same for sparse matrix multiplication. There, the state-of-the-art was $\tilde{O}(m^{2\omega/(\omega+1)})$. I have retained the exponent while again having &quot;optimal&quot; negative dependency on $T$ (albeit the optimality is in the fairly weak sense mentioned above).
For a sketch of the algorithm, see page 5 in the paper. If you have comments, I would be very happy to hear them.
Here is a diagram comparing the running time to other algorithms:

(I have just noticed that the diagram on the right should have log base $m$, I'll fix it later)
The &quot;optimality&quot; lies in the fact that the blue line (my algorithm) touches the dashed red line (the lower bound). And yes, our algorithm is in fact slower than state-of-the-art for large values of $T$. On that range, the optimal algorithm was in fact already known. One could probably fix that so that this algorithm is never slower than the state-of-the-art; however, the analysis is already technically non-trivial as it is now.