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

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