Learning a Hidden Hypergraph

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 4 r 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 ][ bib ] &copy JMLR 2006. ( edit, beta )

Authors

• Dana Angluin
• Jiang Chen

Keywords

No keywords are indexed for this paper.