# Viola's Reduction of 3XOR to listing triangles

Apparently this was due to Pătraşcu, but in this report on the ECCC server, Viola states that 3XOR can be reduced to listing triangles.

Assume that given a graph in adjacency list format, with $$m$$ edges, $$z$$ triangles, $$O(m)$$ nodes, one can list $$\min\{z,m\}$$ triangles in time $$m^{(4/3)-\varepsilon}$$ for $$\epsilon>0$$ constant. Then one can solve 3XOR on a set of size $$n$$ in time $$n^{2-\epsilon'}$$ with error $$1\%$$ for a constant $$\epsilon'>0.$$

My question is the reverse. If one were to have an efficient algorithm for 3XOR, what could one say about efficiently listing triangles?

In this paper, Corollary 1, we show that if you solve 3XOR in close to linear time then you can list $$t$$ triangles in a graph with $$m$$ edges in time $$m\cdot t^{1/3},$$ ignoring lower-order terms.