Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > TRIANGLE:
Reports tagged with triangle:
TR13-009 | 9th January 2013
Zahra Jafargholi, Emanuele Viola

#### 3SUM, 3XOR, Triangles

Revisions: 1

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

ISSN 1433-8092 | Imprint