Non-Adaptive Learning a Hidden Hipergraph

2015/02/13 by Abasi, Hasan, Bshouty, Nader H., Mazzawi, Hanna
#FOS: Computer and information sciences #Machine Learning (cs.LG)

paper · doi:10.48550/arxiv.1502.04137

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.

Related

• Non-adaptive Learning of Random Hypergraphs with Queries
• Learning Low Degree Hypergraphs
• Adaptive Learning a Hidden Hypergraph
• A Fast Hierarchical Splitting Approach for Non-Adaptive Learning of Random Hypergraphs
• Finding a Hidden Edge