ICS 269, Spring 2022: Theory Seminar
Bren Hall 1423, 1:00 – 1:50

3 June 2022: Ramtin Afshar

Exact learning of multitrees and almost-trees using path queries

Given a directed graph, $G=(V,E)$, a path query, $\mathrm{path}(u,v)$, returns whether there is a directed path from $u$ to $v$ in $G$, for $u,v\in V$. Given only $V$, exactly learning all the edges in $G$ 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 $G$ 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.)