Revision #1 Authors: Zahra Jafargholi, Emanuele Viola

Accepted on: 21st August 2013 17:22

Downloads: 956

Keywords:

Patrascu (STOC '10) reduces the 3SUM problem to

listing triangles in a graph. In the other direction, we

show that if one can solve 3SUM on a set of size $n$ in

time $n^{1+\e}$ then one can list $t$ triangles in a

graph with $m$ edges in time $\tilde

O(m^{1+\e}t^{1/3-\e/3})$. Our result builds on and

extends works by the Paghs (PODS '06) and by Vassilevska

and Williams (FOCS '10). We make our reductions

deterministic using tools from pseudorandomness.

We then re-execute both Patrascu's reduction

and ours for the variant 3XOR of 3SUM where integer

summation is replaced by bit-wise xor. As a corollary we

obtain that if 3XOR is solvable in linear time but

3SUM requires quadratic randomized time, or vice versa,

then the randomized time complexity of listing $m$

triangles in a graph with $m$ edges is $m^{4/3}$ up to a

factor $m^\alpha$ for any $\alpha > 0$.

TR13-009 Authors: Zahra Jafargholi, Emanuele Viola

Publication: 9th January 2013 18:13

Downloads: 1146

Keywords:

We show that if one can solve 3SUM on a set of size $n$

in time $n^{1+\epsilon}$ then one can list $t$ triangles in a

graph with $m$ edges in time $\tilde

O(m^{1+\epsilon}t^{1/3+\epsilon'})$ for any $\epsilon' > 0$. This is a

reversal of Patrascu's reduction from 3SUM to

listing triangles (STOC '10).

We then re-execute both Patrascu's reduction

and our reversal for the variant 3XOR of 3SUM where

integer summation is replaced by bit-wise xor. As a

corollary we obtain that if 3XOR is solvable in linear

time but 3SUM requires quadratic randomized time, or vice

versa, then the randomized time complexity of listing $m$

triangles in a graph with $m$ edges is $m^{4/3}$ up to a

factor $m^\alpha$ for any $\alpha > 0$.

Our results are obtained building on and extending works

by the Paghs (PODS '06) and by Vassilevska and Williams

(FOCS '10).