{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,22]],"date-time":"2026-06-22T06:11:04Z","timestamp":1782108664017,"version":"3.54.5"},"reference-count":47,"publisher":"Springer Science and Business Media LLC","issue":"10","license":[{"start":{"date-parts":[[2018,7,23]],"date-time":"2018-07-23T00:00:00Z","timestamp":1532304000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100004569","name":"Ministerstwo Nauki i Szkolnictwa Wy\u017cszego","doi-asserted-by":"publisher","award":["DI2012 018942"],"award-info":[{"award-number":["DI2012 018942"]}],"id":[{"id":"10.13039\/501100004569","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004281","name":"Narodowe Centrum Nauki","doi-asserted-by":"publisher","award":["2016\/21\/B\/ST6\/02165"],"award-info":[{"award-number":["2016\/21\/B\/ST6\/02165"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2019,10]]},"DOI":"10.1007\/s00453-018-0485-7","type":"journal-article","created":{"date-parts":[[2018,7,23]],"date-time":"2018-07-23T09:33:00Z","timestamp":1532338380000},"page":"3968-3992","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Tight Conditional Lower Bounds for Longest Common Increasing Subsequence"],"prefix":"10.1007","volume":"81","author":[{"given":"Lech","family":"Duraj","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Marvin","family":"K\u00fcnnemann","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4925-774X","authenticated-orcid":false,"given":"Adam","family":"Polak","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2018,7,23]]},"reference":[{"key":"485_CR1","doi-asserted-by":"crossref","unstructured":"Abboud, A., Backurs, A., Vassilevska\u00a0Williams, V.: Quadratic-time hardness of LCS and other sequence similarity measures. In: Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201915), pp. 59\u201378 (2015)","DOI":"10.1109\/FOCS.2015.14"},{"key":"485_CR2","doi-asserted-by":"crossref","unstructured":"Abboud, A., Hansen, T.D., Vassilevska\u00a0Williams, V., Williams, R.: Simulating branching programs with edit distance and friends or: a polylog shaved is a lower bound made. In: Proceedings of 48th Annual ACM Symposium on Symposium on Theory of Computing (STOC\u201916), pp. 375\u2013388 (2016)","DOI":"10.1145\/2897518.2897653"},{"key":"485_CR3","doi-asserted-by":"crossref","unstructured":"Abboud, A., Williams, V.V., Weimann, O.: Consequences of faster alignment of sequences. In: Proceedings of 41st International Colloquium on Automata, Languages, and Programming (ICALP\u201914), pp. 39\u201351 (2014)","DOI":"10.1007\/978-3-662-43948-7_4"},{"issue":"1","key":"485_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/321921.321922","volume":"23","author":"AV Aho","year":"1976","unstructured":"Aho, A.V., Hirschberg, D.S., Ullman, J.D.: Bounds on the complexity of the longest common subsequence problem. J. ACM 23(1), 1\u201312 (1976)","journal-title":"J. ACM"},{"issue":"3","key":"485_CR5","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1016\/S0022-2836(05)80360-2","volume":"215","author":"SF Altschul","year":"1990","unstructured":"Altschul, S.F., Gish, W., Miller, W., Myers, E.W., Lipman, D.J.: Basic local alignment search tool. J. Mol. Biol. 215(3), 403\u2013410 (1990)","journal-title":"J. Mol. Biol."},{"issue":"4","key":"485_CR6","doi-asserted-by":"publisher","first-page":"800","DOI":"10.1007\/s10878-012-9588-2","volume":"28","author":"H Ann","year":"2014","unstructured":"Ann, H., Yang, C., Tseng, C.: Efficient polynomial-time algorithms for the constrained LCS problem with strings exclusion. J. Comb. Optim. 28(4), 800\u2013813 (2014)","journal-title":"J. Comb. Optim."},{"issue":"1","key":"485_CR7","first-page":"316","volume":"2","author":"A Apostolico","year":"1987","unstructured":"Apostolico, A., Guerra, C.: The longest common subsequence problem revisited. Algorithmica 2(1), 316\u2013336 (1987)","journal-title":"Algorithmica"},{"issue":"6","key":"485_CR8","doi-asserted-by":"publisher","first-page":"1099","DOI":"10.1142\/S0129054105003674","volume":"16","author":"AN Arslan","year":"2005","unstructured":"Arslan, A.N., Egecioglu, \u00d6.: Algorithms for the constrained longest common subsequence problems. Int. J. Found. Comput. Sci. 16(6), 1099\u20131109 (2005)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"485_CR9","doi-asserted-by":"crossref","unstructured":"Backurs, A., Indyk, P.: Edit distance cannot be computed in strongly subquadratic time (unless SETH is false). In: Proc. 47th Annual ACM Symposium on Theory of Computing (STOC\u201915), pp. 51\u201358 (2015)","DOI":"10.1145\/2746539.2746612"},{"key":"485_CR10","doi-asserted-by":"crossref","unstructured":"Backurs, A., Indyk, P.: Which regular expression patterns are hard to match? In: Proceedings of 57th Annual Symposium on Foundations of Computer Science, (FOCS\u201916), pp. 457\u2013466 (2016)","DOI":"10.1109\/FOCS.2016.56"},{"key":"485_CR11","unstructured":"Backurs, A., Tzamos, C.: Improving viterbi is hard: Better runtimes imply faster clique algorithms. In: Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6\u201311 August 2017, pp. 311\u2013321 (2017)"},{"issue":"1","key":"485_CR12","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1016\/0022-0000(89)90037-8","volume":"38","author":"DA Barrington","year":"1989","unstructured":"Barrington, D.A.: Bounded-width polynomial-size branching programs recognize exactly those languages in NC1. J. Comput. Syst. Sci. 38(1), 150\u2013164 (1989)","journal-title":"J. Comput. Syst. Sci."},{"key":"485_CR13","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/j.tcs.2015.11.026","volume":"638","author":"G Benson","year":"2016","unstructured":"Benson, G., Levy, A., Maimoni, S., Noifeld, D., Shalom, B.R.: Lcsk: a refined similarity measure. Theor. Comput. Sci. 638, 11\u201326 (2016)","journal-title":"Theor. Comput. Sci."},{"key":"485_CR14","doi-asserted-by":"crossref","unstructured":"Bergroth, L., Hakonen, H., Raita, T.: A survey of longest common subsequence algorithms. In: Proc. 7th International Symposium on String Processing and Information Retrieval (SPIRE\u201900), pp. 39\u201348 (2000)","DOI":"10.1109\/SPIRE.2000.878178"},{"key":"485_CR15","doi-asserted-by":"crossref","unstructured":"Bringmann, K.: Why walking the dog takes time: Frechet distance has no strongly subquadratic algorithms unless SETH fails. In: Proc. 55th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201914), pp. 661\u2013670 (2014)","DOI":"10.1109\/FOCS.2014.76"},{"key":"485_CR16","doi-asserted-by":"crossref","unstructured":"Bringmann, K., K\u00fcnnemann, M.: 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\u201915), pp. 79\u201397 (2015)","DOI":"10.1109\/FOCS.2015.15"},{"key":"485_CR17","doi-asserted-by":"crossref","unstructured":"Bringmann, K., K\u00fcnnemann, M.: Multivariate fine-grained complexity of longest common subsequence. In: Proc. 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201918), pp. 1216\u20131235 (2018)","DOI":"10.1137\/1.9781611975031.79"},{"issue":"3","key":"485_CR18","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1007\/s10878-006-9031-7","volume":"13","author":"W Chan","year":"2007","unstructured":"Chan, W., Zhang, Y., Fung, S.P.Y., Ye, D., Zhu, H.: Efficient algorithms for finding a longest common increasing subsequence. J. Comb. Optim. 13(3), 277\u2013288 (2007)","journal-title":"J. Comb. Optim."},{"issue":"3","key":"485_CR19","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1007\/s10878-009-9262-5","volume":"21","author":"YC Chen","year":"2011","unstructured":"Chen, Y.C., Chao, K.M.: On the generalized constrained longest common subsequence problems. J. Comb. Optim. 21(3), 383\u2013392 (2011)","journal-title":"J. Comb. Optim."},{"issue":"4","key":"485_CR20","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1016\/j.ipl.2004.02.008","volume":"90","author":"FYL Chin","year":"2004","unstructured":"Chin, F.Y.L., Santis, A.D., Ferrara, A.L., Ho, N.L., Kim, S.K.: A simple algorithm for the constrained sequence problems. Inf. Process. Lett. 90(4), 175\u2013179 (2004)","journal-title":"Inf. Process. Lett."},{"key":"485_CR21","unstructured":"Chvatal, V., Klarner, D.A., Knuth, D.E.: Selected combinatorial research problems. Tech. Rep. CS-TR-72-292, Stanford University, Department of Computer Science (1972)"},{"issue":"9","key":"485_CR22","doi-asserted-by":"publisher","first-page":"1054","DOI":"10.1016\/j.ic.2010.04.003","volume":"208","author":"M Crochemore","year":"2010","unstructured":"Crochemore, M., Porat, E.: Fast computation of a longest increasing subsequence and application. Inf. Comput. 208(9), 1054\u20131059 (2010)","journal-title":"Inf. Comput."},{"key":"485_CR23","unstructured":"Cygan, M., Mucha, M., Wegrzycki, K., Wlodarczyk, M.: On problems equivalent to (min,+)-convolution. In: Proceedings of 44th International Colloquium on Automata, Languages, and Programming (ICALP\u201917), pp. 22:1\u201322:15 (2017)"},{"issue":"3","key":"485_CR24","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1016\/j.ipl.2012.11.007","volume":"113","author":"L Duraj","year":"2013","unstructured":"Duraj, L.: A linear algorithm for 3-letter longest common weakly increasing subsequence. Inf. Process. Lett. 113(3), 94\u201399 (2013)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"485_CR25","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/0012-365X(75)90103-X","volume":"11","author":"ML Fredman","year":"1975","unstructured":"Fredman, M.L.: On computing the length of longest increasing subsequences. Discret. Math. 11(1), 29\u201335 (1975)","journal-title":"Discret. Math."},{"key":"485_CR26","doi-asserted-by":"crossref","unstructured":"Gotthilf, Z., Hermelin, D., Landau, G.M., Lewenstein, M.: Restricted LCS. In: Proceedings of 17th International Symposium on String Processing and Information Retrieval (SPIRE\u201910), pp. 250\u2013257 (2010)","DOI":"10.1007\/978-3-642-16321-0_26"},{"issue":"4","key":"485_CR27","doi-asserted-by":"publisher","first-page":"664","DOI":"10.1145\/322033.322044","volume":"24","author":"DS Hirschberg","year":"1977","unstructured":"Hirschberg, D.S.: Algorithms for the longest common subsequence problem. J. ACM 24(4), 664\u2013675 (1977)","journal-title":"J. ACM"},{"key":"485_CR28","unstructured":"Hunt, J.W., McIlroy, M.D.: An algorithm for differential file comparison. Computing Science Technical Report\u00a041, Bell Laboratories (1975)"},{"issue":"5","key":"485_CR29","doi-asserted-by":"publisher","first-page":"350","DOI":"10.1145\/359581.359603","volume":"20","author":"JW Hunt","year":"1977","unstructured":"Hunt, J.W., Szymanski, T.G.: A fast algorithm for computing longest subsequences. Commun. ACM 20(5), 350\u2013353 (1977)","journal-title":"Commun. ACM"},{"issue":"2","key":"485_CR30","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1006\/jcss.2000.1727","volume":"62","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R.: On the complexity of k-SAT. J. Comput. Syst. Sci. 62(2), 367\u2013375 (2001)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"485_CR31","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63(4), 512\u2013530 (2001)","journal-title":"J. Comput. Syst. Sci."},{"key":"485_CR32","unstructured":"Jacobson, G., Vo, K.: Heaviest increasing\/common subsequence problems. In: Proceedings of 3rd Annual Symposium Combinatorial Pattern Matching, CPM 92, Tucson, Arizona, USA, April 29\u2013May 1, 1992, pp. 52\u201366 (1992)"},{"issue":"2","key":"485_CR33","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1016\/S1570-8667(03)00080-7","volume":"2","author":"T Jiang","year":"2004","unstructured":"Jiang, T., Lin, G., Ma, B., Zhang, K.: The longest common subsequence problem for arc-annotated sequences. J. Discret. Algorithms 2(2), 257\u2013270 (2004)","journal-title":"J. Discret. Algorithms"},{"key":"485_CR34","unstructured":"K\u00fcnnemann, M., Paturi, R., Schneider, S.: On the Fine-grained Complexity of One-Dimensional Dynamic Programming. In: Proc. 44th International Colloquium on Automata, Languages, and Programming (ICALP\u201917), pp. 21:1\u201321:15 (2017)"},{"issue":"4","key":"485_CR35","doi-asserted-by":"publisher","first-page":"314","DOI":"10.1016\/j.jda.2011.03.013","volume":"9","author":"M Kutz","year":"2011","unstructured":"Kutz, M., Brodal, G.S., Kaligosi, K., Katriel, I.: Faster algorithms for computing longest common increasing subsequences. J. Discret. Algorithms 9(4), 314\u2013325 (2011)","journal-title":"J. Discret. Algorithms"},{"issue":"1","key":"485_CR36","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1016\/0022-0000(80)90002-1","volume":"20","author":"WJ Masek","year":"1980","unstructured":"Masek, W.J., Paterson, M.: A faster algorithm computing string edit distances. J. Comput. Syst. Sci. 20(1), 18\u201331 (1980)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"485_CR37","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1145\/362007.362033","volume":"13","author":"HL Morgan","year":"1970","unstructured":"Morgan, H.L.: Spelling correction in systems programs. Commun. ACM 13(2), 90\u201394 (1970)","journal-title":"Commun. ACM"},{"issue":"2","key":"485_CR38","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1007\/BF01840446","volume":"1","author":"EW Myers","year":"1986","unstructured":"Myers, E.W.: An $$O(ND)$$ O ( N D ) difference algorithm and its variations. Algorithmica 1(2), 251\u2013266 (1986)","journal-title":"Algorithmica"},{"issue":"3","key":"485_CR39","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1016\/0022-2836(70)90057-4","volume":"48","author":"SB Needleman","year":"1970","unstructured":"Needleman, S.B., Wunsch, C.D.: A general method applicable to the search for similarities in the amino acid sequence of two proteins. J. Mol. Biol. 48(3), 443\u2013453 (1970)","journal-title":"J. Mol. Biol."},{"key":"485_CR40","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ipl.2017.11.007","volume":"132","author":"A Polak","year":"2018","unstructured":"Polak, A.: Why is it hard to beat $${O}(n^2)$$ O ( n 2 ) for longest common weakly increasing subsequence? Inf. Process. Lett. 132, 1\u20135 (2018)","journal-title":"Inf. Process. Lett."},{"key":"485_CR41","doi-asserted-by":"crossref","unstructured":"Roditty, L., Vassilevska\u00a0Williams, V.: Fast approximation algorithms for the diameter and radius of sparse graphs. In: Proceedings of the 45th Annual ACM Symposium on Symposium on Theory of Computing (STOC\u201913), pp. 515\u2013524 (2013)","DOI":"10.1145\/2488608.2488673"},{"issue":"4","key":"485_CR42","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1016\/j.ipl.2003.07.001","volume":"88","author":"Y Tsai","year":"2003","unstructured":"Tsai, Y.: The constrained longest common subsequence problem. Inf. Process. Lett. 88(4), 173\u2013176 (2003)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"485_CR43","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1145\/321796.321811","volume":"21","author":"RA Wagner","year":"1974","unstructured":"Wagner, R.A., Fischer, M.J.: The string-to-string correction problem. J. ACM 21(1), 168\u2013173 (1974)","journal-title":"J. ACM"},{"issue":"2","key":"485_CR44","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1016\/j.tcs.2005.09.023","volume":"348","author":"R Williams","year":"2005","unstructured":"Williams, R.: A new algorithm for optimal 2-constraint satisfaction and its implications. Theor. Comput. Sci. 348(2), 357\u2013365 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"485_CR45","unstructured":"Williams, V.V.: Hardness of easy problems: Basing hardness on popular conjectures such as the strong exponential time hypothesis (invited talk). In: Proceedings of 10th International Symposium on Parameterized and Exact Computation (IPEC\u201915), pp. 17\u201329 (2015)"},{"issue":"5","key":"485_CR46","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1016\/j.ipl.2004.10.014","volume":"93","author":"I Yang","year":"2005","unstructured":"Yang, I., Huang, C., Chao, K.: A fast algorithm for computing a longest common increasing subsequence. Inf. Process. Lett. 93(5), 249\u2013253 (2005)","journal-title":"Inf. Process. Lett."},{"key":"485_CR47","unstructured":"Zhu, D., Wang, X.: A space efficient algorithm for lcis problem. In: Proceedings of 10th International Conference Security, Privacy, and Anonymity in Computation, Communication, and Storage: SpaCCS 2017, Guangzhou, China, December 12\u201315, 2017, pp. 70\u201377 (2017)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0485-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-018-0485-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0485-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,5]],"date-time":"2025-07-05T23:25:58Z","timestamp":1751757958000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-018-0485-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,7,23]]},"references-count":47,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2019,10]]}},"alternative-id":["485"],"URL":"https:\/\/doi.org\/10.1007\/s00453-018-0485-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,7,23]]},"assertion":[{"value":"28 December 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 July 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 July 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}