Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR11-113 | 11th August 2011 17:57

Reducing 3XOR to listing triangles, an exposition

RSS-Feed




TR11-113
Authors: Emanuele Viola
Publication: 11th August 2011 17:57
Downloads: 3340
Keywords: 


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.



ISSN 1433-8092 | Imprint