Learning a Hidden Hypergraph
Dana Angluin, Chen Jiang · 2006
We consider the problem of learning a hypergraph using edge-detecting queries. In this model, the learner may query whether a set of vertices induces an edge of the hidden hypergraph or not. We show that an r-uniform hypergraph with m edges and n vertices is learnable with O(2 4r m · poly(r, log n)) queries with high probability. The queries can be made in O(min(2r (log m+r) 2, (log m+r) 3)) rounds. We also give an algorithm that learns