The Learning and Communication Complexity of Subsequence Containment
Público DepositedWe 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
- Colaboradores
- Degree
- Unit
- Publisher
- Identifier
- etd-81996
- Advisor
- Defense date
- Year
- 2022
- Date created
- 2022-12-02
- Resource type
- Source
- etd-81996
- Rights statement
- Última modificação
- 2023-11-03
Relações
- Em Collection:
Itens
Itens
Miniatura | Título | Acesso | Embargo Release Date | Ações |
---|---|---|---|---|
|
Thesis_with_blank_signature_page.pdf | Público | Baixar |
Permanent link to this page: https://digital.wpi.edu/show/8623j213j