Document Open Access Logo

Improved Bounds for 3SUM, k-SUM, and Linear Degeneracy

Authors Omer Gold, Micha Sharir

PDF
Thumbnail PDF

File

LIPIcs.ESA.2017.42.pdf
  • Filesize: 0.56 MB
  • 13 pages

Document Identifiers

Author Details

Omer Gold
Micha Sharir

Cite As Get BibTex

Omer Gold and Micha Sharir. Improved Bounds for 3SUM, k-SUM, and Linear Degeneracy. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 42:1-42:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ESA.2017.42

Abstract

Given a set of n real numbers, the 3SUM problem is to decide whether there are three of them that sum to zero. Until a recent breakthrough by Gronlund and Pettie [FOCS'14], a simple Theta(n^2)-time deterministic algorithm for this problem was conjectured to be optimal. Over the years many algorithmic problems have been shown to be reducible from the 3SUM problem or its variants, including the more generalized forms of the problem, such as k-SUM and k-variate linear degeneracy testing (k-LDT). The conjectured hardness of these problems have become extremely popular for basing conditional lower bounds for numerous algorithmic problems in P.

In this paper, we show that the randomized 4-linear decision tree complexity of 3SUM is O(n^{3/2}), and that the randomized (2k-2)-linear decision tree complexity of k-SUM and k-LDT is O(n^{k/2}), for any odd >= 3. These bounds improve (albeit randomized) the corresponding O(n^{3/2} sqrt{log n}) and O(n^{k/2} sqrt{log n}) decision tree bounds obtained by Gr{\o}nlund and Pettie. Our technique includes a specialized randomized variant of fractional cascading data structure. Additionally, we give another deterministic algorithm for 3SUM that runs in O(n^2 log log n / log n ) time. The latter bound matches a recent independent bound by Freund [Algorithmica 2017], but our algorithm is somewhat simpler, due to a better use of the word-RAM model.

Subject Classification

Keywords
  • 3SUM
  • k-SUM
  • Linear Degeneracy
  • Linear Decision Trees
  • Fractional Cascading

Metrics

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

References

  1. A. Abboud and V. Vassilevska Williams. Popular conjectures imply strong lower bounds for dynamic problems. In Proc. 55th Annu. Sympos. on Foundations of Computer Science (FOCS), pages 434-443, 2014. Google Scholar
  2. A. Abboud, V. Vassilevska Williams, and H. Yu. Matching triangles and basing hardness on an extremely popular conjecture. In Proc. 47th Annu. ACM on Sympos. on Theory of Computing (STOC), pages 41-50, 2015. Google Scholar
  3. O. Aichholzer, F. Aurenhammer, E. D. Demaine, F. Hurtado, P. Ramos, and J. Urrutia. On k-convex polygons. Comput. Geom., 45(3):73-87, 2012. Google Scholar
  4. N. Ailon and B. Chazelle. Lower bounds for linear degeneracy testing. J. ACM, 52(2):157-171, 2005. Google Scholar
  5. A. Amir, T. M. Chan, M. Lewenstein, and N. Lewenstein. On hardness of jumbled indexing. In Proc. 41st Int'l Colloq. on Automata, Languages, and Programming (ICALP), pages 114-125, 2014. Google Scholar
  6. A. Amir, T. Kopelowitz, A. Levy, S. Pettie, E. Porat, and B. Riva Shalom. Mind the gap: Essentially optimal algorithms for online dictionary matching with one gap. In Proc. 27th Int'l Sympos. on Algorithms and Computation (ISAAC), pages 12:1-12:12, 2016. Google Scholar
  7. G. Barequet and S. Har-Peled. Polygon containment and translational min-Hausdorff-distance between segment sets are 3SUM-hard. Int. J. Comput. Geometry Appl., 11(4):465-474, 2001. Google Scholar
  8. R. C. Buck. Partition of space. Amer. Math. Monthly, 50:541-544, 1943. Google Scholar
  9. A. Butman, P. Clifford, R. Clifford, M. Jalsenius, N. Lewenstein, B. Porat, E. Porat, and B. Sach. Pattern matching under polynomial transformation. SIAM J. Comput., 42(2):611-633, 2013. Google Scholar
  10. J. Cardinal, J. Iacono, and A. Ooms. Solving k-SUM using few linear queries. In Proc. 24th Annu. European Sympos. on Algorithms (ESA), pages 25:1-25:17, 2016. Google Scholar
  11. M. L. Carmosino, J. Gao, R. Impagliazzo, I. Mihajlin, R. Paturi, and S. Schneider. Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility. In Proc. 2016 ACM Conference on Innovations in Theoretical Computer Science, pages 261-270, 2016. Google Scholar
  12. B. Chazelle and L. J. Guibas. Fractional cascading: I. A data structuring technique. Algorithmica, 1(2):133-162, 1986. Google Scholar
  13. B. Chazelle and L. J. Guibas. Fractional cascading: II. Applications. Algorithmica, 1(2):163-191, 1986. Google Scholar
  14. E. D. Demaine, J. S. B. Mitchell, and J. O'Rourke. The open problems project. Accessed: 2015-10-28. Google Scholar
  15. H. Edelsbrunner, J. O'Rourke, and R. Seidel. Constructing arrangements of lines and hyperplanes with applications. SIAM J. Comput., 15(2):341-363, 1986. Google Scholar
  16. J. Erickson. Bounds for linear satisfiability problems. Theor. Comput. Sci, 8:388-395, 1999. Google Scholar
  17. E. Ezra and M. Sharir. A nearly quadratic bound for the decision tree complexity of k-SUM. To Appear in Proc. 33st Int'l Sympos. on Computational Geometry (SoCG), 2017. Google Scholar
  18. M. L. Fredman. How good is the information theory bound in sorting? Theor. Comput. Sci, 1(4):355-361, 1976. Google Scholar
  19. A. Freund. Improved subquadratic 3SUM. Algorithmica, 77(2):440-458, 2017. Google Scholar
  20. A. Gajentaan and M. H. Overmars. On a class of O(n²) problems in computational geometry. Comput. Geom., 5:165-185, 1995. Google Scholar
  21. O. Gold and M. Sharir. Improved bounds for 3SUM, k-SUM, and linear degeneracy. CoRR, abs/1512.05279, 2015. URL: http://arxiv.org/abs/1512.05279.
  22. A. Grønlund and S. Pettie. Threesomes, degenerates, and love triangles. In Proc. 55th Annu. Sympos. on Foundations of Computer Science (FOCS), pages 621-630, 2014. Google Scholar
  23. A. Hernández-Barrera. Finding an o(n²log n) algorithm is sometimes hard. In Proc. 8th Canadian Conference on Computational Geometry, pages 289-294, 1996. Google Scholar
  24. R. Impagliazzo and R. Paturi. On the complexity of k-SAT. J. Comput. Syst. Sci., 62(2):367-375, March 2001. Google Scholar
  25. R. Impagliazzo, R. Paturi, and F. Zane. Which problems have strongly exponential complexity? J. Comput. Syst. Sci., 63(4):512-530, 2001. Google Scholar
  26. D. M. Kane, S. Lovett, and S. Moran. Near-optimal linear decision trees for k-SUM and related problems. CoRR, abs/1705.01720, 2017. Google Scholar
  27. T. Kopelowitz, S. Pettie, and E. Porat. Higher lower bounds from the 3SUM conjecture. In Proc. 27th Annu. ACM-SIAM Sympos. on Discrete Algorithms (SODA), pages 1272-1287, 2016. Google Scholar
  28. A. Lincoln, V. Vassilevska Williams, J. R. Wang, and R. Williams. Deterministic time-space trade-offs for k-SUM. In Proc. 43rd Int'l Colloq. on Automata, Languages, and Programming (ICALP), pages 58:1-58:14, 2016. Google Scholar
  29. M. Pǎtraşcu. Towards polynomial lower bounds for dynamic problems. In Proc. 42nd ACM Sympos. on Theory of Computing (STOC), pages 603-610, 2010. Google Scholar
  30. M. A. Soss, J. Erickson, and M. H. Overmars. Preprocessing chains for fast dihedral rotations is hard or even impossible. Comput. Geom., 26(3):235-246, 2003. Google Scholar
  31. O. Weimann, A. Abboud, and V. Vassilevska Williams. Consequences of faster sequence alignment. In Proc. 41st Int'l Colloq. on Automata, Languages, and Programming (ICALP), pages 39-51, 2014. Google Scholar
  32. V. Vassilevska Williams and R. Williams. Subcubic equivalences between path, matrix and triangle problems. In Proc. 51st Annu. IEEE Sympos. on Foundations of Computer Science (FOCS), pages 645-654, 2010. 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