Threesomes, Degenerates, and Love Triangles

Abstract

The 3SUM problem is to decide, given a set of n real numbers, whether any three sum to zero. It is widely conjectured that a trivial O(n²)-time algorithm is optimal on the Real RAM, and optimal even in the nonuniform linear decision tree model. Over the years the consequences of this conjecture have been revealed. This 3SUM conjecture implies Ω (n²) lower bounds on numerous problems in computational geometry, and a variant of the conjecture for integer inputs implies strong lower bounds on triangle enumeration, dynamic graph algorithms, and string matching data structures.

In this article, we refute the conjecture that 3SUM requires Ω (n²) in the Real RAM and refute more forcefully the conjecture that its complexity is Ω (n²) in the linear decision tree model. In particular, we prove that the decision tree complexity of 3SUM is O(n^3/2√ log n) and give two subquadratic 3SUM algorithms, a deterministic one running in O(n² / (log n/ log log n)^2/3) time and a randomized one running in O(n²(log log n)² / log n) time with high probability. Our results lead directly to improved bounds on the decision tree complexity of k-variate linear degeneracy testing for all odd k≥ 3.

Finally, we give a subcubic algorithm for a generalization of the (min ,+)-product over real-valued matrices and apply it to the problem of finding zero-weight triangles in edge-weighted graphs. We give a depth-O(n^5/2√ log n) decision tree for this problem, as well as a deterministic algorithm running in time O(n³ (log log n)²/log n).

References

1. S. Aaronson and Y. Shi. 2004. Quantum lower bounds for the collision and the element distinctness problems. J. ACM 51, 4 (2004), 595--605.
2. A. Abboud, A. Backurs, and V. Vassilevska Williams. 2015. Tight hardness results for LCS and other sequence similarity measures. In Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS’15). 59--78.
3. A. Abboud, F. Grandoni, and V. Vassilevska Williams. 2015. Subcubic equivalences between graph centrality problems, APSP and diameter. In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’15). 1681--1697.
4. A. Abboud and V. V. Williams. 2014. Popular conjectures imply strong lower bounds for dynamic problems. In Proceedings of the 55th Annual IEEE Symposium on Foundations of Computer Science (FOCS’14). 434--443. Retrieved from
5. A. Abboud, V. Vassilevska Williams, and O. Weimann. 2014. Consequences of faster sequence alignment. In Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP’14). 39--51.
6. A. V. Aho, J. E. Hopcroft, and J. D. Ullman. 1975. The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, MA.
7. O. Aichholzer, F. Aurenhammer, E. D. Demaine, F. Hurtado, P. Ramos, and J. Urrutia. 2012. On k-convex polygons. Comput. Geom. 45, 3 (2012), 73--87.
8. N. Ailon and B. Chazelle. 2005. Lower bounds for linear degeneracy testing. J. ACM 52, 2 (2005), 157--171.
9. N. Alon and R. B. Boppana. 1987. The monotone circuit complexity of boolean functions. Combinatorica 7, 1 (1987), 1--22.
10. A. Amir, T. M. Chan, M. Lewenstein, and N. Lewenstein. 2014. Consequences of faster sequence alignment. In Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP’14). 114--125.
11. A. Amir, T. Kopelowitz, A. Levy, S. Pettie, E. Porat, and B. R. Shalom. 2016. Mind the gap: Essentially optimal algorithms for online dictionary matching with one gap. In Proceedings of the 27th International Symposium on Algorithms and Computation (ISAAC’16). 12:1--12:12. Retrieved from
12. A. Backurs and P. Indyk. 2015. Edit distance cannot be computed in strongly subquadratic time (unless SETH is false). In Proceedings of the 47th Annual ACM Symposium on Theory of Computing (STOC’15). 51--58.
13. I. Baran, E. D. Demaine, and M. Pǎtraşcu. 2008. Subquadratic algorithms for 3SUM. Algorithmica 50, 4 (2008), 584--596.
14. L. Barba, J. Cardinal, J. Iacono, S. Langerman, A. Ooms, and N. Solomon. 2017. Subquadratic algorithms for algebraic generalizations of 3SUM. In Proceedings of the 33rd International Symposium on Computational Geometry (SoCG’17). 13:1--13:15. Retrieved from
15. G. Barequet and S. Har-Peled. 2001. Polygon containment and translational min-Hausdorff-distance between segment sets are 3SUM-hard. Int. J. Comput. Geometry Appl. 11, 4 (2001), 465--474.
16. P. Beame. 1991. A general sequential time-space tradeoff for finding unique elements. SIAM J. Comput. 20, 2 (1991), 270--277. Retrieved from
17. C. H. Bennett, E. Bernstein, G. Brassard, and U. V. Vazirani. 1997. Strengths and weaknesses of quantum computing. SIAM J. Comput. 26, 5 (1997), 1510--1523.
18. A. Bjorklund, R. Pagh, V. Vassilevska Williams, and U. Zwick. 2014. Listing triangles. In Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP’14). 223--234.
19. M. Blum, R. W. Floyd, V. Pratt, R. L. Rivest, and R. E. Tarjan. 1973. Time bounds for selection. J. Comput. Syst. Sci. 7, 4 (1973), 448--461.
20. M. Braverman, Y. K. Ko, and O. Weinstein. 2015. Approximating the best nash equilibrium in n^{o(log n)}-time breaks the exponential time hypothesis. In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’15). 970--982.
21. D. Bremner, T. M. Chan, E. D. Demaine, J. Erickson, F. Hurtado, J. Iacono, S. Langerman, M. Pǎtraşcu, and P. Taslakian. 2014. Necklaces, convolutions, and X + Y. Algorithmica 69 (2014), 294--314.
22. K. Bringmann. 2014. Why walking the dog takes time: Fréchet distance has no strongly subquadratic algorithms unless SETH fails. In Proceedings of the 55th Annual IEEE Symposium on Foundations of Computer Science (FOCS’14). 661--670.
23. K. Bringmann and M. Künnemann. 2015. Quadratic conditional lower bounds for string problems and dynamic time warping. In Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS’15). 79--97.
24. R. C. Buck. 1943. Partition of space. Amer. Math. Monthly 50 (1943), 541--544.
25. A. Butman, P. Clifford, R. Clifford, M. Jalsenius, N. Lewenstein, B. Porat, E. Porat, and B. Sach. 2013. Pattern matching under polynomial transformation. SIAM J. Comput. 42, 2 (2013), 611--633.
26. C. Calabro, R. Impagliazzo, and R. Paturi. 2009. The complexity of satisfiability of small depth circuits. In Proceedings of the 4th International Workshop on Parameterized and Exact Computation (IWPEC’09). 75--85. Retrieved from
27. M. L. Carmosino, J. Gao, R. Impagliazzo, I. Mihajlin, R. Paturi, and S. Schneider. 2016. Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility. In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science (ITCS’16). 261--270. Retrieved from
28. T. M. Chan. 2008. All-pairs shortest paths with real weights in O (n³/log n) time. Algorithmica 50, 2 (2008), 236--243.
29. T. M. Chan. 2015. Speeding up the four russians algorithm by about one more logarithmic factor. In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’15). 212--217.
30. T. M. Chan. 2018. More logarithmic-factor speedups for 3SUM, (median, +)-convolution, and some geometric 3SUM-hard problems. In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’18). 881--897. Retrieved from
31. T. M. Chan and M. Lewenstein. 2015. Clustered integer 3SUM via additive combinatorics. In Proceedings of the 47th Annual ACM on Symposium on Theory of Computing (STOC’15). 31--40.
32. S. Chechik, D. Larkin, L. Roditty, G. Schoenebeck, R. E. Tarjan, and V. Vassilevska Williams. 2014. Better approximation algorithms for the graph diameter. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’14). 1041--1052.
33. K.-Y. Chen, P.-H. Hsu, and K.-M. Chao. 2009. Approximate matching for run-length encoded strings is 3SUM-hard. In Combinatorial Pattern Matching. Lecture Notes in Computer Science, Vol. 5577. Springer, 168--179.
34. N. Chiba and T. Nishizeki. 1985. Arboricity and subgraph listing algorithms. SIAM J. Comput. 14, 1 (1985), 210--223.
35. R. Duan and S. Pettie. 2010. Connectivity oracles for failure prone graphs. In Proceedings of the 42nd ACM Symposium on Theory of Computing. 465--474.
36. R. Duan and S. Pettie. 2017. Connectivity oracles for graphs subject to vertex failures. In Proceedings of the 28th ACM-SIAM Symposium on Discrete Algorithms (SODA’17). 490--509.
37. D. P. Dubhashi and A. Panconesi. 2009. Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press.
38. H. Edelsbrunner, J. O’Rourke, and R. Seidel. 1986. Constructing arrangements of lines and hyperplanes with applications. SIAM J. Comput. 15, 2 (1986), 341--363.
39. J. Erickson. 1999. Bounds for linear satisfiability problems. Chicago J. Theor. Comput. Sci. 1999, 8 (1999).
40. M. L. Fredman. 1976. How good is the information theory bound in sorting? Theor. Comput. Sci. 1, 4 (1976), 355--361.
41. M. L. Fredman. 1976. New bounds on the complexity of the shortest path problem. SIAM J. Comput. 5, 1 (1976), 83--89.
42. M. L. Fredman and M. Saks. 1989. The cell probe complexity of dynamic data structures. In Proceedings of the 21st Annual ACM Symposium on Theory of Computing (STOC’89). 345--354.
43. A. Freund. 2017. Improved subquadratic 3SUM. Algorithmica 77, 2 (2017), 440--458. Retrieved from
44. A. Gajentaan and M. H. Overmars. 1995. On a class of O/(n²) problems in computational geometry. Comput. Geom. 5 (1995), 165--185.
45. O. Gold and M. Sharir. 2017. Improved bounds for 3SUM, k-SUM, and linear degeneracy. In Proceedings of the 25th Annual European Symposium on Algorithms (ESA’17) (Leibniz International Proceedings in Informatics (LIPIcs)), Kirk Pruhs and Christian Sohler (Eds.), Vol. 87. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 42:1--42:13. Retrieved from
46. A. Grønlund and S. Pettie. 2014. Threesomes, degenerates, and love triangles. In Proceedings of the 55th IEEE Symposium on Foundations of Computer Science (FOCS’14). 621--630.
47. J. Hartmanis and R. E. Stearns. 1965. On the computational complexity of algorithms. Trans. Amer. Math. Soc. 117 (1965), 285--306.
48. J. Håstad. 1986. Almost optimal lower bounds for small depth circuits. In Proceedings of the 18th Annual ACM Symposium on Theory of Computing (STOC’86). 6--20.
49. M. Henzinger, S. Krinninger, D. Nanongkai, and T. Saranurak. 2015. Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture. In Proceedings of the 47th Annual ACM Symposium on Theory of Computing (STOC’15). 21--30.
50. R. Impagliazzo, S. Lovett, R. Paturi, and S. Schneider. 2014. 0-1 integer linear programming with a linear number of constraints. Electron. Colloq. Comput. Complex. (ECCC) 21 (2014), 24.
51. R. Impagliazzo and R. Paturi. 2001. On the complexity of k-SAT. J. Comput. Syst. Sci. 62, 2 (2001), 367--375.
52. R. Impagliazzo, R. Paturi, and F. Zane. 2001. Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63, 4 (2001), 512--530.
53. Z. Jafargholi and E. Viola. 2016. 3SUM, 3XOR, triangles. Algorithmica 74, 1 (2016), 326--343. Retrieved from
54. D. Kane, S. Lovett, and S. Moran. 2018. Near-optimal linear decision trees for k-SUM and related problems. In Proceedings of the 50th ACM Symposium on Theory of Computing (STOC’18).
55. T. Kopelowitz, S. Pettie, and E. Porat. 2015. Dynamic set intersection. In Proceedings of the 14th International Symposium on Algorithms and Data Structures (WADS’15). 470--481.
56. T. Kopelowitz, S. Pettie, and E. Porat. 2016. Higher lower bounds from the 3SUM conjecture. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’16). 1272--1287. Retrieved from
57. K. G. Larsen. 2012. The cell probe complexity of dynamic range counting. In Proceedings of the 44th Symposium on Theory of Computing Conference (STOC’12). 85--94.
58. A. Lincoln, V. Vassilevska Williams, J. R. Wang, and R. R. Williams. 2016. Deterministic time-space trade-offs for k-SUM. In Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP’16). 58:1--58:14. Retrieved from
59. S. Meiser. 1993. Point location in arrangements of hyperplanes. Inf. Comput. 106, 2 (1993), 286--303.
60. F. Meyer auf der Heide. 1984. A polynomial linear search algorithm for the n-dimensional knapsack problem. J. ACM 31, 3 (1984), 668--676.
61. C. St. J. A. Nash-Williams. 1964. Decomposition of finite graphs into forests. J. London Math. Soc. 39 (1964), 12.
62. M. Pǎtraşcu and E. Demaine. 2006. Logarithmic lower bounds in the cell-probe model. SIAM J. Comput. 35, 4 (2006), 932--963.
63. F. P. Preparata and M. I. Shamos. 1985. Computational Geometry. Springer, New York.
64. M. Pǎtraşcu. 2010. Towards polynomial lower bounds for dynamic problems. In Proceedings 42nd ACM Symposium on Theory of Computing (STOC’10). 603--610.
65. M. Pǎtraşcu and R. Williams. 2010. On the possibility of faster SAT algorithms. In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’10). 1065--1075.
66. A. A. Razborov. 1985. Lower bounds for the monotone complexity of some boolean functions. Dokl. Ak. Nauk. USSR 281 (1985), 798--801(in Russian). English translation in Sov. Math. Dokl. 31 (1985): 354--357.
67. L. Roditty and V. Vassilevska Williams. 2013. Fast approximation algorithms for the diameter and radius of sparse graphs. In Proceedings of the 45th ACM Symposium on Theory of Computing (STOC’13). 515--524.
68. B. Saha. 2015. Language edit distance and maximum likelihood parsing of stochastic grammars: Faster algorithms and connection to fundamental graph problems. In Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS’15). 118--135. Retrieved from
69. M. A. Soss, J. Erickson, and M. H. Overmars. 2003. Preprocessing chains for fast dihedral rotations is hard or even impossible. Comput. Geom. 26, 3 (2003), 235--246.
70. V. Vassilevska Williams and R. Williams. 2010. Subcubic equivalences between path, matrix and triangle problems. In Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS’10). 645--654.
71. V. Vassilevska Williams and R. Williams. 2013. Finding, minimizing, and counting weighted subgraphs. SIAM J. Comput. 42, 3 (2013), 831--854.

Index Terms

• Mathematics of computing

  • Discrete mathematics

    • Combinatorics

      • Combinatorial algorithms

• Theory of computation

  • Computational complexity and cryptography

    • Oracles and decision trees