5
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

[Copying here the answer from here]

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.