On the Communication Complexity of Approximate Pattern Matching

The decades-old Pattern Matching with Edits problem, given a length-𝑛 string 𝑇 (the text), a length-𝑚 string 𝑃 (the pattern), and a positive integer 𝑘 (the threshold), asks to list all fragments of 𝑇 that are at edit distance at most 𝑘 from 𝑃. 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 𝑃 and 𝑇.

The closely related Pattern Matching with Mismatches problem (defined in terms of the Hamming distance instead of the edit distance) is already well understood from the communication complexity perspective: Clifford, Kociumaka, and Porat [SODA 2019] proved that Ω(𝑛/𝑚 • 𝑘 log(𝑚/𝑘)) bits are necessary and 𝒪(𝑛/𝑚 • 𝑘 log(𝑚|Σ|/𝑘)) bits are sufficient; the upper bound allows encoding not only the occurrences of 𝑃 in 𝑇 with at most 𝑘 mismatches but also the substitutions needed to make each 𝑘-mismatch occurrence exact.

Despite recent improvements in the running time [Charalampopoulos, Kociumaka, and Wellnitz; FOCS 2020 and 2022], the communication complexity of Pattern Matching with Edits remained unexplored, with a lower bound of Ω(𝑛/𝑚 • 𝑘 log(𝑚/𝑘)) bits and an upper bound of 𝒪(𝑛/𝑚 • 𝑘 3 log 𝑚) bits stemming from previous research. In this work, we prove an upper bound of 𝒪(𝑛/𝑚 • 𝑘 log 2 𝑚) bits, thus establishing the optimal communication complexity up to logarithmic factors. We also show that 𝒪(𝑛/𝑚 • 𝑘 log 𝑚 log(𝑚|Σ|)) bits allow encoding, for each 𝑘-error occurrence of 𝑃 in 𝑇, the shortest sequence of edits needed to make the occurrence exact. Our result further emphasizes the close relationship between Pattern Matching with Mismatches and Pattern Matching with Edits.

We leverage the techniques behind our new result on the communication complexity to obtain quantum algorithms for Pattern Matching with Edits: we demonstrate a quantum algorithm that uses 𝒪(𝑛 1+𝑜(1) /𝑚 • √ 𝑘𝑚) queries and 𝒪(𝑛 1+𝑜(1) /𝑚 • ( √ 𝑘𝑚 + 𝑘 3.5 )) quantum time. Moreover, when determining the existence of at least one occurrence, the algorithm uses 𝒪( 𝑛 1+𝑜(1) /𝑚 • √ 𝑘𝑚) queries and 𝒪( 𝑛 1+𝑜(1) /𝑚 • ( √ 𝑘𝑚 + 𝑘 3.5 )) time. For both cases, we establish corresponding lower bounds to demonstrate that the query complexity is optimal up to sub-polynomial factors. Acknowledgements The work of Philip Wellnitz was carried out at the Max Planck Institute for Informatics. The work of Jakob Nogler was carried out mostly during a summer internship at the Max Planck Institute for Informatics.