Non-adaptive Learning of Random Hypergraphs with Queries
This addresses a theoretical limitation in hypergraph learning for researchers in algorithms and combinatorics, though it is incremental as it extends prior graph results to hypergraphs.
The paper tackles the problem of learning hidden hypergraphs non-adaptively with queries, overcoming a known lower bound by assuming the hypergraph is random and k-uniform, and achieves this by connecting it to group testing.
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 $S\subseteq 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 $Ω(\min\{m^2\log n, n^2\})$ 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 Erdős-Rényi 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.