Access Restriction

Author Hellerstein, Lisa ♦ Pillaipakkamnatt, Krishnan ♦ Raghavan, Vijay ♦ Wilkins, Dawn
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1996
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Certificates ♦ Equivalence queries ♦ Exact identification ♦ Membership queries ♦ Polynomial-query learning ♦ Polynomial-time hierarchy ♦ Polynomial-time learning ♦ Proper learning
Abstract We investigate the query complexity of exact learning in the membership and (proper) equivalence query model. We give a complete characterization of concept classes that are learnable with a polynomial number of polynomial sized queries in this model. We give applications of this characterization, including results on learning a natural subclass of DNF formulas, and on learning with membership queries alone. Query complexity has previously been used to prove lower bounds on the time complexity of exact learning. We show a new relationship between query complexity and time complexity in exact learning: If any “honest” class is exactly and properly learnable with polynomial query complexity, but not learnable in polynomial time, then P = NP. In particular, we show that an honest class is exactly polynomial-query learnable if and only if it is learnable using an oracle for Γp4.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1996-09-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 43
Issue Number 5
Page Count 23
Starting Page 840
Ending Page 862

Open content in new tab

   Open content in new tab
Source: ACM Digital Library