Learning a Hidden Hypergraph

Abstract

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 $^{\rm 4{\it r}}$ m · poly ( r ,log n )) queries with high probability. The queries can be made in O ( min (2^ r r ^2 log^2 n , r ^3 log^3 n )) rounds. We also give an algorithm that learns a non-uniform hypergraph whose minimum edge size is r _1 and maximum edge size is r _2 using $O(f_{1}(r_{1},r_{2})\cdot m^{(r_{2}-r_{1}+2)/2} \cdot poly(log n))$ queries with high probability, and give a lower bound of $\Omega(f_{2}(r_{1},r_{2})\cdot m^{(r_{2}-r_{1}+2)/2})$ for this class of hypergraphs, where f _1 and f _2 are functions depending only on r _1 and r _2. The queries can also be made in $O(min(2^{r2}r^{2}_{2}log^{2} n, r^{3}_{2}log^{3}n))$ rounds.