The Communication Complexity of Subsequence Detection

We study the communication complexity of deciding whether a binary sequence $x$ of length $n$ contains a binary sequence $y$ of length $k$ as a subsequence. We give nearly tight bounds for the communication complexity of this problem, and extend most of our results to larger alphabets. Finally, we prove a lower bound for the VC dimension of a family of classifiers that are based on subsequence containment.