Patrascu (STOC '10) reduces the 3SUM problem tolisting triangles in a graph. In the other direction, weshow that if one can solve 3SUM on a set of size n intime n1+\e then one can list t triangles in agraph with m edges in time O(m1+\et13−\e3) . Our result builds on andextends works by the Paghs (PODS '06) and by Vassilevskaand Williams (FOCS '10). We make our reductionsdeterministic using tools from pseudorandomness.

We then re-execute both Patrascu's reductionand ours for the variant 3XOR of 3SUM where integersummation is replaced by bit-wise xor. As a corollary weobtain that if 3XOR is solvable in linear time but3SUM requires quadratic randomized time, or vice versa,then the randomized time complexity of listing mtriangles in a graph with m edges is m43 up to afactor m for any 0">0.