Jakob Nogler

Tomasz Kociumaka, Jakob Nogler, Philip Wellnitz

In 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), the task is 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 Pattern Matching with Edits 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. For the natural parameter regime of $0 < k < m < n/2$, our recent work [STOC'24] yields that $Ω(n/m \cdot k \log(m/k))$ bits are necessary and $O(n/m \cdot k \log^2 m)$ bits are sufficient for Pattern Matching with Edits. More generally, for strings over an alphabet $Σ$, our recent work [STOC'24] gives an $O(n/m \cdot 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 work, we revisit the original proof and improve the encoding size to $O(n/m \cdot k \log(m|Σ|/k))$, which matches the lower bound for constant-sized alphabets. We further establish a new tight lower bound of $Ω(n/m \cdot k \log(m|Σ|/k))$ for the edit sequence reporting variant that 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].

Jakob Nogler, Virginia Vassilevska Williams

Given a graph and two fixed 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: (1) Single Source Replacement Paths (SSRP): Given a graph $G$ and a source node $s$, compute for every vertex $v$ and every edge $e$ the $s$-$v$ distance in $G \setminus \{e\}$. That is, we do not fix the target anymore. (2) $2$-Fault Replacement Paths (2-FRP): Given a graph $G$ and two nodes $s$ and $t$, compute for every pair of edges $e, e'$ the $s$-$t$ distance in $G \setminus \{e, e'\}$. That is, we consider two failures instead of one. Previously, there was no known 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 obtain the first algorithms for $2$-FRP that match the best-known runtimes for SSRP: (1) $\tilde{O}(M n^ω)$ for weights in $[1, M]$ [GVW19], improving upon $O(Mn^{2.87})$ [CZ24]; (2) $n^3/2^{Ω(\sqrt{\log n})}$ for weights in $[1, \text{poly}(n)]$ [GVW19], improving over the previous $n^3\text{polylog}(n)$ running time [VWWX22]; (3) $\tilde{O}(mn^{1/2}+n^{2})$ combinatorial time for unweighted graphs [CC19], and more generally for rational weights in $[1, 2]$ [CM20], improving upon $\tilde{O}(n^{3-1/18})$ [CZ24]. We complement these upper bounds with tight lower bounds under fine-grained hypotheses.