Complexity of counting the number of triangles of a graph The trivial approach of counting the number of triangles in a simple graph $G$ of order $n$ is to check for every triple $(x,y,z) \in   {V(G)\choose 3}$ if $x,y,z$ forms a triangle. 
This procedure gives us the algorithmic complexity of $O(n^3)$.
It is well known that if $A$ is the adjacency matrix of $G$ then the number of triangles in $G$ is $tr(A^3)/6.$
Since matrix multiplication can  be computed in time $O(n^{2.37})$ it is natural to ask:
Is there any (known) faster method for computing the number of triangles of a graph?

Let me cite this paper from 2007 (Practical algorithms for triangle computations in very large (sparse (power-law)) graphs by Matthieu Latapy):

The fastest algorithm known for finding and counting triangles relies
on fast matrix product and has an $\mathcal{O}(n^\omega)$ time
complexity, where $\omega < 2.376$ is the fast matrix product
exponent. This approach however leads to a $\theta(n^2)$ space
complexity.

There are some improvements for sparse graphs or if you want to list the triangles shown in the document.
