The Learning and Communication Complexity of Subsequence Containment
公开 Deposited可下载的内容
open in viewerWe 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
- 贡献者
- Degree
- Unit
- Publisher
- Identifier
- etd-81996
- Advisor
- Defense date
- Year
- 2022
- Date created
- 2022-12-02
- Resource type
- Source
- etd-81996
- Rights statement
- 最新修改
- 2023-11-03
关系
- 属于 Collection:
项目
Permanent link to this page: https://digital.wpi.edu/show/8623j213j