All reports by Author Zahra Jafargholi:

__
TR13-009
| 9th January 2013
__

Zahra Jafargholi, Emanuele Viola#### 3SUM, 3XOR, Triangles

Revisions: 1

__
TR12-125
| 2nd October 2012
__

Zahra Jafargholi, Hamidreza Jahanjou, Eric Miles, Jaideep Ramachandran, Emanuele Viola#### From RAM to SAT

Revisions: 1

Zahra Jafargholi, Emanuele Viola

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

Zahra Jafargholi, Hamidreza Jahanjou, Eric Miles, Jaideep Ramachandran, Emanuele Viola

Common presentations of the NP-completeness of SAT suffer

from two drawbacks which hinder the scope of this

flagship result. First, they do not apply to machines

equipped with random-access memory, also known as

direct-access memory, even though this feature is

critical in basic algorithms. Second, they incur a

quadratic blow-up ...
more >>>