Etd

The Learning and Communication Complexity of Subsequence Containment

Pubblico Deposited

Contenuto scaricabile

open in viewer

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
Contributori
Degree
Unit
Publisher
Identifier
  • etd-81996
Advisor
Defense date
Year
  • 2022
Date created
  • 2022-12-02
Resource type
Source
  • etd-81996
Rights statement
Ultima modifica
  • 2023-11-03

Relazioni

In Collection:

Articoli

Elementi

Permanent link to this page: https://digital.wpi.edu/show/8623j213j