On the Communication Complexity of Approximate Pattern Matching

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.