Pith. sign in

REVIEW 5 minor 22 references

String matching on three-block labeled graphs is near-linear; four blocks is as hard as Boolean matrix multiplication.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · grok-4.5

2026-07-31 16:00 UTC pith:SQJL3XTP

load-bearing objection Clean fine-grained classification of string matching on block graphs: near-linear at b=3, combinatorial hardness already at b=4, and the usual algebraic/OV picture after that.

arxiv 2607.28159 v1 pith:SQJL3XTP submitted 2026-07-30 cs.DS

String Matching in (Block) Graphs: A Full Classification by Walk Length

Sebastian Angrick , Ben Bals , Pawe{\l} Gawrychowski , Solon P. Pissis , Yuki Yonemoto This is my paper
classification cs.DS MSC 68W3268Q25
keywords string matchinglabeled graphsblock graphsfine-grained complexityBoolean matrix multiplicationSETHarithmetic progressionspangenome graphs
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

When node labels on a directed graph are strings, finding a walk whose concatenated labels contain a pattern is a basic primitive in pangenome analysis. The classical algorithm runs in time proportional to pattern length times number of edges, and that bound is tight for unrestricted walks. This paper asks what happens when the walk is forced to cross only a fixed number of blocks. It gives a near-linear algorithm for three blocks by compressing how prefixes and suffixes of the pattern align to node labels into a logarithmic number of arithmetic progressions, then intersecting those progressions via periodicity. For four or more blocks the same problem is conditionally as hard as multiplying Boolean matrices, while a matrix-multiplication algorithm matches that barrier for constant block counts. Under standard hardness assumptions the classical bound cannot be beaten once the number of blocks grows faster than logarithmic in the number of nodes. The result therefore draws a sharp line: short walks are easy; slightly longer walks inherit the hardness of dense linear algebra.

Core claim

The complexity of string matching in block graphs is essentially settled by the number of blocks b. For b=3 the problem (and the corresponding walk-length-2 string matching problem) admits an Õ(m+|E|+N)-time algorithm. For every b≥4 there is no combinatorial algorithm running in O((m|E|)^{1-ε}+N) time unless the combinatorial Boolean matrix multiplication conjecture fails, while an O(max(|V|,m)^ω+N)-time algorithm based on fast matrix multiplication is conditionally optimal for constant b. Once b=ω(log|V|), no algorithm of any kind can improve the classical O(m|E|+N) bound under the Orthogonal Vectors Hypothesis.

What carries the argument

Arithmetic-progression compression of borders and periods of the pattern: every set of prefixes (or suffixes) of P that match a node label collapses into O(log m) overlap-free APs; synchronized unions and constant-time AP intersections, guided by the periodicity lemma, let the middle block of a 3-block instance be matched without enumerating all occurrences. For b≥4 the same matching step is realized by rectangular Boolean matrix multiplication across consecutive blocks.

Load-bearing premise

The combinatorial hardness claim for four or more blocks stands only if no combinatorial algorithm can detect a triangle in an n-node graph in truly subcubic time.

What would settle it

Exhibit either a combinatorial O(n^{3-ε})-time triangle-detection algorithm, or a combinatorial algorithm that solves 4-block string matching on labeled graphs in O((m|E|)^{1-ε}+N) time for some ε>0; either object refutes the claimed combinatorial threshold.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • Walks of length at most 2 in arbitrary node-labeled graphs can be searched for a pattern in near-linear time.
  • Any practical pangenome matcher that only needs short walks can replace the classical O(m|E|) scan by the three-block AP algorithm.
  • For dense constant-block instances the matrix-multiplication algorithm is optimal up to subpolynomial factors and already beats O(m|E|) when |E| is quadratic.
  • Once the number of blocks exceeds a logarithmic threshold, even algebraic methods cannot improve the classical bound under SETH-derived hypotheses.
  • The same classification transfers, up to subpolynomial factors, to the walk-length parameterization of ordinary string matching in labeled graphs.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The open gap for unique-label instances with exactly four or five blocks is the natural next target: either a specialized algebraic algorithm or a duplicate-free reduction from triangle detection would close the last remaining case.
  • Because the three-block algorithm only needs standard string and AP primitives, it is a candidate for immediate engineering inside existing sequence-to-graph aligners that already limit seed length.
  • The density-sensitive analysis suggests that hybrid implementations—switching between the combinatorial scan and sparse matrix multiplication according to local block density—could be fastest in real pangenome graphs that mix sparse and dense regions.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

0 major / 5 minor

Summary. The paper studies string matching on node-labeled directed graphs, focusing on the parameterized variant b-SMBG in which the graph is partitioned into b blocks and matches must span a walk of length exactly b-1. Building on the classical O(m|E|+N) algorithm of Amir et al. and the SETH-hardness of Equi et al. for unrestricted walk length, the authors give a fine-grained classification by b: (i) a near-linear Õ(m+|E|+N)-time algorithm for b=3 (Theorem 4.8 / Algorithm 2) via arithmetic-progression compression of borders and careful AP intersection that exploits periodicity; (ii) a combinatorial lower bound ruling out O((m|E|)^{1-ε}+N) time for every b≥4 under the Triangle Detection / combinatorial BMM hypothesis (Theorem 6.1); (iii) an O(max(|V|,m)^ω+N)-time algorithm via rectangular matrix multiplication that is conditionally optimal for constant b≥4 (Corollary 5.2 / Theorem 5.1); and (iv) an OVH/SETH lower bound already for b=ω(log|V|) blocks (Theorem 6.6). The same landscape transfers to h-SMLG for subpolynomial h. Open Question 6.5 records the remaining unique-label gap for b=4,5.

Significance. The work essentially settles the complexity of an important primitive for pangenome / variation-graph analysis when parameterized by walk (block) length. The b=3 near-linear algorithm is a genuine technical contribution: it is not a routine extension of the known linear-time b=2 case and rests on a clean combination of classical border/period AP structure, LCP/suffix-tree primitives, and a non-trivial intersection lemma. Matching upper and lower bounds under standard fine-grained hypotheses (combinatorial BMM/TD for constant b≥4, OVH for super-logarithmic b) give a crisp classification that will be cited as the reference landscape. Algorithms are described at a level that makes implementation plausible, which strengthens applied relevance. The unique-label open question is honestly stated and does not undercut the main claims.

minor comments (5)
  1. [Section 4.3, Lemma 4.7] Section 4.3 / Lemma 4.7: the argument that a non-singleton–non-singleton intersection implies a singleton intersection (via extended periodic regions, the shift by |λ(v2)|+1, and Fine–Wilf) is correct but dense. A short schematic or one concrete numeric example would help readers verify the gcd-period transfer after undoing the shift.
  2. [Section 5, proof of Corollary 5.2] Corollary 5.2 proof: the convexity argument that reduces the sum of rectangular multiplications to O(n^ω) is standard but slightly telegraphic (“by convexity, (★)”). Expanding the inequality chain by one line would improve readability without changing the result.
  3. [Section 6.3, Theorem 6.6] Theorem 6.6 / Fenwick construction: the claim that each pattern fragment appears in O(log n) nodes is attributed to “standard results on Fenwick trees.” A one-sentence pointer to the precise property (or a short inductive argument) would make the size analysis self-contained.
  4. [Introduction / Open Question 6.5] Open Question 6.5 is well placed; consider also stating explicitly in the introduction or abstract that the b=4 combinatorial hardness (Theorem 6.1) uses duplicate labels, so that readers interested only in unique-label block graphs know the precise threshold is b=6.
  5. Minor typographical / notation points: “Pississhowed” (p. 3); occasional missing spaces around citations; “eO” vs. “Õ” consistency; Figure 3 caption could name the two occurrence categories (green/blue) more explicitly in the text of Lemma 4.6.

Circularity Check

0 steps flagged

No significant circularity: standard fine-grained algorithms and external hardness reductions

full rationale

The paper's classification of b-SMBG is self-contained algorithmic and reduction work against external benchmarks. The b=3 near-linear algorithm (Thm 4.8, Alg 2) derives from classical stringology (KMP borders as O(log m) APs, Fine–Wilf periodicity, suffix trees/LCP) plus new intersection lemmas (4.3–4.7); none of these define the target match set in terms of a fitted parameter or rename the output as an input. The algebraic upper bound (Cor 5.2 / Thm 5.1) is ordinary block-wise Boolean/rectangular matrix multiplication. Hardness for b≥4 (Thm 6.1) is an explicit size-preserving reduction from Triangle Detection / combinatorial BMM; hardness for b=ω(log|V|) (Thm 6.6) is an explicit OV reduction via Fenwick alignment gadgets. Both hypotheses are long-standing external assumptions stated in Sec 6.1, not self-justified. Citations to Pissis (b=2), Amir et al. (O(m|E|+N)), and Equi et al. (prior SETH bounds) are used as black-box priors and do not close a definitional loop. Open Question 6.5 on unique labels for b=4,5 is acknowledged rather than papered over. No self-definitional step, fitted-as-prediction step, or load-bearing self-citation uniqueness claim appears.

Axiom & Free-Parameter Ledger

0 free parameters · 6 axioms · 0 invented entities

Pure fine-grained algorithms paper. Central claims rest on standard word-RAM and stringology primitives plus two external hardness hypotheses (combinatorial BMM/TD and OVH/SETH). No fitted parameters and no newly postulated physical or combinatorial entities.

axioms (6)
  • standard math Word RAM with Ω(log n)-bit words; arithmetic and indirect addressing in O(1)
    Stated in Computational Model paragraph; used for all running-time claims.
  • standard math Periodicity lemma (Fine–Wilf) and O(log m) AP representation of borders/periods of a string
    Lemmas 2.2, 4.1; classical KMP/Guibas–Odlyzko facts underlying the b=3 algorithm.
  • standard math Suffix tree + LCP in O(m log m) preprocess, O(1) LCP; linear-time exact string matching
    Lemmas 2.3–2.5; black-box primitives for occurrence and border computation.
  • domain assumption Combinatorial Triangle Detection / BMM hypothesis: no combinatorial O(n^{3-ε}) triangle algorithm
    Sec 6.1; load-bearing for Thm 6.1 and Cor 6.2 (combinatorial hardness at b≥4).
  • domain assumption Orthogonal Vectors Hypothesis (implied by SETH): no O(n^{2-ε}) OV for d=ω(log n)
    Sec 6.1; load-bearing for Thm 6.6 (hardness for b=ω(log|V|)).
  • standard math Matrix-multiplication exponent ω and rectangular exponents ω(a,b,c) as currently known
    Thm 5.1 / Cor 5.2; algebraic upper bound expressed in ω.

pith-pipeline@v1.2.0-daily-grok45 · 32850 in / 2909 out tokens · 58997 ms · 2026-07-31T16:00:10.922999+00:00 · methodology

0 comments
read the original abstract

We consider directed graphs in which the nodes are labeled with strings. A walk in such a graph naturally corresponds to the concatenation of the visited nodes' labels. These graphs are widely used in bioinformatics to compactly describe large collections of highly similar genomes. Given such a graph $G=(V,E)$ and a pattern of length $m$, we seek a walk whose corresponding string has an occurrence of the pattern. We call this the SMLG problem. Amir et al. [J. Algorithms, 2000] showed that SMLG can be solved in $\mathcal{O}(m|E| + N)$ time, where $N$ is the total length of all node labels. Equi et al. [ACM Trans. Algorithms, 2023] showed that this is essentially optimal (under SETH). The existing lower bound assumes that the sought walk is of length $\Theta(|V|)$. Thus, we might be able to bypass this lower bound by restricting the walk length to $b-1$, which naturally reduces to having as input a directed graph whose set of nodes is partitioned into $b$ blocks. Then, we seek a walk in this graph that starts in the first block and ends in the last block. We call this the $b$-SMBG problem. We provide a more fine-grained classification that essentially settles the complexity of $b$-SMBG parameterized by $b$: (1) We give a near-linear-time algorithm for $b=3$. (2) We show that there is no combinatorial algorithm improving over the state-of-the-art $\mathcal{O}(m|E| + N)$ bound for any $b\ge 4$. (3) We also present a fast matrix multiplication-based algorithm yielding an improvement for $b \in \mathcal{O}(1)$, which is conditionally optimal. (4) Finally, we show that under SETH, for any $b \in \omega(\log |V|)$, no algorithm can improve over the state of the art.

Figures

Figures reproduced from arXiv: 2607.28159 by Ben Bals, Pawe{\l} Gawrychowski, Sebastian Angrick, Solon P. Pissis, Yuki Yonemoto.

Figure 1
Figure 1. Figure 1: The DNA sequences on the left are represented by the node-labeled graph on the right. The [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: A block graph with an occurrence of 𝑃 = 𝑃[1 . . 8] = ATCGTAGA (in orange). String Matching in Block Graphs (SMBG) Input: A block graph 𝐺 = (𝑉, 𝐸, 𝜆) with 𝑏 blocks and a pattern 𝑃 = 𝑃[1 . . 𝑚]. Output: True if and only if there is at least one occurrence of 𝑃 in 𝐺. When ℎ is bounded, we can efficiently reduce ℎ-SMLG on 𝐺 = (𝑉, 𝐸, 𝜆) to string matching in a block graph 𝐺 ′ = (𝑉 ′ , 𝐸′ , 𝜆′ ) with 𝑏 := ℎ bloc… view at source ↗
Figure 3
Figure 3. Figure 3: Illustration of Lemma 4.6. Orange lines depict an AP of prefixes of 𝑃. As purple, further repetitions of the period string. Below, all possible occurrences of a string 𝜆(𝑣 2 ) directly after an AP element. These fall into the two categories used in the proof: entirely within the periodic region (green), and partially or entirely after (blue). For green, we only need to check a single starting position (ind… view at source ↗
Figure 4
Figure 4. Figure 4: Left, an undirected graph with 𝑛 = 4. Right, the corresponding construction of the block graph from the proof of Theorem 6.1. One block match for the triangle 123 is indicated in red. Intuitively, we find triangles like this as all paths through the graph that start and end at copies of the same node will have 1 0𝑛+2 1 as their concatenation of labels. We have a match in 𝐺𝐵 if there are four nodes (𝑣 1 𝑖1 … view at source ↗
Figure 5
Figure 5. Figure 5: The coordinate, element, and set gadget on an example set [PITH_FULL_IMAGE:figures/full_fig_p019_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: The construction of the prefix alignment gadget. Left, the subdivision of the pattern into ranges, [PITH_FULL_IMAGE:figures/full_fig_p019_6.png] view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

22 extracted references · 7 canonical work pages

  1. [7]

    21 [Bra] Jan van den Brand

    URL:https://doi.org/10.1137/20m1368033, doi: 10.1137/20M1368033. 21 [Bra] Jan van den Brand. Complexity term balancer.jvdbrand.com/complexity/. Tool to balance complexity terms depending on fast matrix multiplication. [CF06] Deepayan Chakrabarti and Christos Faloutsos. Graph mining: Laws, generators, and algorithms.ACM Comput. Surv., 38(1):2, 2006.doi:10....

    arXiv 2006

  2. [8]

    [CP91] MaximeCrochemoreandDominiquePerrin

    URL:https://mitpress.mit.edu/ 9780262046305/introduction-to-algorithms/. [CP91] MaximeCrochemoreandDominiquePerrin. Two-waystringmatching.J.ACM,38(3):651– 675, 1991.doi:10.1145/116825.116845. [EMTG23] Massimo Equi, Veli Mäkinen, Alexandru I. Tomescu, and Roberto Grossi. On the complexity of string matching for graphs.ACM Trans. Algorithms, 19(3):21:1–21:25,

    arXiv 1991

  3. [10]

    [Fen94] PeterM.Fenwick

    URL: https://doi.org/10.1007/s00453-022-01007-w, doi:10.1007/S00453-022-01007-W. [Fen94] PeterM.Fenwick. Anewdatastructureforcumulativefrequencytables.Software: Practice and Experience, 24(3):327–336, 1994.doi:10.1002/spe.4380240306. [FW65] Nathan J. Fine and Herbert S. Wilf. Uniqueness theorems for periodic functions. Proceedings of the American Mathemat...

    doi:10.1007/s00453-022-01007-w 1994

  4. [15]

    [KRRW24] Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, and Tomasz Walen

    URL: https://doi.org/10.1016/j.jcss.2016.09.003, doi: 10.1016/J.JCSS.2016.09.003. [KRRW24] Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, and Tomasz Walen. Internal pattern matching queries in a text and applications.SIAM J. Comput., 53(5):1524–1577,

    work page doi:10.1016/j.jcss.2016.09.003 2016

  5. [18]

    [RM20] Mikko Rautiainen and Tobias Marschall

    doi: 10.1137/1.9781611978315.13. [RM20] Mikko Rautiainen and Tobias Marschall. Graphaligner: rapid and versatile sequence-to-graph alignment.Genome Biology, 21(1):253,

    work page doi:10.1137/1.9781611978315.13

  6. [22]

    URL: https://doi.org/10.1017/s0956796824000169, doi:10.1017/ S0956796824000169. 24

    work page doi:10.1017/s0956796824000169

  7. [134]

    Linearpatternmatchingalgorithms

    [Wei73] PeterWeiner. Linearpatternmatchingalgorithms. In14thAnnualSymposiumonSwitching and Automata Theory, Iowa City, Iowa, USA, October 15-17, 1973, pages 1–11. IEEE Computer Society, 1973.doi:10.1109/SWAT.1973.13. [Wil05] Ryan Williams. A new algorithm for optimal 2-constraint satisfaction and its implications. Theor. Comput. Sci., 348(2-3):357–365, 20...

    doi:10.1109/swat.1973.13 1973

  8. [1965]

    [Gaw13] Pawel Gawrychowski

    doi: 10.1090/S0002-9939-1965-0174934-9. [Gaw13] Pawel Gawrychowski. Optimal pattern matching in LZW compressed strings.ACM Trans. Algorithms, 9(3):25:1–25:17, 2013.doi:10.1145/2483699.2483705. [GFB94] Ming Gu, Martin Farach, and Richard Beigel. An efficient algorithm for dynamic text indexing. In Daniel Dominic Sleator, editor,Proceedings of the Fifth Ann...

    arXiv 1965

  9. [1994]

    URL:http://dl.acm.org/citation.cfm?id=314464. 314675. [GIL+17] Roberto Grossi, Costas S. Iliopoulos, Chang Liu, Nadia Pisanti, Solon P. Pissis, Ahmad Retha, Giovanna Rosone, Fatima Vayani, and Luca Versari. On-line pattern matching on similar texts. In Juha Kärkkäinen, Jakub Radoszewski, and Wojciech Rytter, editors,28th Annual Symposium on Combinatorial ...

    2017

  10. [2000]

    [ANI+18] Kotaro Aoyama, Yuto Nakashima, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda

    URL:https://doi.org/10.1006/jagm.1999.1063, doi:10.1006/JAGM.1999.1063. [ANI+18] Kotaro Aoyama, Yuto Nakashima, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda. Faster online elastic degenerate string matching. In Gonzalo Navarro, David Sankoff, and Binhai Zhu, editors,Annual Symposium on Combinatorial Pattern Matching, CPM 2018, Qingdao, ...

    arXiv 1999

  11. [2011]

    23 [Tha13] ChrisThachuk.Indexinghypertext.J.DiscreteAlgorithms,18:113–122,2013.URL: https: //doi.org/10.1016/j.jda.2012.10.001,doi:10.1016/J.JDA.2012.10.001

    URL:https://doi.org/10.1007/s00453-010-9401-5, doi: 10.1007/S00453-010-9401-5. 23 [Tha13] ChrisThachuk.Indexinghypertext.J.DiscreteAlgorithms,18:113–122,2013.URL: https: //doi.org/10.1016/j.jda.2012.10.001,doi:10.1016/J.JDA.2012.10.001. [VXXZ24] Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, and Renfei Zhou. New bounds for matrix multiplication: fr...

    doi:10.1007/s00453-010-9401-5 2013

  12. [2013]

    1016/j.tcs.2012.11.040,doi:10.1016/J.TCS.2012.11.040

    URL: https://doi.org/10. 1016/j.tcs.2012.11.040,doi:10.1016/J.TCS.2012.11.040. [BGP+22] Giulia Bernardini, Pawel Gawrychowski, Nadia Pisanti, Solon P. Pissis, and Giovanna Rosone. Elastic-degenerate string matching via fast matrix multiplication.SIAM J. Comput., 51(3):549–576,

    doi:10.1016/j.tcs.2012.11.040 2012

  13. [2017]

    [GO81] Leonidas J

    URL:https://doi.org/10.4230/LIPIcs.CPM.2017.9, doi: 10.4230/LIPICS.CPM.2017.9. [GO81] Leonidas J. Guibas and Andrew M. Odlyzko. Periods in strings.J. Comb. Theory A, 30(1):19–42, 1981.doi:10.1016/0097-3165(81)90038-8. [Gus78] Fred G. Gustavson. Two fast algorithms for sparse matrices: Multiplication and permuted transposition.ACM Trans. Math. Softw., 4(3)...

    arXiv 2017

  14. [2018]

    [AV14] Amir Abboud and Virginia Vassilevska Williams

    URL: https: //doi.org/10.4230/LIPIcs.CPM.2018.9,doi:10.4230/LIPICS.CPM.2018.9. [AV14] Amir Abboud and Virginia Vassilevska Williams. Popular conjectures imply strong lower bounds for dynamic problems. In55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages 434–443. IEEE Computer Society...

    doi:10.4230/lipics.cpm.2018.9 2018

  15. [2019]

    [RZ11] Liam Roditty and Uri Zwick

    URL: https://doi.org/10.1093/ bioinformatics/btz162,doi:10.1093/BIOINFORMATICS/BTZ162. [RZ11] Liam Roditty and Uri Zwick. On dynamic shortest paths problems.Algorithmica, 61(2):389–401,

    work page doi:10.1093/bioinformatics/btz162

  16. [2020]

    [Pis25] Solon P

    URL:https: //doi.org/10.4230/LIPIcs.WABI.2020.7,doi:10.4230/LIPICS.WABI.2020.7. [Pis25] Solon P. Pissis. Optimal prefix-suffix queries with applications. In Ioana Oriana Bercea and Rasmus Pagh, editors,2025 Symposium on Simplicity in Algorithms, SOSA 2025, New Orleans, LA, USA, January 13-15, 2025, pages 166–171. SIAM,

    work page doi:10.4230/lipics.wabi.2020.7 2020

  17. [2021]

    1016/j.ic.2020.104616,doi:10.1016/J.IC.2020.104616

    URL:https://doi.org/10. 1016/j.ic.2020.104616,doi:10.1016/J.IC.2020.104616. [IP01] RussellImpagliazzoandRamamohanPaturi. Onthecomplexityofk-SAT.J.Comput.Syst. Sci., 62(2):367–375, 2001.doi:10.1006/JCSS.2000.1727. [IR78] Alon Itai and Michael Rodeh. Finding a minimum circuit in a graph.SIAM J. Comput., 7(4):413–423, 1978.doi:10.1137/0207033. [KAMD+25] Venk...

    arXiv 2020

  18. [2022]

    [BG14] DanyBreslauerandZviGalil.Real-timestreamingstring-matching.ACMTrans.Algorithms, 10(4):22:1–22:12, 2014.doi:10.1145/2635814

    URL:https: //doi.org/10.1007/s11047-022-09882-6,doi:10.1007/S11047-022-09882-6. [BG14] DanyBreslauerandZviGalil.Real-timestreamingstring-matching.ACMTrans.Algorithms, 10(4):22:1–22:12, 2014.doi:10.1145/2635814. [BG25] Itai Boneh and Shay Golan. Covers in optimal space. In Paola Bonizzoni and Veli Mäkinen,editors,36thAnnualSymposiumonCombinatorialPatternMa...

    work page doi:10.1007/s11047-022-09882-6 2014

  19. [2023]

    [ENA+23] Massimo Equi, Tuukka Norri, Jarno Alanko, Bastien Cazaux, Alexandru I

    doi:10.1145/3588334. [ENA+23] Massimo Equi, Tuukka Norri, Jarno Alanko, Bastien Cazaux, Alexandru I. Tomescu, and Veli Mäkinen. Algorithms and complexity on indexing founder graphs.Algorithmica, 85(6):1586–1623,

    work page doi:10.1145/3588334

  20. [2024]

    [LV86] Gad M

    URL:https://doi.org/10.1137/23m1567618,doi:10.1137/23M1567618. [LV86] Gad M. Landau and Uzi Vishkin. Efficient string matching with k mismatches.Theor. Comput. Sci., 43:239–249, 1986.doi:10.1016/0304-3975(86)90178-7. [MCE+20] Veli Mäkinen, Bastien Cazaux, Massimo Equi, Tuukka Norri, and Alexandru I. Tomescu. Linear time construction of indexable founder b...

    doi:10.1137/23m1567618 1986

  21. [2025]

    CPM.2025.5,doi:10.4230/LIPICS.CPM.2025.5

    URL:https://doi.org/10.4230/LIPIcs. CPM.2025.5,doi:10.4230/LIPICS.CPM.2025.5. [BGM13] Dany Breslauer, Roberto Grossi, and Filippo Mignosi. Simple real-time constant-space string matching.Theor. Comput. Sci., 483:2–9,

    doi:10.4230/lipics 2025

  22. [2026]

    1186/s13015-025-00289-3,doi:10.1186/S13015-025-00289-3

    URL: https://doi.org/10. 1186/s13015-025-00289-3,doi:10.1186/S13015-025-00289-3. [ABFK24] AmirAbboud,KarlBringmann,NickFischer,andMarvinKünnemann.Thetimecomplexity offullysparsematrixmultiplication. InDavidP.Woodruff, editor,Proceedingsofthe2024 20 ACM-SIAMSymposiumonDiscreteAlgorithms,SODA2024,Alexandria,VA,USA,January 7-10, 2024, pages 4670–4703. SIAM, ...

    arXiv 2024