Reducing 3XOR to listing triangles, an exposition
Emanuele Viola · 2011
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). This problem can be easily solved in time Õ(n2). (Throughout this note, Õ and ˜ Ω hide subpolynomial factors no(1).) It seems natural to believe that this problem also requires time ˜ Ω(n2), and this has been confirmed in some restricted models.[Eri99, AC05] The importance of this belief was brought to the forefront by Gajentaan and Overmars who show that the belief implies lower bounds for a number of problems in computational geometry;[GO95] and the list of such reductions has grown ever since. Recently, a series of exciting papers by Baran, Demaine, Pǎtra¸scu, Vassilevska, and Williams set the stage for, and establish, reductions from 3SUM to new types of problems which are not defined in terms of summation.[BDP08, VW09, PW10, Pǎt10] In particular, Pǎtra¸scu reduces 3SUM to the problem of listing triangles of a graph.[Pǎt10] In this note we present this reduction by Pǎtra¸scu 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. So one can think of 3XOR as asking if a given n × O(lg n) matrix over the field with two elements has a linear combination of length 3. This problem is likely