Document Open Access Logo

A Subquadratic Algorithm for 3XOR

Authors Martin Dietzfelbinger , Philipp Schlag , Stefan Walzer

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2018.59.pdf
  • Filesize: 0.56 MB
  • 15 pages

Document Identifiers

Author Details

Martin Dietzfelbinger
  • Technische Universität Ilmenau, Germany
Philipp Schlag
  • Technische Universität Ilmenau, Germany
Stefan Walzer
  • Technische Universität Ilmenau, Germany

Cite As Get BibTex

Martin Dietzfelbinger, Philipp Schlag, and Stefan Walzer. A Subquadratic Algorithm for 3XOR. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 59:1-59:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.MFCS.2018.59

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).

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • 3SUM
  • 3XOR
  • Randomized Algorithms
  • Reductions
  • Conditional Lower Time Bounds

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Susanne Albers and Torben Hagerup. Improved Parallel Integer Sorting without Concurrent Writing. Inf. Comput., 136(1):25-51, 1997. Google Scholar
  2. Ilya Baran, Erik D. Demaine, and Mihai Pătraşcu. Subquadratic Algorithms for 3SUM. Algorithmica, 50(4):584-596, 2008. Google Scholar
  3. Ilya Baran, Erik D. Demaine, and Mihai Pǎtraşcu. Subquadratic Algorithms for 3SUM. In WADS, pages 409-421, 2005. Google Scholar
  4. Luis Barba, Jean Cardinal, John Iacono, Stefan Langerman, Aurélien Ooms, and Noam Solomon. Subquadratic Algorithms for Algebraic Generalizations of 3SUM. In SoCG, volume 77 of LIPIcs, pages 13:1-13:15, 2017. Google Scholar
  5. K. E. Batcher. Sorting Networks and Their Applications. In SJCC, AFIPS (Spring), pages 307-314, 1968. Google Scholar
  6. Charles Bouillaguet, Claire Delaplace, and Pierre-Alain Fouque. Revisiting and Improving Algorithms for the 3XOR Problem. IACR ToSC, 2018(1):254-276, 2018. Google Scholar
  7. Timothy M. Chan. The Art of Shaving Logs. WADS (Invited Talk), 2013. Google Scholar
  8. Timothy M. Chan. More Logarithmic-Factor Speedups for 3SUM, (median, +)-Convolution, and Some Geometric 3SUM-Hard Problems. In SODA, pages 881-897, 2018. Google Scholar
  9. Timothy M. Chan and Moshe Lewenstein. Clustered Integer 3SUM via Additive Combinatorics. In STOC, pages 31-40, 2015. Google Scholar
  10. Martin Dietzfelbinger. Universal hashing and k-wise independent random variables via integer arithmetic without primes. In STACS, pages 569-580, 1996. Google Scholar
  11. Martin Dietzfelbinger, Philipp Schlag, and Stefan Walzer. A Subquadratic Algorithm for 3XOR. CoRR, abs/1804.11086, 2018. URL: http://arxiv.org/abs/1804.11086.
  12. Michael L. Fredman, János Komlós, and Endre Szemerédi. Storing a Sparse Table with O(1) Worst Case Access Time. J. ACM, 31(3):538-544, 1984. Google Scholar
  13. Michael L. Fredman and Dan E. Willard. Surpassing the Information Theoretic Bound with Fusion Trees. J. Comput. Syst. Sci., 47(3):424-436, 1993. Google Scholar
  14. Ari Freund. Improved Subquadratic 3SUM. Algorithmica, 77(2):440-458, Feb 2017. Google Scholar
  15. Anka Gajentaan and Mark H. Overmars. On a Class of O(n²) Problems in Computational Geometry. Comput. Geom., 5(3):165-185, 1995. Google Scholar
  16. Omer Gold and Micha Sharir. Improved Bounds for 3SUM, k-SUM, and Linear Degeneracy. CoRR, abs/1512.05279, 2015. Google Scholar
  17. Torben Hagerup, Peter Bro Miltersen, and Rasmus Pagh. Deterministic Dictionaries. J. Algorithms, 41(1):69-85, 2001. URL: http://dx.doi.org/10.1006/jagm.2001.1171.
  18. Yijie Han. Deterministic sorting in O(n log log n) time and linear space. J. Algorithms, 50(1):96-105, 2004. Google Scholar
  19. Zahra Jafargholi and Emanuele Viola. 3SUM, 3XOR, Triangles. Algorithmica, 74(1):326-343, 2016. Google Scholar
  20. Allan Grønlund Jørgensen and Seth Pettie. Threesomes, Degenerates, and Love Triangles. In FOCS, pages 621-630, 2014. Google Scholar
  21. Daniel M. Kane, Shachar Lovett, and Shay Moran. Near-optimal Linear Decision Trees for k-SUM and Related Problems. In STOC, pages 554-563, 2018. Google Scholar
  22. Tsvi Kopelowitz, Seth Pettie, and Ely Porat. Higher lower bounds from the 3SUM conjecture. In SODA, pages 1272-1287, 2016. Google Scholar
  23. Andrea Lincoln, Virginia Vassilevska Williams, Joshua R. Wang, and R. Ryan Williams. Deterministic Time-Space Tradeoffs for k-SUM. CoRR, abs/1605.07285, 2016. Google Scholar
  24. Y. Mansour, N. Nisan, and P. Tiwari. The Computational Complexity of Universal Hashing. Theor. Comput. Sci., 107(1):121-133, 1993. Google Scholar
  25. Donald R. Morrison. PATRICIA - Practical Algorithm To Retrieve Information Coded in Alphanumeric. J. ACM, 15(4):514-534, 1968. URL: http://dx.doi.org/10.1145/321479.321481.
  26. Mihai Pătraşcu. Towards Polynomial Lower Bounds for Dynamic Problems. In STOC, pages 603-610, 2010. Google Scholar
  27. Philipp Schlag. Untere Schranken für Berechnungsprobleme auf der Basis der 3SUM-Vermutung. Master’s thesis, TU Ilmenau, Germany, 2016. Google Scholar
  28. Joshua R. Wang. Space-Efficient Randomized Algorithms for K-SUM. In ESA, pages 810-829, 2014. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact