Polynomial Certificates for Propositional Classes.
M. Arias and Aaron Feigelson and R. Khardon and R. Servedio
Information and Computation 204(5), May 2006, pp. 816--834.
Preliminary version in
Sixteenth Annual Conference on Computational Learning Theory (COLT), 2003, pp. 537-551.


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 {\em not} have polynomial size certificates of non-membership, thus answering an open question of Feigelson.

Postscript or pdf of conference version

pdf of journal version

Back to main papers page