The Communication Complexity of Pattern Matching with Edits Revisited
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866917415795818496 |
|---|---|
| author | Kociumaka, Tomasz Nogler, Jakob Wellnitz, Philip |
| author_facet | Kociumaka, Tomasz Nogler, Jakob Wellnitz, Philip |
| contents | 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]. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_15601 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | The Communication Complexity of Pattern Matching with Edits Revisited Kociumaka, Tomasz Nogler, Jakob Wellnitz, Philip Data Structures and Algorithms 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]. |
| title | The Communication Complexity of Pattern Matching with Edits Revisited |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2604.15601 |