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 if it contains a fixed binary string y as a subsequence. In the communication problem, x and y are partitioned between two players, Alice and Bob, who wish to determine if x contains y as a subsequence using a minimal amount of communication. We devise asymptotically tight bounds for the sample complexity (VC dimension) of the learning problem and the communication complexity of the communication problem. Our results illustrate that the sample complexity of our learning problem can be considerably larger when the subsequence occurs in non-contiguous locations.

Creator

• DiCicco, Mason

Contributori

• Reichman, Daniel
• Sarkozy, Gabor N

Degree

• MS

Unit

• Computer Science

Publisher

• Worcester Polytechnic Institute

Identifier

• etd-81996

Advisor

• Reichman, Daniel

Defense date

• 2022-11-21

Year

• 2022

Date created

• 2022-12-02

Resource type

• Thesis

Source

• etd-81996

Rights statement

• In Copyright

Ultima modifica

• 2023-11-03