Non-adaptive learning of a hidden hypergraph

摘要

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 hypergraphs that asks an almost optimal number of queries. (C) 2017 Elsevier B.V. All rights reserved.