Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with sub-quadratic:
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