Approximate Triangle Counting via Sampling and Fast Matrix Multiplication

Understand

There is a trivial $O(\frac{n^3}{T})$ time 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$; this as follows from the lower bound of Eden and Rosenbaum [APPROX/RANDOM 2018].