Polynomial Certificates for Propositional Classes
Abstract
This paper studies the query complexity of learning classes of expressions in propositional logic from equivalence and membership queries. We give new constructions of polynomial size certificates of non-membership for monotone, unate and Horn CNF functions. Our constructions yield quantitatively different bounds from previous constructions of certificates for these classes. We prove lower bounds on certificate size which show that for some parameter settings the certificates we construct for these classes are exactly optimal. Finally, we also prove that a natural generalization of these classes, the class of renamable Horn CNF functions, does not have polynomial size certificates of non-membership, thus answering an open question of Feigelson.
Cite
Text
Arias et al. "Polynomial Certificates for Propositional Classes." Annual Conference on Computational Learning Theory, 2003. doi:10.1007/978-3-540-45167-9_39Markdown
[Arias et al. "Polynomial Certificates for Propositional Classes." Annual Conference on Computational Learning Theory, 2003.](https://mlanthology.org/colt/2003/arias2003colt-polynomial/) doi:10.1007/978-3-540-45167-9_39BibTeX
@inproceedings{arias2003colt-polynomial,
title = {{Polynomial Certificates for Propositional Classes}},
author = {Arias, Marta and Khardon, Roni and Servedio, Rocco A.},
booktitle = {Annual Conference on Computational Learning Theory},
year = {2003},
pages = {537-551},
doi = {10.1007/978-3-540-45167-9_39},
url = {https://mlanthology.org/colt/2003/arias2003colt-polynomial/}
}