Nader H. Bshouty

Non-Adaptive Learning a Hidden Hipergraph

2015 · arXiv (Cornell University)

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 …