{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,19]],"date-time":"2026-02-19T07:20:56Z","timestamp":1771485656904,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":53,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783662439470","type":"print"},{"value":"9783662439487","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-43948-7_4","type":"book-chapter","created":{"date-parts":[[2014,6,11]],"date-time":"2014-06-11T16:10:36Z","timestamp":1402503036000},"page":"39-51","source":"Crossref","is-referenced-by-count":45,"title":["Consequences of Faster Alignment of Sequences"],"prefix":"10.1007","author":[{"given":"Amir","family":"Abboud","sequence":"first","affiliation":[]},{"given":"Virginia Vassilevska","family":"Williams","sequence":"additional","affiliation":[]},{"given":"Oren","family":"Weimann","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"4_CR1","unstructured":"Abboud, A., Lewi, K., Williams, R.: On the parameterized complexity of k-sum. CoRR, abs\/1311.3054 (2013)"},{"key":"4_CR2","doi-asserted-by":"crossref","unstructured":"Abboud, A., Vassilevska Williams, V.: Popular conjectures imply strong lower bounds for dynamic problems. arXiv, arXiv:1402.0054 (2014)","DOI":"10.1109\/FOCS.2014.53"},{"issue":"3","key":"4_CR3","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1016\/S0022-2836(05)80360-2","volume":"215","author":"S.F. Altschul","year":"1990","unstructured":"Altschul, S.F., Gish, W., Miller, W., Myers, E.W., Lipman, D.J.: Basic local alignment search tool. Journal of Molecular Biology\u00a0215(3), 403\u2013410 (1990)","journal-title":"Journal of Molecular Biology"},{"issue":"4","key":"4_CR4","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1093\/bioinformatics\/17.4.327","volume":"17","author":"A.N. Arslan","year":"2001","unstructured":"Arslan, A.N., E\u011fecio\u011flu, \u00d6., Pevzner, P.A.: A new approach to sequence comparison: Normalized sequence alignment. Bioinformatics\u00a017(4), 327\u2013337 (2001)","journal-title":"Bioinformatics"},{"issue":"2","key":"4_CR5","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/0022-2836(86)90252-4","volume":"191","author":"J. David","year":"1986","unstructured":"David, J.: Bacon and Wayne\u00a0F. Anderson. Multiple sequence alignment. Journal of Molecular Biology\u00a0191(2), 153\u2013161 (1986)","journal-title":"Journal of Molecular Biology"},{"key":"#cr-split#-4_CR6.1","doi-asserted-by":"crossref","unstructured":"Baran, I., Demaine, E.D., P\u01cetra\u015fcu, M.: Subquadratic algorithms for 3SUM. Algorithmica 50(4), 584-596 (2008)","DOI":"10.1007\/s00453-007-9036-3"},{"key":"#cr-split#-4_CR6.2","unstructured":"In: Dehne, F., L\u00f3pez-Ortiz, A., Sack, J.-R. (eds.) WADS 2005. LNCS, vol.\u00a03608, pp. 409-421. Springer, Heidelberg (2005)"},{"key":"4_CR7","unstructured":"Barequet, G., Har-Peled, S.: Some variants of polygonal containment and minimum hausdorff distance undertranslation are 3SUM-hard. In: SODA, pp. 862\u2013863 (1999)"},{"issue":"3","key":"4_CR8","doi-asserted-by":"publisher","first-page":"486","DOI":"10.1016\/j.tcs.2008.08.042","volume":"409","author":"P. Bille","year":"2008","unstructured":"Bille, P., Farach-Colton, M.: Fast and compact regular expression matching. Theoretical Computer Science\u00a0409(3), 486\u2013496 (2008)","journal-title":"Theoretical Computer Science"},{"key":"4_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1007\/978-3-642-31155-0_25","volume-title":"Algorithm Theory \u2013 SWAT 2012","author":"P. Bille","year":"2012","unstructured":"Bille, P., G\u00f8rtz, I.L., Vildh\u00f8j, H.W., Vind, S.: String indexing for patterns with wildcards. In: Fomin, F.V., Kaski, P. (eds.) SWAT 2012. LNCS, vol.\u00a07357, pp. 283\u2013294. Springer, Heidelberg (2012)"},{"issue":"1","key":"4_CR10","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/0304-3975(94)00251-D","volume":"147","author":"H.L. Bodlaender","year":"1995","unstructured":"Bodlaender, H.L., Downey, R.G., Fellows, M.R., Wareham, H.T.: The parameterized complexity of sequence alignment and consensus. Theoretical Computer Science\u00a0147(1), 31\u201354 (1995)","journal-title":"Theoretical Computer Science"},{"key":"4_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/978-3-642-11269-0_6","volume-title":"Parameterized and Exact Computation","author":"C. Calabro","year":"2009","unstructured":"Calabro, C., Impagliazzo, R., Paturi, R.: The complexity of satisfiability of small depth circuits. In: Chen, J., Fomin, F.V. (eds.) IWPEC 2009. LNCS, vol.\u00a05917, pp. 75\u201385. Springer, Heidelberg (2009)"},{"key":"4_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1007\/978-3-642-02441-2_15","volume-title":"Combinatorial Pattern Matching","author":"K.-Y. Chen","year":"2009","unstructured":"Chen, K.-Y., Hsu, P.-H., Chao, K.-M.: Approximate matching for run-length encoded strings is 3sum-hard. In: Kucherov, G., Ukkonen, E. (eds.) CPM 2009 Lille. LNCS, vol.\u00a05577, pp. 168\u2013179. Springer, Heidelberg (2009)"},{"key":"4_CR13","unstructured":"Cheong, O., Efrat, A., Har-Peled, S.: On finding a guard that sees most and a shop that sells most. In: SODA, pp. 1098\u20131107 (2004)"},{"key":"4_CR14","doi-asserted-by":"crossref","unstructured":"Cole, R., Gottlieb, L.-A., Lewenstein, M.: Dictionary matching and indexing with errors and don\u2019t cares. In: STOC, pp. 91\u2013100 (2004)","DOI":"10.1145\/1007352.1007374"},{"key":"4_CR15","doi-asserted-by":"publisher","first-page":"1654","DOI":"10.1137\/S0097539702402007","volume":"32","author":"M. Crochemore","year":"2003","unstructured":"Crochemore, M., Landau, G.M., Ziv-Ukelson, M.: A subquadratic sequence alignment algorithm for unrestricted scoring matrices. SIAM Journal on Computing\u00a032, 1654\u20131673 (2003)","journal-title":"SIAM Journal on Computing"},{"key":"4_CR16","doi-asserted-by":"crossref","unstructured":"Cygan, M., Dell, H., Lokshtanov, D., Marx, D., Nederlof, J., Okamoto, Y., Paturi, R., Saurabh, S., Wahlstrom, M.: On problems as hard as CNFSAT. In: CCC, pp. 74\u201384 (2012)","DOI":"10.1109\/CCC.2012.36"},{"key":"4_CR17","doi-asserted-by":"crossref","unstructured":"Cygan, M., Kratsch, S., Nederlof, J.: Fast Hamiltonicity checking via bases of perfect matchings. In: STOC, pp. 301\u2013310 (2013)","DOI":"10.1145\/2488608.2488646"},{"key":"4_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1007\/978-3-642-14186-7_27","volume-title":"Theory and Applications of Satisfiability Testing \u2013 SAT 2010","author":"E. Dantsin","year":"2010","unstructured":"Dantsin, E., Wolpert, A.: On moderately exponential time for SAT. In: Strichman, O., Szeider, S. (eds.) SAT 2010. LNCS, vol.\u00a06175, pp. 313\u2013325. Springer, Heidelberg (2010)"},{"issue":"81","key":"4_CR19","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/0925-7721(95)00045-3","volume":"7","author":"M. Berg de","year":"1997","unstructured":"de Berg, M., de Groot, M., Overmars, M.H.: Perfect binary space partitions. Computational Geometry: Theory and Applications\u00a07(81), 81\u201391 (1997)","journal-title":"Computational Geometry: Theory and Applications"},{"key":"4_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"569","DOI":"10.1007\/3-540-60922-9_46","volume-title":"STACS 96","author":"M. Dietzfelbinger","year":"1996","unstructured":"Dietzfelbinger, M.: Universal hashing and k-wise independent random variables via integer arithmetic without primes. In: Puech, C., Reischuk, R. (eds.) STACS 1996. LNCS, vol.\u00a01046, pp. 569\u2013580. Springer, Heidelberg (1996)"},{"key":"4_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1007\/978-3-540-27801-6_25","volume-title":"Combinatorial Pattern Matching","author":"N. Efraty","year":"2004","unstructured":"Efraty, N., Landau, G.M.: Sparse normalized local alignment. In: Sahinalp, S.C., Muthukrishnan, S.M., Dogrusoz, U. (eds.) CPM 2004. LNCS, vol.\u00a03109, pp. 333\u2013346. Springer, Heidelberg (2004)"},{"issue":"4","key":"4_CR22","doi-asserted-by":"publisher","first-page":"1198","DOI":"10.1137\/S0097539797315410","volume":"28","author":"J. Erickson","year":"1999","unstructured":"Erickson, J.: New lower bounds for convex hull problems in odd dimensions. SIAM Journal on Computing\u00a028(4), 1198\u20131214 (1999)","journal-title":"SIAM Journal on Computing"},{"key":"4_CR23","unstructured":"Erickson, J.: Bounds for linear satisfiability problems. Chicago J. Theor. Comput. Sci. (1999)"},{"key":"4_CR24","first-page":"113","volume":"7","author":"M.J. Fischer","year":"1973","unstructured":"Fischer, M.J., Paterson, M.S.: String matching and other products. SIAM-AMS Proc.\u00a07, 113\u2013125 (1973)","journal-title":"SIAM-AMS Proc."},{"issue":"3","key":"4_CR25","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.: On a class of o(n 2) problems in computational geometry. Computational Geometry\u00a05(3), 165\u2013185 (1995)","journal-title":"Computational Geometry"},{"key":"4_CR26","doi-asserted-by":"publisher","first-page":"705","DOI":"10.1016\/0022-2836(82)90398-9","volume":"162","author":"O. Gotoh","year":"1982","unstructured":"Gotoh, O.: An improved algorithm for matching biological sequences. J. Mol. Biol.\u00a0162, 705\u2013708 (1982)","journal-title":"J. Mol. Biol."},{"key":"4_CR27","doi-asserted-by":"crossref","unstructured":"Gusfield, D.: Algorithms on strings, trees and sequences: computer science and computational biology. Cambridge University Press (1997)","DOI":"10.1017\/CBO9780511574931"},{"key":"4_CR28","unstructured":"Hirsch, E.A.: Two new upper bounds for SAT. In: SODA, pp. 521\u2013530 (1998)"},{"key":"4_CR29","unstructured":"Huang, X.: Parameterized complexity and polynomial-time approximation schemes. PhD thesis, Citeseer (2004)"},{"issue":"2","key":"4_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.\u00a062(2), 367\u2013375 (2001)","journal-title":"J. Comput. Syst. Sci."},{"key":"4_CR31","doi-asserted-by":"crossref","unstructured":"Indyk, P.: Faster algorithms for string matching problems: Matching the convolution bound. In: FOCS, p. 166 (1998)","DOI":"10.1109\/SFCS.1998.743440"},{"key":"4_CR32","first-page":"9","volume":"20","author":"Z. Jafargholi","year":"2013","unstructured":"Jafargholi, Z., Viola, E.: 3sum, 3xor, triangles. Electronic Colloquium on Computational Complexity (ECCC)\u00a020, 9 (2013)","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"4_CR33","unstructured":"Kalai, A.: Efficient pattern-matching with don\u2019t cares. In: SODA, pp. 655\u2013656 (2002)"},{"issue":"5131","key":"4_CR34","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1126\/science.8211139","volume":"262","author":"C.E. Lawrence","year":"1993","unstructured":"Lawrence, C.E., Altschul, S.F., Boguski, M.S., Liu, J.S., Neuwald, A.F., Wootton, J.C.: Detecting subtle sequence signals: a gibbs sampling strategy for multiple alignment. Science\u00a0262(5131), 208\u2013214 (1993)","journal-title":"Science"},{"key":"4_CR35","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Marx, D., Saurabh, S.: Known algorithms on graphs on bounded treewidth are probably optimal. In: SODA, pp. 777\u2013789 (2011)","DOI":"10.1137\/1.9781611973082.61"},{"key":"4_CR36","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/S0304-3975(96)00268-X","volume":"181","author":"D. Lopresti","year":"1997","unstructured":"Lopresti, D., Tomkins, A.: Block edit models for approximate string matching. Theoretical Computer Science\u00a0181, 159\u2013179 (1997)","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"4_CR37","first-page":"235","volume":"26","author":"J. Erickson","year":"2002","unstructured":"Erickson, J., Soss, M., Overmars, M.H.: Preprocessing chains for fast dihedral rotations is hard or even impossible. Computational Geometry: Theory and Applications\u00a026(3), 235\u2013246 (2002)","journal-title":"Computational Geometry: Theory and Applications"},{"key":"4_CR38","doi-asserted-by":"crossref","unstructured":"Masek, W.J., Paterson, M.S.: A faster algorithm computing string edit distances. Journal of Computer and System Sciences\u00a020 (1980)","DOI":"10.1016\/0022-0000(80)90002-1"},{"issue":"2","key":"4_CR39","first-page":"415","volume":"26","author":"J. Ne\u0161et\u0159il","year":"1985","unstructured":"Ne\u0161et\u0159il, J., Poljak, S.: On the complexity of the subgraph problem. Comment. Math. Univ. Carolin.\u00a026(2), 415\u2013419 (1985)","journal-title":"Comment. Math. Univ. Carolin."},{"key":"4_CR40","doi-asserted-by":"crossref","unstructured":"P\u01cetra\u015fcu, M.: Towards polynomial lower bounds for dynamic problems. In: STOC, pp. 603\u2013610 (2010)","DOI":"10.1145\/1806689.1806772"},{"issue":"3","key":"4_CR41","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1145\/1066100.1066101","volume":"52","author":"R. Paturi","year":"2005","unstructured":"Paturi, R., Pudl\u00e1k, P., Saks, M.E., Zane, F.: An improved exponential-time algorithm for k-SAT. J. ACM\u00a052(3), 337\u2013364 (2005)","journal-title":"J. ACM"},{"issue":"4","key":"4_CR42","doi-asserted-by":"publisher","first-page":"757","DOI":"10.1016\/S0022-0000(03)00078-3","volume":"67","author":"K. Pietrzak","year":"2003","unstructured":"Pietrzak, K.: On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems. Journal of Computer and System Sciences\u00a067(4), 757\u2013771 (2003)","journal-title":"Journal of Computer and System Sciences"},{"key":"4_CR43","doi-asserted-by":"crossref","unstructured":"P\u01cetra\u015fcu, M., Williams, R.: On the possibility of faster SAT algorithms. In: SODA, pp. 1065\u20131075 (2010)","DOI":"10.1137\/1.9781611973075.86"},{"key":"4_CR44","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1007\/11809678_17","volume-title":"Computing and Combinatorics","author":"M.S. Rahman","year":"2006","unstructured":"Rahman, M.S., Iliopoulos, C., Lee, I., Mohamed, M., Smyth, W.F.: Finding patterns with variable length gaps or don\u2019t cares. In: Chen, D.Z., Lee, D.T. (eds.) COCOON 2006. LNCS, vol.\u00a04112, pp. 146\u2013155. Springer, Heidelberg (2006)"},{"key":"4_CR45","doi-asserted-by":"crossref","unstructured":"Roditty, L., Vassilevska Williams, V.: Fast approximation algorithms for the diameter and radius of sparse graphs. In: STOC, pp. 515\u2013524 (2013)","DOI":"10.1145\/2488608.2488673"},{"key":"4_CR46","doi-asserted-by":"crossref","unstructured":"Sch\u00f6ning, U.: A probabilistic algorithm for k-SAT and constraint satisfaction problems. In: FOCS, pp. 410\u2013414 (1999)","DOI":"10.1109\/SFFCS.1999.814612"},{"key":"4_CR47","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/0022-2836(81)90087-5","volume":"147","author":"T.F. Smith","year":"1981","unstructured":"Smith, T.F., Waterman, M.S.: The identification of common molecular subsequences. Journal of Molecular Biology\u00a0147, 195\u2013197 (1981)","journal-title":"Journal of Molecular Biology"},{"key":"4_CR48","doi-asserted-by":"crossref","unstructured":"Vassilevska, V., Williams, R.: Finding, minimizing, and counting weighted subgraphs. In: STOC, pp. 455\u2013464 (2009)","DOI":"10.1145\/1536414.1536477"},{"issue":"4","key":"4_CR49","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1089\/cmb.1994.1.337","volume":"1","author":"L. Wang","year":"1994","unstructured":"Wang, L., Jiang, T.: On the complexity of multiple sequence alignment. Journal of Computational Biology\u00a01(4), 337\u2013348 (1994)","journal-title":"Journal of Computational Biology"},{"key":"4_CR50","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1227","DOI":"10.1007\/978-3-540-27836-8_101","volume-title":"Automata, Languages and Programming","author":"R. Williams","year":"2004","unstructured":"Williams, R.: A new algorithm for optimal constraint satisfaction and its implications. In: D\u00edaz, J., Karhum\u00e4ki, J., Lepist\u00f6, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol.\u00a03142, pp. 1227\u20131237. Springer, Heidelberg (2004)"},{"key":"4_CR51","doi-asserted-by":"crossref","unstructured":"Vassilevska Williams, V., Williams, R.: Subcubic equivalences between path, matrix and triangle problems. In: FOCS, pp. 645\u2013654 (2010)","DOI":"10.1109\/FOCS.2010.67"},{"key":"4_CR52","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1007\/978-3-540-28639-4_25","volume-title":"Parameterized and Exact Computation","author":"G.J. Woeginger","year":"2004","unstructured":"Woeginger, G.J.: Space and time complexity of exact algorithms: Some open problems. In: Downey, R.G., Fellows, M.R., Dehne, F. (eds.) IWPEC 2004. LNCS, vol.\u00a03162, pp. 281\u2013290. Springer, Heidelberg (2004)"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-43948-7_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,3]],"date-time":"2025-05-03T09:31:27Z","timestamp":1746264687000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-43948-7_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662439470","9783662439487"],"references-count":53,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-43948-7_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014]]}}}