Non-adaptive Learning of Random Hypergraphs with Queries

We study the problem of learning a hidden hypergraph G=(V,E) by making a single batch of queries (non-adaptively). We consider the hyperedge detection model, in which every query must be of the form: ``Does this set Ssubseteq V contain at least one full hyperedge?'' In this model, it is known that there is no algorithm that allows to non-adaptively learn arbitrary hypergraphs by making fewer than Omega(minm2log n, n2) even when the hypergraph is constrained to be 2-uniform (i.e. the hypergraph is simply a graph). Recently, Li et al. overcame this lower bound in the setting in which G is a graph by assuming that the graph learned is sampled from an ErdHos-R'enyi model. We generalize the result of Li et al. to the setting of random k-uniform hypergraphs. To achieve this result, we leverage a novel equivalence between the problem of learning a single hyperedge and the standard group testing problem. This latter result may also be of independent interest.