For some background on this theorem, we mention that reductions from 3-SUM to triangle listing were initiated by Pătraşcu [1]} and further refined in [2]}. Recently, Vassilevska Williams and Xu [3]} showed that the 3-SUM conjecture can be replaced by the APSP conjecture, obtaining the same result under either of these conjectures. They also showed a variant of this lower bound which replaces triangle listing by asking for every edge whether it is part of a triangle [3]}; this variant is more useful in our context and stated above (slightly rephrased).
