The conditional lower bounds in this paper are based on the \(n^{2-o(1)}\)  time hardness of two versions of triangle finding in \(\sqrt{n}\) -degree graphs:
The all-edge version of reporting for each of the \(n^{1.5}\)  edges whether it is in a triangle, and the more basic detection version of just deciding if there is any triangle in the graph.
The former is already known to be hard under either the 3SUM or APSP conjectures [1]}, two of the most central conjectures in fine-grained complexity [2]}, [3]}, and therefore does not need further justification (see also [4]} for equivalences to range reporting problems).
The goal of this section is to discuss the latter assumption.
