ML Anthology

Non-Adaptive Learning of a Hidden Hypergraph

Hasan Abasi, Nader H. Bshouty, Hanna Mazzawi
ALT 2015 pp. 89-101
doi:10.1007/978-3-319-24486-0_6 /alt/2015/abasi2015alt-nonadaptive/

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 an almost optimal number of queries.

PDF ALT Semantic Scholar

Cite

Text

Abasi et al. "Non-Adaptive Learning of a Hidden Hypergraph." International Conference on Algorithmic Learning Theory, 2015. doi:10.1007/978-3-319-24486-0_6

Markdown

[Abasi et al. "Non-Adaptive Learning of a Hidden Hypergraph." International Conference on Algorithmic Learning Theory, 2015.](https://mlanthology.org/alt/2015/abasi2015alt-nonadaptive/) doi:10.1007/978-3-319-24486-0_6

BibTeX

@inproceedings{abasi2015alt-nonadaptive,
  title     = {{Non-Adaptive Learning of a Hidden Hypergraph}},
  author    = {Abasi, Hasan and Bshouty, Nader H. and Mazzawi, Hanna},
  booktitle = {International Conference on Algorithmic Learning Theory},
  year      = {2015},
  pages     = {89-101},
  doi       = {10.1007/978-3-319-24486-0_6},
  url       = {https://mlanthology.org/alt/2015/abasi2015alt-nonadaptive/}
}