## Learning a Hidden Hypergraph

** Dana Angluin, Jiang Chen**; 7(Oct):2215--2236, 2006.

### 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

^{4r}

*m*·

*poly*(

*r*,log

*n*)) queries with high probability. The queries can be made in

*O*(min(2

^{r}(log

*m+r*)

^{2}, (log

*m+r*)

^{3})) rounds. We also give an algorithm that learns an almost uniform hypergraph of dimension

*r*using

*O*(2

^{O((1+Δ/2)r)}·

*m*

^{1+Δ/2}·

*poly*(log

*n*)) queries with high probability, where Δ is the difference between the maximum and the minimum edge sizes. This upper bound matches our lower bound of Ω((

*m*/(1+Δ/2))

^{1+Δ/2}) for this class of hypergraphs in terms of dependence on

*m*. The queries can also be made in

*O*((1+Δ) · min(2

^{r}(log

*m+r*)

^{2}, (log

*m+r*)

^{3})) rounds.

[abs][pdf]