ECCC-Report TR11-113https://eccc.weizmann.ac.il/report/2011/113Comments and Revisions published for TR11-113en-usThu, 11 Aug 2011 17:57:58 +0300
Paper TR11-113
| Reducing 3XOR to listing triangles, an exposition |
Emanuele Viola
https://eccc.weizmann.ac.il/report/2011/113The 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.
Thu, 11 Aug 2011 17:57:58 +0300https://eccc.weizmann.ac.il/report/2011/113