UC Irvine

Given the vertices, V, of an unknown graph G = (V, E), exact learning refers to the process of reconstructing the edges, E, to learn its structure using an all-knowing black box oracle. This is motivated by a broad range of applications from network discovery, where the goal is to infer the topology of a communication network from queries, to computational biology and digital phylogeny, where we wish to learn how a set of objects have been evolved through a set of experiments. In this dissertation, we study various instances of exact learning of graphs using different query settings. For instance, we present an optimal algorithm to learn digital phylogenetic trees (directed rooted trees) using path queries, where a path query given two vertex, u and v, it returns true if and only if there is a directed path from u to v. We also provide efficient algorithms to learn other directed graphs such as multitrees, butterfly networks, and almost-trees from path queries. In addition, we study efficient learning algorithms for network mapping using kth-hop queries, where a kth-hop query given vertex u and v and integer k, it returns the k-th vertex on a shortest path from u to v.