Non-adaptive Learning of Random Hypergraphs with Queries

Bethany Austhof, Lev Reyzin, Erasmo Tani

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…