{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,7]],"date-time":"2026-03-07T18:31:02Z","timestamp":1772908262608,"version":"3.50.1"},"reference-count":11,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2015,10,19]],"date-time":"2015-10-19T00:00:00Z","timestamp":1445212800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2017,2]]},"DOI":"10.1007\/s00453-015-0079-6","type":"journal-article","created":{"date-parts":[[2015,10,19]],"date-time":"2015-10-19T10:13:43Z","timestamp":1445249623000},"page":"440-458","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["Improved Subquadratic 3SUM"],"prefix":"10.1007","volume":"77","author":[{"given":"Ari","family":"Freund","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,10,19]]},"reference":[{"issue":"2","key":"79_CR1","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1145\/1059513.1059515","volume":"52","author":"N Ailon","year":"2005","unstructured":"Ailon, N., Chazelle, B.: Lower bounds for linear degeneracy testing. J. ACM 52(2), 157\u2013171 (2005)","journal-title":"J. ACM"},{"issue":"4","key":"79_CR2","doi-asserted-by":"crossref","first-page":"584","DOI":"10.1007\/s00453-007-9036-3","volume":"50","author":"I Baran","year":"2008","unstructured":"Baran, I., Demaine, E.D., P\u01cetra\u015fcu, M.: Subquadratic algorithms for 3SUM. Algorithmica 50(4), 584\u2013596 (2008)","journal-title":"Algorithmica"},{"issue":"2","key":"79_CR3","doi-asserted-by":"crossref","first-page":"611","DOI":"10.1137\/110853327","volume":"42","author":"A Butman","year":"2013","unstructured":"Butman, A., Clifford, P., Clifford, R., Jalsenius, M., Lewenstein, N., Porat, B., Porat, E., Sach, B.: Pattern matching under polynomial transformation. SIAM J. Comput. 42(2), 611\u2013633 (2013)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"79_CR4","doi-asserted-by":"crossref","first-page":"236","DOI":"10.1007\/s00453-007-9062-1","volume":"50","author":"TM Chan","year":"2008","unstructured":"Chan, T.M.: All-pairs shortest paths with real weights in $$\\text{ O }(n^3\/\\log n)$$ O ( n 3 \/ log n ) time. Algorithmica 50(2), 236\u2013243 (2008)","journal-title":"Algorithmica"},{"key":"79_CR5","doi-asserted-by":"crossref","unstructured":"Chan, T.M.: Speeding up the four Russians algorithm by about one more logarithmic factor. In: Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 212\u2013217. Society for Industrial and Applied Mathematics, Philadelphia (2015)","DOI":"10.1137\/1.9781611973730.16"},{"key":"79_CR6","first-page":"388","volume":"8","author":"J Erickson","year":"1997","unstructured":"Erickson, J.: Lower bounds for linear satisfiability problems. Chic. J. Theor. Comput. Sci. 8, 388\u2013395 (1997)","journal-title":"Chic. J. Theor. Comput. Sci."},{"issue":"3","key":"79_CR7","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1016\/0925-7721(95)00022-2","volume":"5","author":"A Gajentaan","year":"1995","unstructured":"Gajentaan, A., Overmars, M.H.: On a class of $$\\text{ O }(n^2)$$ O ( n 2 ) problems in computational geometry. Comput. Geom. 5(3), 165\u2013185 (1995)","journal-title":"Comput. Geom."},{"key":"79_CR8","doi-asserted-by":"crossref","unstructured":"Gr\u00f8nlund, A., Pettie, S.: Threesomes, degenerates, and love triangles. In: Proceedings of the 55th IEEE Symposium on Foundations of Computer Science. ArXiv preprint arXiv:1404.0799 (2014)","DOI":"10.1109\/FOCS.2014.72"},{"key":"79_CR9","unstructured":"Impagliazzo, R., Lovett, S., Paturi, R., Schneider, S.: 0\u20131 Integer linear programming with a linear number of constraints. ArXiv preprint arXiv:1401.5512 (2014)"},{"key":"79_CR10","doi-asserted-by":"crossref","unstructured":"P\u01cetra\u015fcu, M.: Towards polynomial lower bounds for dynamic problems. In: Proceedings of the Forty-Second ACM Symposium on Theory of Computing, pp. 603\u2013610. Association for Computing Machinery, New York (2010)","DOI":"10.1145\/1806689.1806772"},{"key":"79_CR11","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry, an Introduction","author":"FP Preparata","year":"1985","unstructured":"Preparata, F.P., Shamos, M.I.: Computational Geometry, an Introduction. Springer, New York (1985)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0079-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-015-0079-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0079-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0079-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,31]],"date-time":"2019-08-31T14:09:24Z","timestamp":1567260564000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-015-0079-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,10,19]]},"references-count":11,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,2]]}},"alternative-id":["79"],"URL":"https:\/\/doi.org\/10.1007\/s00453-015-0079-6","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,10,19]]}}}