The decades-old Pattern Matching with Edits problem, given a length-n string T (the text), a length-m string P (the pattern), and a positive integer k (the threshold), asks to list the k-error occurrences of P in T, that is, all fragments of T whose edit distance to P is at most k. The one-way communication complexity of this problem is the minimum number of bits that Alice, given an instance (P,T,k) of the problem, must send to Bob so that Bob can reconstruct the answer solely from that message. In recent work [STOC'24], we showed that, in the natural parameter regime 0 < k < m < n/2, Ω(n/m ⋅ k log(m/k)) bits are necessary and 𝒪(n/m ⋅ k log² m) bits are sufficient for this problem. More generally, for strings over an alphabet Σ, we gave an 𝒪(n/m ⋅ k log m log(m|Σ|))-bit encoding that allows one to recover a shortest sequence of edits for every k-error occurrence of P in T. In this paper, we revisit the original proof and improve the encoding size to 𝒪(n/m ⋅ k log (m|Σ|/k)), which matches the lower bound for constant-sized alphabets. We further establish a new tight lower bound of Ω(n/m ⋅ k log(m|Σ|/k)) for the edit sequence reporting variant we solve. Our encoding size also matches the communication complexity established for the simpler Pattern Matching with Mismatches problem in the context of streaming algorithms [Clifford, Kociumaka, Porat; SODA'19].

Given a graph and two vertices s and t, the Replacement Path Problem (RP) is to compute for every edge e, the distance between s and t when e is removed. There are two natural extensions to RP: - Single Source Replacement Paths (SSRP): Given a graph 𝐆 and a source node s, compute for every vertex v and every edge e the s-v distance in 𝐆⧵e. That is, we do not fix the target anymore. - 2-Fault Replacement Paths (2-FRP): Given a graph 𝐆 and two nodes s and t, compute for every pair of edges e,e' the s-t distance in 𝐆⧵e,e'. That is, there are two failures instead of one. Previously, there was no known formal reduction between SSRP and 2-FRP. It seemed plausible that 2-FRP would be computationally harder because there are no settings where 2-FRP admits a faster algorithm than SSRP. In directed unweighted graphs there is a provable gap in complexity, and in undirected graphs many of the known 2-FRP algorithms in a variety of settings are much slower than those for SSRP in the same setting. The main contribution of this paper is a tight reduction from undirected 2-FRP to undirected SSRP, showing that contrary to prior intuition, 2-FRP is not harder than SSRP. As our reduction is weight-preserving, we get new algorithms for 2-FRP that match the best-known runtimes for SSRP: (a) 𝒪̃(M n^ω) for weights in [1..M] [Grandoni and Vassilevska Williams, FOCS 2012 & TALG 2019], improving upon 𝒪(Mn^{2.87}) [Chechik, Zhang, ICALP 2024]; (b) n³/2^Ω(√{log n}) for weights in [1..poly(n)] [Grandoni and Vassilevska Williams, FOCS 2012 & TALG 2019], improving over the previous n³polylog(n) running time [Vassilevska W., Woldeghebriel and Xu, FOCS 2022]; (c) 𝒪̃(mn^{1/2} + n²) combinatorial time for unweighted graphs [Chechik and Cohen, SODA 2019], and more generally for rational weights in [1,2] [Chechik and Magen, ICALP 2020], improving upon 𝒪̃(n^{3-1/18}) [Chechik, Zhang ICALP 2024]. We complement these upper bounds with tight lower bounds under fine-grained hypotheses.

String Edit Distance is a more-than-classical problem whose behavior in the dynamic setting, where the strings are updated over time, is well studied. A single-character substitution, insertion, or deletion can be processed in time $\tilde{\mathcal{O}}(n w)$ when operation costs are positive integers bounded by $w$ [Charalampopoulos, Kociumaka, Mozes, CPM 2020][Gorbachev, Kociumaka, STOC 2025]. If the weights are further uniform (insertions and deletions have equal cost), also an $\tilde{\mathcal{O}}(n \sqrt{n})$-update time algorithm exists [Charalampopoulos, Kociumaka, Mozes, CPM 2020]. This is a substantial improvement over the static $\mathcal{O}(n^2)$ algorithm when $w \ll n$ or when we are dealing with uniform weights. In contrast, for inherently related problems such as Tree Edit Distance, Dyck Edit Distance, and RNA Folding, it has remained unknown whether it is possible to devise dynamic algorithms with an advantage over the static algorithm. In this paper, we resolve this question by showing that (weighted) Tree Edit Distance, Dyck Edit Distance, and RNA Folding admit no dynamic speedup: under well-known fine-grained assumptions we show that the best possible algorithm recomputes the solution from scratch after each update. Furthermore, we prove a quadratic per-update lower bound for unweighted Tree Edit Distance under the $k$-Clique Conjecture. This provides the first separation between dynamic unweighted String Edit Distance and unweighted Tree Edit Distance, problems whose relative difficulty in the static setting is still open.

Approximate Pattern Matching is among the most fundamental string-processing tasks. Given a text T of length n, a pattern P of length m, and a threshold k, the task is to identify the fragments of T that are at distance at most k to P. We consider the two most common distances: Hamming distance (the number of mismatches or character substitutions) in Pattern Matching with Mismatches and edit distance (the minimum number of character insertions, deletions, and substitutions) in Pattern Matching with Edits. We revisit the complexity of these two problems in the quantum setting.

The decades-old Pattern Matching with Edits problem, given a length-n string T (the text), a length-m string P (the pattern), and a positive integer k (the threshold), asks to list all fragments of T that are at edit distance at most k from P. The one-way communication complexity of this problem is the minimum amount of space needed to encode the answer so that it can be retrieved without accessing the input strings P and T.

Longest common substring (LCS) is an important text processing problem, which has recently been investigated in the quantum query model. The decision version of this problem, LCS with threshold \(d\) , asks whether two length- \(n\) input strings have a common substring of length \(d\) . The two extreme cases, \(d=1\) and \(d=n\) , correspond, respectively to Element Distinctness and Unstructured Search, two fundamental problems in quantum query complexity. However, the intermediate case \(1\ll d\ll n\) was not fully understood. We show that the complexity of LCS with threshold \(d\) smoothly interpolates between the two extreme cases up to \(n^{o(1)}\) factors: — LCS with threshold \(d\) has a quantum algorithm in \(n^{2/3+o(1)}/d^{1/6}\) query complexity and time complexity, and requires at least \(\Omega(n^{2/3}/d^{1/6})\) quantum query complexity. Our result improves upon previous upper bounds \(\widetilde{O}(\min\{n/d^{1/2},n^{2/3}\})\) (Le Gall and Seddighin ITCS 2022, Akmal and Jin SODA 2022), and answers an open question of Akmal and Jin. Our main technical contribution is a quantum speed-up of the powerful String Synchronizing Set technique introduced by Kempa and Kociumaka (STOC 2019). It consistently samples \(n/\tau^{1-o(1)}\) synchronizing positions in the string depending on their length- \(\Theta(\tau)\) contexts, and each synchronizing position can be reported by a quantum algorithm in \(\widetilde{O}(\tau^{1/2+o(1)})\) time. Our quantum string synchronizing set also yields a near-optimal LCE data structure in the quantum setting. As another application of our quantum string synchronizing set, we study the \(k\) -mismatch Matching problem, which asks if the pattern has an occurrence in the text with at most \(k\) Hamming mismatches. Using a structural result of Charalampopoulos et al. (FOCS 2020), we obtain: — \(k\) -mismatch matching has a quantum algorithm with \(k^{3/4}n^{1/2+o(1)}\) query complexity and \(\widetilde{O}(kn^{1/2})\) time complexity. We also observe a non-matching quantum query lower bound of \(\Omega(\sqrt{kn})\) .

Longest Common Substring (LCS) is an important text processing problem, which has recently been investigated in the quantum query model. The decisional version of this problem, LCS with threshold d, asks whether two length-n input strings have a common substring of length d. The two extreme cases, d = 1 and d = n, correspond respectively to Element Distinctness and Unstructured Search, two fundamental problems in quantum query complexity. However, the intermediate case 1 ≪ d ≪ n was not fully understood.