id: 02176127
dt: a
an: 02176127
au: Vinodchandran, N.Variyam
ti: Learning DNFs and circuits using teaching assistants.
so: Chwa, Kyung-Yong (ed.) et al., Computing and combinatorics. 10th annual
    international conference, COCOON 2004, Jeju Island, Korea, August
    17‒20, 2004. Proceedings. Berlin: Springer (ISBN 3-540-22856-X/pbk).
    Lecture Notes in Computer Science 3106, 188-197 (2004).
py: 2004
pu: Berlin: Springer
la: EN
cc: 
ut: 
ci: 
li: doi:10.1007/b99243
ab: Summary: In this paper we consider the complexity of learning monotone DNF
    formulae and Boolean circuits in an exact learning model called the
    teaching assistant model. This model, introduced in one of our earlier
    works, uses teaching assistant classes for classifying learning
    problems. Teaching assistant classes are a learning-theoretic analog of
    complexity classes. We show that monotone DNFs are learnable using a
    teaching assistant in the class SPP. On the other hand, Boolean
    circuits and general DNFs are not learnable using an SPP teaching
    assistant unless $\text{NP}\subseteq \text{SPP}$. We also show that
    learnability of Boolean circuits with an assistant in the class NP will
    improve the Karp-Lipton collapse result to $\text{P}^{\text{NP}}$.
rv: