There is a trivial  (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 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(n^\omega{T^{\omega - 2}}\big) \cdot 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 O\big(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 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(m^{2\omega/(\omega+1)}{ T^{2(\omega-1)/(\omega+1)}}\Big) \cdot 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  .
There is a trivial O (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 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(n^\omega{T^{\omega - 2}}\big) \cdot 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]. Our algorithm improves upon the state of the art when T = \omega(1) and T = o(n). 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 O\big(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 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(m^{2\omega/(\omega+1)}{ T^{2(\omega-1)/(\omega+1)}}\Big) \cdot 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 without worsening the dependency on m. This algorithm improves upon the state of the art when T = \omega(1) and T = o(\sqrt{m .
A
O
A
time
R
,
; this
A
Our algorithm improves upon the state of the art when T = \omega(1) and T = o(n).
A
without worsening the dependency on m. This algorithm improves upon the state of the art when T = \omega(1) and T = o(\sqrt{m