The Communication Complexity of Pattern Matching with Edits Revisited

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),…