Breaking the hardness assumption at the base of our conditional lower bound would be a major breakthrough.
The longstanding upper bound for triangle detection is \(O(\min \lbrace m^{2\omega /(\omega +1)},n^{\omega }\rbrace )\)  [1]}.
Even if an optimal matrix multiplication algorithm exists (\(\omega =2\) ) no algorithm breaks the quadratic barrier when \(m=n^{1.5}\) .
This continues to be the case in the natural setting where the maximum degree (rather than the average degree) is \(\sqrt{n}\) .
Note that we cannot base these lower bounds on 3SUM or APSP, as we did in the results above for problems with multiple outputs, until we know how to base the hardness of Triangle detection itself on these assumptions.
See Section  for further discussion.
