Exact Learning of Juntas from Membership Queries

ALT 2016 pp. 115-129

doi:10.1007/978-3-319-46379-7_8 /alt/2016/bshouty2016alt-exact/

Abstract

In this paper we study adaptive and non-adaptive exact learning of Juntas from membership queries. We use new techniques to find new bounds, narrow some of the gaps between the lower bounds and upper bounds and find new deterministic and randomized algorithms with small query and time complexities.

PDF ALT Semantic Scholar

Cite

Text

Bshouty and Costa. "Exact Learning of Juntas from Membership Queries." International Conference on Algorithmic Learning Theory, 2016. doi:10.1007/978-3-319-46379-7_8

Markdown

[Bshouty and Costa. "Exact Learning of Juntas from Membership Queries." International Conference on Algorithmic Learning Theory, 2016.](https://mlanthology.org/alt/2016/bshouty2016alt-exact/) doi:10.1007/978-3-319-46379-7_8

BibTeX

@inproceedings{bshouty2016alt-exact,
  title     = {{Exact Learning of Juntas from Membership Queries}},
  author    = {Bshouty, Nader H. and Costa, Areej},
  booktitle = {International Conference on Algorithmic Learning Theory},
  year      = {2016},
  pages     = {115-129},
  doi       = {10.1007/978-3-319-46379-7_8},
  url       = {https://mlanthology.org/alt/2016/bshouty2016alt-exact/}
}