3 June 2022: Ramtin Afshar
Exact learning of multitrees and almost-trees using path queries
Given a directed graph, , a path query,
, returns whether there is a directed path
from to in , for . Given only ,
exactly learning all the edges in using path queries is often
impossible, since path queries cannot detect transitive edges. In this
paper, we study the query complexity of exact learning for cases when
learning is possible using path queries. In particular, we
provide efficient learning algorithms, as well as lower bounds, for
multitrees and almost-trees, including butterfly networks.
(Joint work with Michael Goodrich.)