<p>[Copying here the answer from <a href="https://emanueleviola.wordpress.com/2018/12/20/50m-to-northeastern-computer-science/" rel="nofollow noreferrer">here</a>]</p>

<blockquote>
  <p>In <a href="http://www.ccs.neu.edu/home/viola/papers/threethree.pdf" rel="nofollow noreferrer">this paper</a>, Corollary 1, we show that if you solve 3XOR in close to linear time then you can list <span class="math-container">$t$</span> triangles in a graph with <span class="math-container">$m$</span> edges in time <span class="math-container">$m\cdot t^{1/3},$</span> ignoring lower-order terms.</p>
</blockquote>

CC BY-SA 4.0
2019-02-01T14:57:49.343Z
2019-02-01T18:08:22.833Z
2019-02-01T18:08:22.833Z
Manu
<p>Apparently this was due to Pătraşcu, but in <a href="https://eccc.weizmann.ac.il/report/2011/113/" rel="nofollow noreferrer">this report</a> on the ECCC server, Viola states that 3XOR can be reduced to listing triangles.</p>

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

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

<cc.complexity-theory><graph-theory>
Viola's Reduction of 3XOR to listing triangles
kodlu
# Viola's Reduction of 3XOR to listing triangles

(Asked by: username_0 on 2019-01-21)

Apparently this was due to Pătraşcu, but in [this report](https://eccc.weizmann.ac.il/report/2011/113/) 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?

**Tags:** cc.complexity-theory, graph-theory


---

## 1 answers

### Answer by username_1 on 2019-02-01. Score: 4

[Copying here the answer from [here](https://emanueleviola.wordpress.com/2018/12/20/50m-to-northeastern-computer-science/)]

> In [this paper](http://www.ccs.neu.edu/home/viola/papers/threethree.pdf), 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.


---

