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