__
TR11-113 | 11th August 2011 17:57
__

#### Reducing 3XOR to listing triangles, an exposition

**Abstract:**
The 3SUM problem asks if there are three integers $a,b,c$ summing to $0$ in a given set of $n$ integers of magnitude poly($n$). Patrascu (STOC '10) reduces solving 3SUM in time $n^{2-\Omega(1)}$ to listing $m$ triangles in a graph with $m$ edges in time $m^{4/3-\Omega(1)}$.

In this note we present this reduction but for a variant of the 3SUM problem which we call 3XOR. The problem 3XOR is like 3SUM except that integer summation is replaced with bit-wise xor. The proof of the reduction is slightly simpler than the original one.