The Learning and Communication Complexity of Subsequence Containment

Mason DiCicco, Daniel Reichman

We consider the learning and communication complexity of subsequence containment. In the learning problem, we seek to learn a classifier that positively labels a binary string $x$…