{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:41:32Z","timestamp":1787341292127,"version":"build-2736575974"},"reference-count":72,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"DOI":"10.13039\/501100003407","name":"Ministero dell'Istruzione, dell'Universit\u00e0 e della Ricerca","doi-asserted-by":"publisher","award":["RBSI146R5L"],"award-info":[{"award-number":["RBSI146R5L"]}],"id":[{"id":"10.13039\/501100003407","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003246","name":"Nederlandse Organisatie voor Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","award":["OCENW.GROOT.2019.015"],"award-info":[{"award-number":["OCENW.GROOT.2019.015"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2022,6]]},"abstract":"<jats:p>An elastic-degenerate (ED) string is a sequence of $n$ sets of strings of total length $N$ which was recently proposed to model a set of similar sequences. The ED string matching (EDSM) problem is to find all occurrences of a pattern of length $m$ in an ED text. The EDSM problem has recently received some attention in the combinatorial pattern matching community, and an $\\mathcal{O}(nm^{1.5}\\sqrt{\\log m} + N)$-time algorithm is known [Aoyama et al., CPM 2018]. The standard assumption in the prior work on this question is that $N$ is substantially larger than both $n$ and $m$, and thus we would like to have a linear dependency on the former. Under this assumption, the natural open problem is whether we can decrease the 1.5 exponent in the time complexity, similarly as in the related (but, to the best of our knowledge, not equivalent) word break problem [Backurs and Indyk, FOCS 2016]. Our starting point is a conditional lower bound for the EDSM problem. We use the popular combinatorial Boolean matrix multiplication (BMM) conjecture stating that there is no truly subcubic combinatorial algorithm for BMM [Abboud and Williams, FOCS 2014]. By designing an appropriate reduction, we show that a combinatorial algorithm solving the EDSM problem in $\\mathcal{O}(nm^{1.5-\\epsilon} + N)$ time, for any $\\epsilon&gt;0$, refutes this conjecture. Our reduction should be understood as an indication that decreasing the exponent requires fast matrix multiplication. String periodicity and fast Fourier transform are two standard tools in string algorithms. Our main technical contribution is that we successfully combine these tools with fast matrix multiplication to design a noncombinatorial $\\tilde{\\mathcal{O}}(nm^{\\omega-1}+N)$-time algorithm for EDSM, where $\\omega$ denotes the matrix multiplication exponent and the $\\tilde{\\mathcal{O}}(\\cdot)$ notation suppresses polylog factors. To the best of our knowledge, we are the first to combine these tools. In particular, using the fact that $\\omega&lt;2.373$ [Alman and Williams, SODA 2021; Le Gall, ISSAC 2014; Williams, STOC 2012], we obtain an $\\mathcal{O}(nm^{1.373} + N)$-time algorithm for EDSM. An important building block in our solution that might find applications in other problems is a method of selecting a small set of length-$\\ell$ substrings of the pattern, called anchors, so that any occurrence of a string from an ED text set contains at least one but not too many (on average) such anchors inside.<\/jats:p>","DOI":"10.1137\/20m1368033","type":"journal-article","created":{"date-parts":[[2022,5,19]],"date-time":"2022-05-19T15:19:16Z","timestamp":1652973556000},"page":"549-576","source":"Crossref","is-referenced-by-count":10,"title":["Elastic-Degenerate String Matching via Fast Matrix Multiplication"],"prefix":"10.1137","volume":"51","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6647-088X","authenticated-orcid":true,"given":"Giulia","family":"Bernardini","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pawe\u0142","family":"Gawrychowski","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nadia","family":"Pisanti","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Solon P.","family":"Pissis","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Giovanna","family":"Rosone","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2022,5,19]]},"reference":[{"key":"atypb1","first-page":"98","volume-title":"Proceedings of the 56th IEEE Symposium on Foundations Of Computer Science (FOCS)","author":"Abboud A.","year":"2015"},{"key":"atypb2","first-page":"434","volume-title":"Proceedings of the 55th IEEE Symposium on Foundations of Computer Science (FOCS)","author":"Abboud A.","year":"2014"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1137\/0216067"},{"key":"atypb4","doi-asserted-by":"crossref","first-page":"522","DOI":"10.1137\/1.9781611976465.32","volume-title":"Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Alman J.","year":"2021"},{"key":"atypb5","first-page":"1","volume-title":"Proceedings of the 18th Workshop on Algorithms in Bioinformatics (WABI), LIPIcs 113","author":"Alzamel M.","year":"2018"},{"key":"atypb6","first-page":"41","volume":"175","author":"Alzamel M.","year":"2020","journal-title":"Fund. Inform."},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(03)00097-X"},{"key":"atypb8","first-page":"1","volume-title":"Proceedings of the 29th Symposium on Combinatorial Pattern Matching (CPM), LIPIcs 105","author":"Aoyama K.","year":"2018"},{"key":"atypb9","first-page":"1209","volume":"11","author":"Arlazarov V.","year":"1970","journal-title":"Soviet Math. Dokl."},{"key":"atypb10","first-page":"457","volume-title":"Proceedings of the 57th IEEE Symposium on Foundations of Computer Science (FOCS)","author":"Backurs A.","year":"2016"},{"key":"atypb11","first-page":"745","volume-title":"Proceedings of the 50th IEEE Symposium on Foundations of Computer Science (FOCS)","author":"Bansal N.","year":"2009"},{"key":"atypb12","first-page":"88","volume-title":"4th Latin American Symposium on Theoretical Informatics (LATIN), Springer LNCS 1776","author":"Bender M.","year":"2000"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1145\/361002.361007"},{"key":"atypb14","first-page":"1","volume":"132","author":"Bernardini G.","year":"2019","journal-title":"LIPIcs"},{"key":"atypb15","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1007\/978-3-319-67428-5_7","volume-title":"Proceedings of the 24th International Symposium on String Processing and Information Retrieval (SPIRE)","author":"Bernardini G.","year":"2017"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2019.08.012"},{"key":"atypb17","first-page":"375","volume-title":"Proceedings of the 56th IEEE Symposium on Foundations of Computer Science (FOCS)","author":"Bringmann K.","year":"2016"},{"key":"atypb18","first-page":"307","volume-title":"Proceedings of the 58th IEEE Symposium on Foundations of Computer Science (FOCS)","author":"Bringmann K.","year":"2017"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11269-0_6"},{"key":"atypb20","first-page":"212","volume-title":"Proceedings of the 26th ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Chan T.","year":"2015"},{"key":"atypb21","first-page":"1","volume-title":"Proceedings of the 27th Symposium on Combinatorial Pattern Matching (CPM), LIPIcs 54","author":"Chang Y.-J.","year":"2016"},{"key":"atypb22","first-page":"1","volume-title":"Proceedings of the 45th ACM SIGPLAN Symposium on Principles of Programming Languages (POPL)","author":"Chatterjee K.","year":"2018"},{"key":"atypb23","volume-title":"CoRR, abs\/2004.03033","author":"Cislak A.","year":"2020"},{"key":"atypb24","doi-asserted-by":"crossref","first-page":"4290","DOI":"10.1093\/bioinformatics\/bty506","volume":"34","author":"Cis\u0142ak A.","year":"2018","journal-title":"Bioinformatics"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2006.08.002"},{"key":"atypb26","first-page":"592","volume-title":"Proceedings of the 34th ACM Symposium on Theory of Computing (STOC)","author":"Cole R.","year":"2002"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1965-0178586-1"},{"key":"atypb28","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511546853","volume-title":"Algorithms on Strings","author":"Crochemore M.","year":"2007"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1145\/116825.116845"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1137\/070695149"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(83)90017-2"},{"key":"atypb32","first-page":"130","volume-title":"Proceedings of the 7th Annual Symposium on Combinatorial Pattern Matching (CPM), Springer LNCS 1075","author":"Farach-Colton M.","year":"1996"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1965-0174934-9"},{"key":"atypb34","first-page":"129","volume-title":"Proceedings of the 12th IEEE Symposium on Switching and Automata Theory (SWAT\/FOCS)","author":"Fischer M.","year":"1971"},{"key":"atypb35","first-page":"113","volume":"7","author":"Fischer M.","year":"1974","journal-title":"SIAM-AMS Proceedings"},{"key":"atypb36","first-page":"1252","volume":"11","author":"Furman M.","year":"1970","journal-title":"Soviet Math. Dokl."},{"key":"atypb37","first-page":"1","volume-title":"Proceedings of the 31st Symposium on Combinatorial Pattern Matching (CPM), LIPIcs 161","author":"Gawrychowski P.","year":"2020"},{"key":"atypb38","first-page":"1","volume":"107","author":"Gawrychowski P.","year":"2018","journal-title":"LIPIcs"},{"key":"atypb39","first-page":"1","volume-title":"Proceedings of the 28th Symposium on Combinatorial Pattern Matching (CPM), LIPIcs 78","author":"Grossi R.","year":"2017"},{"key":"atypb40","first-page":"21","volume-title":"Proceedings of the 47th ACM Symposium on Theory of Computing (STOC)","author":"Henzinger M.","year":"2015"},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2006.10.003"},{"key":"atypb42","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1007\/978-3-319-53733-7_9","volume-title":"Proceedings of the 11th International Conference on Language and Automata Theory and Applications (LATA), Springer LNCS 10168","author":"Iliopoulos C.","year":"2017"},{"key":"atypb43","first-page":"166","volume-title":"Proceedings of the 39th Symposium on Foundations of Computer Science (FOCS)","author":"Indyk P.","year":"1998"},{"key":"atypb44","first-page":"1","volume-title":"Proceedings of the 9th ACM Symposium on Theory of Computing (STOC)","author":"Itai A.","year":"1977"},{"key":"atypb45","doi-asserted-by":"publisher","DOI":"10.1021\/bi00822a023"},{"key":"atypb46","first-page":"655","volume-title":"Proceedings of the 13th ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Kalai A.","year":"2002"},{"key":"atypb47","doi-asserted-by":"publisher","DOI":"10.1137\/0206024"},{"key":"atypb48","first-page":"532","volume-title":"Proceedings of the 26th ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Kociumaka T.","year":"2015"},{"key":"atypb49","first-page":"1","volume-title":"Proceedings of the 27th Symposium on Combinatorial Pattern Matching (CPM), LIPIcs 54","author":"Kopelowitz T.","year":"2016"},{"key":"atypb50","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.03.026"},{"key":"atypb51","doi-asserted-by":"crossref","first-page":"296","DOI":"10.1145\/2608628.2608664","volume-title":"Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation (ISSAC)","author":"Gall F. Le","year":"2014"},{"key":"atypb52","doi-asserted-by":"publisher","DOI":"10.1145\/505241.505242"},{"key":"atypb53","first-page":"1","volume-title":"Proceedings of the 20th Workshop on Algorithms in Bioinformatics (WABI), LIPIcs 172","author":"M\u00e4kinen V.","year":"2020"},{"key":"atypb54","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(91)90071-O"},{"key":"atypb55","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(71)90006-8"},{"key":"atypb56","doi-asserted-by":"publisher","DOI":"10.1002\/spe.411"},{"key":"atypb57","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2007.03.003"},{"key":"atypb58","first-page":"1","volume-title":"Proceedings of the 32nd Annual Symposium on Combinatorial Pattern Matching (CPM), LIPIcs 191","author":"Pisanti N.","year":"2021"},{"key":"atypb59","first-page":"1","volume-title":"Proceedings of the 17th International Symposium on Experimental Algorithms (SEA), LIPIcs 103","author":"Pissis S.","year":"2018"},{"key":"atypb60","first-page":"580","volume-title":"Proceedings of the 12th European Symposium on Algorithms (ESA), Springer LNCS 3221","author":"Roditty L.","year":"2004"},{"key":"atypb61","first-page":"84","volume":"5125","author":"Ru\u017ei\u0107 M.","year":"2008","journal-title":"Springer LNCS"},{"key":"atypb62","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(83)90006-5"},{"key":"atypb63","first-page":"118","volume":"19","author":"The Computational Pan-Genomics Consortium","year":"2018","journal-title":"Briefings Bioinform."},{"key":"atypb64","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(75)80046-8"},{"key":"atypb65","first-page":"1","volume-title":"Proceedings of the 14th IEEE Annual Symposium on Switching and Automata Theory (SWAT\/FOCS)","author":"Weiner P.","year":"1973"},{"key":"atypb66","first-page":"887","volume-title":"Proceedings of the 44th ACM Symposium on Theory of Computing Conference (STOC)","author":"Williams V.","year":"2012"},{"key":"atypb67","first-page":"225","volume-title":"Proceedings of the 38th ACM Symposium on Theory of Computing Conference (STOC)","author":"Williams V.","year":"2006"},{"key":"atypb68","first-page":"645","volume-title":"Proceedings of the 51st IEEE Symposium on Foundations of Computer Science (FOCS)","author":"Williams V.","year":"2010"},{"key":"atypb69","first-page":"153","volume-title":"USENIX Technical Conference","author":"Wu S.","year":"1992"},{"key":"atypb70","first-page":"1094","volume":"9134","author":"Yu H.","year":"2015","journal-title":"Springer LNCS"},{"key":"atypb71","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2018.02.006"},{"key":"atypb72","doi-asserted-by":"publisher","DOI":"10.1145\/567112.567114"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/20M1368033","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:12:54Z","timestamp":1787339574000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/20M1368033"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,5,19]]},"references-count":72,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,6]]}},"alternative-id":["10.1137\/20M1368033"],"URL":"https:\/\/doi.org\/10.1137\/20m1368033","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,5,19]]}}}