Non-Adaptive Learning a Hidden Hipergraph
This addresses a computational learning theory problem for researchers, offering a more efficient solution but is incremental as it builds on prior non-adaptive algorithms.
The paper tackles the problem of non-adaptively learning a hidden hypergraph from edge-detecting queries, presenting a new deterministic algorithm that runs in polynomial time and asks almost optimal queries, improving over previous exponential-time or non-optimal methods.
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.