UC Irvine

Exact learning aims at unambiguously determining an unknown concept from answers to a carefully crafted set of questions, where each answer, given by an all-knowing oracle, reveals structural properties of the concept being learned. We consider Exact learning of sequences, i.e. collections of objects with an intrinsic total order. In this setting, we introduce a new kind of oracle, whose answers depend on an augmented version of the problem's input, devised strategically in advance by the learner, to enable efficient learning of the unknown concept. In particular, we study the problem of reconstructing the path traversed from s to t in the known input graph, by placing trackers on a subset T of the vertices, whose intersection with any s-t path results in a unique sequence, thus enabling exact reconstruction. This problem has applications to animal migration tracking and securing of large infrastructures.Since minimizing |T| is NP-complete, we devise approximation and FPT algorithms. We also study the problem of learning an unknown string over a known fixed alphabet. We consider classic oracle queries which have been shown to yield linear query complexity lower bounds, and exploit string periodicity to obtain algorithms with sublinear query complexities. We also study the problem of reconstructing a periodic string that has been corrupted by a small number of errors (e.g. due to noisy transmission channels). Finally, we study lower and upper bounds for learning a general string using jumbled-index queries.