Non-Adaptive Learning a Hidden Hipergraph

Abstract

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.

References in corpus (1)

• Linear time Constructions of some $d$-Restriction Problems