License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2018.59
URN: urn:nbn:de:0030-drops-96417
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9641/
Dietzfelbinger, Martin ;
Schlag, Philipp ;
Walzer, Stefan
A Subquadratic Algorithm for 3XOR
Abstract
Given a set X of n binary words of equal length w, the 3XOR problem asks for three elements a, b, c in X such that a oplus b=c, where oplus denotes the bitwise XOR operation. The problem can be easily solved on a word RAM with word length w in time O(n^2 log n). Using Han's fast integer sorting algorithm (STOC/J. Algorithms, 2002/2004) this can be reduced to O(n^2 log log n). With randomization or a sophisticated deterministic dictionary construction, creating a hash table for X with constant lookup time leads to an algorithm with (expected) running time O(n^2). At present, seemingly no faster algorithms are known.
We present a surprisingly simple deterministic, quadratic time algorithm for 3XOR. Its core is a version of the PATRICIA tree for X, which makes it possible to traverse the set a oplus X in ascending order for arbitrary a in {0, 1}^{w} in linear time. Furthermore, we describe a randomized algorithm for 3XOR with expected running time O(n^2 * min{log^3(w)/w, (log log n)^2/log^2 n}). The algorithm transfers techniques to our setting that were used by Baran, Demaine, and Patrascu (WADS/Algorithmica, 2005/2008) for solving the related int3SUM problem (the same problem with integer addition in place of binary XOR) in expected time o(n^2). As suggested by Jafargholi and Viola (Algorithmica, 2016), linear hash functions are employed.
The latter authors also showed that assuming 3XOR needs expected running time n^(2-o(1)) one can prove conditional lower bounds for triangle enumeration just as with 3SUM. We demonstrate that 3XOR can be reduced to other problems as well, treating the examples offline SetDisjointness and offline SetIntersection, which were studied for 3SUM by Kopelowitz, Pettie, and Porat (SODA, 2016).
BibTeX - Entry
@InProceedings{dietzfelbinger_et_al:LIPIcs:2018:9641,
author = {Martin Dietzfelbinger and Philipp Schlag and Stefan Walzer},
title = {{A Subquadratic Algorithm for 3XOR}},
booktitle = {43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
pages = {59:1--59:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-086-6},
ISSN = {1868-8969},
year = {2018},
volume = {117},
editor = {Igor Potapov and Paul Spirakis and James Worrell},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9641},
URN = {urn:nbn:de:0030-drops-96417},
doi = {10.4230/LIPIcs.MFCS.2018.59},
annote = {Keywords: 3SUM, 3XOR, Randomized Algorithms, Reductions, Conditional Lower Time Bounds}
}
|
Keywords: |
|
3SUM, 3XOR, Randomized Algorithms, Reductions, Conditional Lower Time Bounds |
|
Collection: |
|
43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
27.08.2018 |
