{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,27]],"date-time":"2026-04-27T04:43:51Z","timestamp":1777265031659,"version":"3.51.4"},"reference-count":71,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2018,4,24]],"date-time":"2018-04-24T00:00:00Z","timestamp":1524528000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001732","name":"Danish National Research Foundation","doi-asserted-by":"crossref","award":["DNRF84"],"award-info":[{"award-number":["DNRF84"]}],"id":[{"id":"10.13039\/501100001732","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1217338, CCF-1514383, and CCF-1637546"],"award-info":[{"award-number":["CCF-1217338, CCF-1514383, and CCF-1637546"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2018,8,31]]},"abstract":"<jats:p>\n            The 3SUM problem is to decide, given a set of\n            <jats:italic>n<\/jats:italic>\n            real numbers, whether any three sum to zero. It is widely conjectured that a trivial\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\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 \u03a9 (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\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.\n          <\/jats:p>\n          <jats:p>\n            In this article, we refute the conjecture that 3SUM requires \u03a9 (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            ) in the Real RAM and refute more forcefully the conjecture that its complexity is \u03a9 (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            ) in the linear decision tree model. In particular, we prove that the decision tree complexity of 3SUM is\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>3\/2<\/jats:sup>\n            \u221a log\n            <jats:italic>n<\/jats:italic>\n            ) and give two subquadratic 3SUM algorithms, a deterministic one running in\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            \/ (log\n            <jats:italic>n<\/jats:italic>\n            \/ log log\n            <jats:italic>n<\/jats:italic>\n            )\n            <jats:sup>2\/3<\/jats:sup>\n            ) time and a randomized one running in\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            (log log\n            <jats:italic>n<\/jats:italic>\n            )\n            <jats:sup>2<\/jats:sup>\n            \/ log\n            <jats:italic>n<\/jats:italic>\n            ) time with high probability. Our results lead directly to improved bounds on the decision tree complexity of\n            <jats:italic>k<\/jats:italic>\n            -variate linear degeneracy testing for all odd\n            <jats:italic>k<\/jats:italic>\n            \u2265 3.\n          <\/jats:p>\n          <jats:p>\n            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-\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>5\/2<\/jats:sup>\n            \u221a log\n            <jats:italic>n<\/jats:italic>\n            ) decision tree for this problem, as well as a deterministic algorithm running in time\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>3<\/jats:sup>\n            (log log\n            <jats:italic>n<\/jats:italic>\n            )\n            <jats:sup>2<\/jats:sup>\n            \/log\n            <jats:italic>n<\/jats:italic>\n            ).\n          <\/jats:p>","DOI":"10.1145\/3185378","type":"journal-article","created":{"date-parts":[[2018,4,25]],"date-time":"2018-04-25T12:22:17Z","timestamp":1524658937000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":26,"title":["Threesomes, Degenerates, and Love Triangles"],"prefix":"10.1145","volume":"65","author":[{"given":"Allan","family":"Gr\u00f8nlund","sequence":"first","affiliation":[{"name":"Aarhus University, Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Seth","family":"Pettie","sequence":"additional","affiliation":[{"name":"University of Michigan, Ann Arbor, MI"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,4,24]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1008731.1008735"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.14"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201915)","author":"Abboud A."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.53"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP\u201914)","author":"Abboud A."},{"key":"e_1_2_1_6_1","unstructured":"A. V. Aho J. E. Hopcroft and J. D. Ullman. 1975. The Design and Analysis of Computer Algorithms. Addison-Wesley Reading MA.   A. V. Aho J. E. Hopcroft and J. D. Ullman. 1975. The Design and Analysis of Computer Algorithms. Addison-Wesley Reading MA."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2011.09.001"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1059513.1059515"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579196"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP\u201914)","author":"Amir A."},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 27th International Symposium on Algorithms and Computation (ISAAC\u201916)","author":"Amir A."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746612"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/3118772.3119148"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 33rd International Symposium on Computational Geometry (SoCG\u201917)","author":"Barba L."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195901000596"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/0220017"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796300933"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP\u201914)","author":"Bjorklund A."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(73)80033-9"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201915)","author":"Braverman M."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9734-3"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.76"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.15"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1943.11991447"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/110853327"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the 4th International Workshop on Parameterized and Exact Computation (IWPEC\u201909)","author":"Calabro C."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2840728.2840746"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/1341151.1341158"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/2722129.2722145"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/3174304.3175327"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746568"},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201914)","author":"Chechik S."},{"key":"e_1_2_1_33_1","series-title":"Lecture Notes in Computer Science","volume-title":"Combinatorial Pattern Matching","author":"Chen K.-Y."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214017"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806754"},{"key":"e_1_2_1_36_1","volume-title":"Proceedings of the 28th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201917)","author":"Duan R."},{"key":"e_1_2_1_37_1","doi-asserted-by":"crossref","unstructured":"D. P. Dubhashi and A. Panconesi. 2009. Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press.   D. P. Dubhashi and A. Panconesi. 2009. Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press.","DOI":"10.1017\/CBO9780511581274"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215024"},{"key":"e_1_2_1_39_1","article-title":"Bounds for linear satisfiability problems","volume":"1999","author":"Erickson J.","year":"1999","journal-title":"Chicago J. Theor. Comput. Sci."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90078-5"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1137\/0205006"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/73007.73040"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-015-0079-6"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(95)00022-2"},{"key":"e_1_2_1_45_1","volume-title":"Proceedings of the 25th Annual European Symposium on Algorithms (ESA\u201917) (Leibniz International Proceedings in Informatics (LIPIcs)), Kirk Pruhs and Christian Sohler (Eds.)","volume":"87","author":"Gold O."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.72"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1965-0170805-7"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/12130.12132"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746609"},{"key":"e_1_2_1_50_1","volume-title":"Electron. Colloq. Comput. Complex. (ECCC) 21","author":"Impagliazzo R.","year":"2014"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1727"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-014-9946-9"},{"key":"e_1_2_1_54_1","volume-title":"Proceedings of the 50th ACM Symposium on Theory of Computing (STOC\u201918)","author":"Kane D."},{"key":"e_1_2_1_55_1","volume-title":"Proceedings of the 14th International Symposium on Algorithms and Data Structures (WADS\u201915)","author":"Kopelowitz T."},{"key":"e_1_2_1_56_1","volume-title":"Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201916)","author":"Kopelowitz T."},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2213987"},{"key":"e_1_2_1_58_1","volume-title":"Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP\u201916)","author":"Lincoln A."},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1993.1057"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/828.322450"},{"key":"e_1_2_1_61_1","first-page":"12","article-title":"Decomposition of finite graphs into forests","volume":"39","author":"St C.","year":"1964","journal-title":"J. London Math. Soc."},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705447256"},{"key":"e_1_2_1_63_1","doi-asserted-by":"crossref","unstructured":"F. P. Preparata and M. I. Shamos. 1985. Computational Geometry. Springer New York.   F. P. Preparata and M. I. Shamos. 1985. Computational Geometry. Springer New York.","DOI":"10.1007\/978-1-4612-1098-6"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806772"},{"key":"e_1_2_1_65_1","volume-title":"Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201910)","author":"P\u01cetra\u015fcu M."},{"key":"e_1_2_1_66_1","first-page":"798","article-title":"Lower bounds for the monotone complexity of some boolean functions","volume":"281","author":"Razborov A. A.","year":"1985","journal-title":"Dokl. Ak. Nauk. USSR"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488673"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.17"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(02)00156-6"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.67"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1137\/09076619X"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3185378","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3185378","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3185378","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:26:36Z","timestamp":1750213596000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3185378"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,4,24]]},"references-count":71,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,8,31]]}},"alternative-id":["10.1145\/3185378"],"URL":"https:\/\/doi.org\/10.1145\/3185378","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,4,24]]},"assertion":[{"value":"2015-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-04-24","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}