{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:57Z","timestamp":1740109317930,"version":"3.37.3"},"reference-count":50,"publisher":"Springer Science and Business Media LLC","issue":"11","license":[{"start":{"date-parts":[[2022,8,22]],"date-time":"2022-08-22T00:00:00Z","timestamp":1661126400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,8,22]],"date-time":"2022-08-22T00:00:00Z","timestamp":1661126400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["1909634"],"award-info":[{"award-number":["1909634"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000893","name":"Simons Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000893","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100012652","name":"ETH Z\u00fcrich Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100012652","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,11]]},"DOI":"10.1007\/s00453-022-01014-x","type":"journal-article","created":{"date-parts":[[2022,8,22]],"date-time":"2022-08-22T13:06:12Z","timestamp":1661173572000},"page":"3156-3191","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["The Fine-Grained Complexity of Multi-Dimensional Ordering Properties"],"prefix":"10.1007","volume":"84","author":[{"given":"Haozhe","family":"An","sequence":"first","affiliation":[]},{"given":"Mohit","family":"Gurumukhani","sequence":"additional","affiliation":[]},{"given":"Russell","family":"Impagliazzo","sequence":"additional","affiliation":[]},{"given":"Michael","family":"Jaber","sequence":"additional","affiliation":[]},{"given":"Marvin","family":"K\u00fcnnemann","sequence":"additional","affiliation":[]},{"given":"Maria Paula","family":"Parga Nina","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,8,22]]},"reference":[{"key":"1014_CR1","doi-asserted-by":"crossref","unstructured":"Abboud, A., Backurs, A., Williams, V.V.: Tight hardness results for LCS and other sequence similarity measures. In: Foundations of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium on, pp. 59\u201378. IEEE (2015)","DOI":"10.1109\/FOCS.2015.14"},{"key":"1014_CR2","doi-asserted-by":"crossref","unstructured":"Abboud, A., Bringmann, K., Dell, H., Nederlof, J.: More consequences of falsifying SETH and the orthogonal vectors conjecture. In: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pp. 253\u2013266. ACM (2018)","DOI":"10.1145\/3188745.3188938"},{"key":"1014_CR3","doi-asserted-by":"crossref","unstructured":"Abboud, A., Grandoni, F., Williams, V.V.: Subcubic equivalences between graph centrality problems, apsp and diameter. In: Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms, pp. 1681\u20131697. SIAM (2014)","DOI":"10.1137\/1.9781611973730.112"},{"key":"1014_CR4","doi-asserted-by":"crossref","unstructured":"Abboud, A., Williams, R., Yu, H.: More applications of the polynomial method to algorithm design. In: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 218\u2013230. SIAM (2015)","DOI":"10.1137\/1.9781611973730.17"},{"key":"1014_CR5","doi-asserted-by":"crossref","unstructured":"Abboud, A., Williams, V.V., Wang, J.R.: Approximation and fixed parameter subquadratic algorithms for radius and diameter in sparse graphs. In: Krauthgamer, R. (ed.) Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, January 10-12, 2016, pp. 377\u2013391. SIAM, Arlington, VA, USA (2016)","DOI":"10.1137\/1.9781611974331.ch28"},{"key":"1014_CR6","doi-asserted-by":"crossref","unstructured":"Abboud, A., Williams, V.V., Weimann, O.: Consequences of faster alignment of sequences. In: International Colloquium on Automata, Languages, and Programming, pp. 39\u201351. Springer (2014)","DOI":"10.1007\/978-3-662-43948-7_4"},{"key":"1014_CR7","unstructured":"Abiteboul, S., Hull, R., Vianu, V.: Foundations of databases: The logical level. Addison-Wesley Longman Publishing Co., Inc., Boston, MA (1995)"},{"key":"1014_CR8","unstructured":"Agarwal, P.K.: Range searching. In: Goodman, J.E., O\u2019Rourke, J., T\u00f3th, C.D. (eds.) Handbook of Discrete and Computational Geometry, chapter\u00a040. 3rd edition, CRC Press LLC (2017)"},{"key":"1014_CR9","doi-asserted-by":"crossref","unstructured":"Agarwal, U., Ramachandran, V.: Fine-grained complexity for sparse graphs. In: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, pp. 239\u2013252 (2018)","DOI":"10.1145\/3188745.3188888"},{"issue":"3","key":"1014_CR10","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1007\/BF02523189","volume":"17","author":"N Alon","year":"1997","unstructured":"Alon, N., Yuster, R., Zwick, U.: Finding and counting given length cycles. Algorithmica 17(3), 209\u2013223 (1997)","journal-title":"Algorithmica"},{"key":"1014_CR11","doi-asserted-by":"crossref","unstructured":"Alstrup, S., Brodal, G.S., Rauhe, T.: New data structures for orthogonal range searching. In: 41st Annual Symposium on Foundations of Computer Science, FOCS 2000, 12-14 November 2000, pp. 198\u2013207. IEEE Computer Society, Redondo Beach, California, USA (2000)","DOI":"10.1109\/SFCS.2000.892088"},{"key":"1014_CR12","doi-asserted-by":"crossref","unstructured":"Backurs, A., Indyk, P.: Edit distance cannot be computed in strongly subquadratic time (unless SETH is false). In: Proceedings of the forty-seventh annual ACM symposium on Theory of computing, pp. 51\u201358. ACM (2015)","DOI":"10.1145\/2746539.2746612"},{"key":"1014_CR13","doi-asserted-by":"crossref","unstructured":"Backurs, A., Roditty, L., Segal, G., Williams, V.V., Wein, N.: Towards tight approximation bounds for graph diameter and eccentricities. In: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pp. 267\u2013280. ACM (2018)","DOI":"10.1145\/3188745.3188950"},{"key":"1014_CR14","doi-asserted-by":"crossref","unstructured":"Bringmann, K.: Why walking the dog takes time: Frechet distance has no strongly subquadratic algorithms unless seth fails. In: Foundations of Computer Science (FOCS), 2014 IEEE 55th Annual Symposium on, pp. 661\u2013670. IEEE (2014)","DOI":"10.1109\/FOCS.2014.76"},{"key":"1014_CR15","unstructured":"Bringmann, K., Fischer, N., K\u00fcnnemann, M.: A fine-grained analogue of schaefer\u2019s theorem in P: dichotomy of exists k-forall-quantified first-order graph properties. In: Shpilka, A. (ed.) 34th Computational Complexity Conference, CCC 2019, July 18-20, 2019, New Brunswick, NJ, USA, volume 137 of LIPIcs, pp. 31:1\u201331:27. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2019)"},{"key":"1014_CR16","doi-asserted-by":"crossref","unstructured":"Bringmann, K., K\u00fcnnemann, M.: Quadratic conditional lower bounds for string problems and dynamic time warping. In: Foundations of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium on, pp. 79\u201397. IEEE (2015)","DOI":"10.1109\/FOCS.2015.15"},{"key":"1014_CR17","doi-asserted-by":"crossref","unstructured":"Carmosino, M.L., Gao, J., Impagliazzo, R., Mihajlin, I., Paturi, R., Schneider, S.: Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility. In: Sudan, M. (ed.) Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, Cambridge, MA, USA, January 14-16, 2016, pp. 261\u2013270. ACM (2016)","DOI":"10.1145\/2840728.2840746"},{"issue":"4","key":"1014_CR18","doi-asserted-by":"publisher","first-page":"899","DOI":"10.1007\/s00454-019-00062-5","volume":"61","author":"Timothy M Chan","year":"2019","unstructured":"Chan, Timothy M.: Orthogonal range searching in moderate dimensions: k-d trees and range trees strike back. Discret. Comput. Geom. 61(4), 899\u2013922 (2019)","journal-title":"Discret. Comput. Geom."},{"key":"1014_CR19","doi-asserted-by":"crossref","unstructured":"Chan, T.M., Larsen, K.G., Patrascu, M.: Orthogonal range searching on the ram, revisited. In: Hurtado, F., van Kreveld, M.J. (eds.) Proceedings of the 27th ACM Symposium on Computational Geometry, Paris, France, June 13-15, 2011, pp. 1\u201310. ACM (2011)","DOI":"10.1145\/1998196.1998198"},{"issue":"1","key":"1014_CR20","first-page":"27","volume":"10","author":"TM Chan","year":"2019","unstructured":"Chan, T.M., Skrepetos, D.: All-pairs shortest paths in geometric intersection graphs. JoCG 10(1), 27\u201341 (2019)","journal-title":"JoCG"},{"key":"1014_CR21","doi-asserted-by":"crossref","unstructured":"Chan, T.M., Williams, R.: Deterministic APSP, Orthogonal Vectors, and More: Quickly derandomizing Razborov-Smolensky. In: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1246\u20131255. SIAM (2016)","DOI":"10.1137\/1.9781611974331.ch87"},{"key":"1014_CR22","unstructured":"Chan, T.M., Zhou, G.: Multidimensional range selection. In: Elbassioni, K.M., Makino, K. (eds.) Algorithms and Computation - 26th International Symposium, ISAAC 2015, Nagoya, Japan, December 9-11, 2015, Proceedings, volume 9472 of Lecture Notes in Computer Science, pp. 83\u201392. Springer (2015)"},{"issue":"3","key":"1014_CR23","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1137\/0217026","volume":"17","author":"B Chazelle","year":"1988","unstructured":"Chazelle, B.: A functional approach to data structures and its use in multidimensional searching. SIAM J. Comput. 17(3), 427\u2013462 (1988)","journal-title":"SIAM J. Comput."},{"key":"1014_CR24","doi-asserted-by":"crossref","unstructured":"Chen, L., Williams, R.: An equivalence class for orthogonal vectors. In: Chan, T.M. (ed.) Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, January 6-9, 2019, pp. 21\u201340. SIAM, San Diego, California, USA (2019)","DOI":"10.1137\/1.9781611975482.2"},{"key":"1014_CR25","doi-asserted-by":"crossref","unstructured":"de\u00a0Berg, M., Bodlaender, H.L.., Kisfaludi-Bak, S., Marx, D., van\u00a0der Zanden, T.C..: A framework for eth-tight algorithms and lower bounds in geometric intersection graphs. In: Diakonikolas, I., Kempe,D., Henzinger, M. (eds.) Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, June 25-29, 2018, pp. 574\u2013586. ACM, Los Angeles, CA, USA (2018)","DOI":"10.1145\/3188745.3188854"},{"key":"1014_CR26","doi-asserted-by":"crossref","unstructured":"de\u00a0Berg, M., van Kreveld, M., Overmars, M., Schwarzkopf, O.C.: Orthogonal Range Searching, pp. 95\u2013120. Springer Berlin Heidelberg, Berlin, Heidelberg (2000)","DOI":"10.1007\/978-3-662-04245-8_5"},{"issue":"3","key":"1014_CR27","doi-asserted-by":"publisher","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 $$o(n^2)$$ problems in computational geometry. Comput. geom. 5(3), 165\u2013185 (1995)","journal-title":"Comput. geom."},{"key":"1014_CR28","unstructured":"Gao, J..: On the fine-grained complexity of least weight subsequence in multitrees and bounded treewidth dags. In: Jansen, B.M.P., Telle, J.A. (eds.) 14th International Symposium on Parameterized and Exact Computation, IPEC 2019, September 11-13, 2019, Munich, Germany, volume 148 of LIPIcs, pp. 16:1\u201316:17. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2019)"},{"key":"1014_CR29","unstructured":"Gao, J., Impagliazzo, R.: The fine-grained complexity of strengthenings of first-order logic. Electronic Colloquium on Computational Complexity (ECCC), 26, 9 (2019). URL: https:\/\/eccc.weizmann.ac.il\/report\/2019\/009"},{"key":"1014_CR30","doi-asserted-by":"crossref","unstructured":"Gao, J., Impagliazzo, R., Kolokolova, A., Williams, R.: Completeness for first-order properties on sparse structures with algorithmic applications. In: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201917, pp. 2162\u20132181 (2017)","DOI":"10.1137\/1.9781611974782.141"},{"key":"1014_CR31","doi-asserted-by":"crossref","unstructured":"Immerman, N.: Descriptive complexity. Graduate texts in computer science. Springer, New York, NY (1999)","DOI":"10.1007\/978-1-4612-0539-5"},{"key":"1014_CR32","unstructured":"Impagliazzo, R., Lovett, S., Paturi, R., Schneider, S.: 0-1 integer linear programming with a linear number of constraints. (2014). arXiv:1401.5512"},{"key":"1014_CR33","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Paturi, R., Schneider, S.: A satisfiability algorithm for sparse depth-2 threshold circuits. (2012). arXiv:1212.4548","DOI":"10.1109\/FOCS.2013.58"},{"key":"1014_CR34","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? In: Foundations of Computer Science, 1998. Proceedings. 39th Annual Symposium on, pp. 653\u2013662. IEEE (1998)","DOI":"10.1109\/SFCS.1998.743516"},{"key":"1014_CR35","doi-asserted-by":"crossref","unstructured":"J\u00e1J\u00e1, J.F., Mortensen, C.W., Shi, Q.: Space-efficient and fast algorithms for multidimensional dominance reporting and counting. In: Fleischer, R., Trippen, G. (eds.) Algorithms and Computation, 15th International Symposium, ISAAC 2004, Hong Kong, China, December 20-22, 2004, Proceedings, volume 3341 of Lecture Notes in Computer Science, pp. 558\u2013568. Springer (2004)","DOI":"10.1007\/978-3-540-30551-4_49"},{"key":"1014_CR36","unstructured":"Korhonen, T.: On multidimensional range queries. (2019). https:\/\/laakeri.kapsi.fi\/a\/rmq.pdf, Accessed: 2021-06-27"},{"key":"1014_CR37","unstructured":"K\u00fcnnemann, M., Marx, D.: Finding small satisfying assignments faster than brute force: A fine-grained perspective into boolean constraint satisfaction. In: Saraf, S. (ed.) 35th Computational Complexity Conference, CCC 2020, July 28-31, 2020, Saarbr\u00fccken, Germany (Virtual Conference), volume 169 of LIPIcs, pp. 27:1\u201327:28. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2020)"},{"key":"1014_CR38","unstructured":"K\u00fcnnemann, M., Paturi, R., Schneider, S.: On the Fine-Grained Complexity of One-Dimensional Dynamic Programming. In: 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), volume\u00a080 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 21:1\u201321:15 (2017)"},{"key":"1014_CR39","unstructured":"Lau, J., Ritossa, A.: Algorithms and hardness for multidimensional range updates and queries. In: Lee, J.R. (ed.) 12th Innovations in Theoretical Computer Science Conference, ITCS 2021, January 6-8, 2021, Virtual Conference, volume 185 of LIPIcs, pp. 35:1\u201335:20. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2021)"},{"key":"1014_CR40","doi-asserted-by":"crossref","unstructured":"Lincoln, A., Williams, V.V., Williams, R.: Tight hardness for shortest cycles and paths in sparse graphs. In: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1236\u20131252. Society for Industrial and Applied Mathematics (2018)","DOI":"10.1137\/1.9781611975031.80"},{"key":"1014_CR41","doi-asserted-by":"crossref","unstructured":"Lueker, G.S.: A data structure for orthogonal range queries. In: 19th Annual Symposium on Foundations of Computer Science, 16-18 October 1978, pp. 28\u201334. IEEE Computer Society, Ann Arbor, Michigan, USA (1978)","DOI":"10.1109\/SFCS.1978.1"},{"key":"1014_CR42","unstructured":"Marx, D., Sidiropoulos, A.: The limited blessing of low dimensionality: when 1-1\/d is the best possible exponent for d-dimensional geometric problems. In: Cheng, S.-W., Devillers, O. (eds.) 30th Annual Symposium on Computational Geometry, SOCG\u201914, June 08 - 11, 2014, pp. 67. ACM, Kyoto, Japan (2014)"},{"key":"1014_CR43","doi-asserted-by":"crossref","unstructured":"Moeller, D., Paturi, R., Schneider, S.: Subquadratic algorithms for succinct stable matching. In: International Computer Science Symposium in Russia, pp. 294\u2013308. Springer (2016)","DOI":"10.1007\/978-3-319-34171-2_21"},{"issue":"4","key":"1014_CR44","doi-asserted-by":"publisher","first-page":"342","DOI":"10.1016\/j.comgeo.2008.09.001","volume":"42","author":"Yakov Nekrich","year":"2009","unstructured":"Nekrich, Yakov: Orthogonal range searching in linear and almost-linear space. Comput. Geom. 42(4), 342\u2013351 (2009)","journal-title":"Comput. Geom."},{"key":"1014_CR45","doi-asserted-by":"crossref","unstructured":"Patrascu, M., Williams, R.: On the possibility of faster SAT algorithms. In: SODA, volume\u00a010, pp. 1065\u20131075. SIAM (2010)","DOI":"10.1137\/1.9781611973075.86"},{"key":"1014_CR46","unstructured":"Willard, D.E..: Predicate-oriented Database Search Algorithms. Center for Research in Computing Technology: Center for Research in Computing Technology. Garland Pub., (1979). URL: https:\/\/books.google.de\/books?id=iLQmAAAAMAAJ"},{"issue":"2\u20133","key":"1014_CR47","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1016\/j.tcs.2005.09.023","volume":"348","author":"Ryan Williams","year":"2005","unstructured":"Williams, Ryan: A new algorithm for optimal 2-constraint satisfaction and its implications. Theor. Comput. Sci. 348(2\u20133), 357\u2013365 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"1014_CR48","doi-asserted-by":"crossref","unstructured":"Williams, R.: Faster decision of first-order graph properties. In: Proceedings of the Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM\/IEEE Symposium on Logic in Computer Science (LICS), pp.\u00a080. ACM (2014)","DOI":"10.1145\/2603088.2603121"},{"key":"1014_CR49","doi-asserted-by":"crossref","unstructured":"Williams, V.V., Williams, R.: Subcubic equivalences between path, matrix and triangle problems. In: Foundations of Computer Science (FOCS), 2010 51st Annual IEEE Symposium on, pp. 645\u2013654. IEEE (2010)","DOI":"10.1109\/FOCS.2010.67"},{"issue":"3","key":"1014_CR50","doi-asserted-by":"publisher","first-page":"831","DOI":"10.1137\/09076619X","volume":"42","author":"VV Williams","year":"2013","unstructured":"Williams, V.V., Williams, R.: Finding, minimizing, and counting weighted subgraphs. SIAM J. Comput. 42(3), 831\u2013854 (2013)","journal-title":"SIAM J. Comput."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01014-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-01014-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01014-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,2]],"date-time":"2024-10-02T07:20:21Z","timestamp":1727853621000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-01014-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8,22]]},"references-count":50,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2022,11]]}},"alternative-id":["1014"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-01014-x","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2022,8,22]]},"assertion":[{"value":"15 December 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 July 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 August 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors are not aware of any conflict of interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}