Non-Adaptive Learning a Hidden Hipergraph
Hasan Abasi, Nader H. Bshouty, Hanna Mazzawi · arXiv (Cornell University) · 2015
We give a new deterministic algorithm that non-adaptively learns a hidden hypergraph from edge-detecting queries. All previous non-adaptive algorithms either run in exponential time or have non-optimal query complexity. We give the first polynomial time non-adaptive learning algorithm for learning hypergraph that asks almost optimal number of queries.