Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR13-009 | 21st August 2013 17:22

3SUM, 3XOR, Triangles

RSS-Feed




Revision #1
Authors: Zahra Jafargholi, Emanuele Viola
Accepted on: 21st August 2013 17:22
Downloads: 2633
Keywords: 


Abstract:

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$.


Paper:

TR13-009 | 9th January 2013 18:13

3SUM, 3XOR, Triangles





TR13-009
Authors: Zahra Jafargholi, Emanuele Viola
Publication: 9th January 2013 18:13
Downloads: 2804
Keywords: 


Abstract:

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).



ISSN 1433-8092 | Imprint