TY - GEN
T1 - Read-thrice DNF is hard to learn with membership and equivalence queries
AU - Aizenstein, Howard
AU - Hellerstein, Lisa
AU - Pitt, Leonard
N1 - Publisher Copyright:
© 1992 IEEE.
PY - 1992
Y1 - 1992
N2 - A general technique is developed to obtain nonlearnability results in the model of exact learning from equivalence and membership queries. The technique is applied to show that, assuming NP not=co-NP, there does not exist a polynomial-time membership and equivalence query algorithm for exactly learning read-thrice DNF formulas-boolean formulas in disjunctive normal form where each variable appears at most three times. This result adds evidence to the conjecture that DNF is hard to learn in the membership and equivalence query model.
AB - A general technique is developed to obtain nonlearnability results in the model of exact learning from equivalence and membership queries. The technique is applied to show that, assuming NP not=co-NP, there does not exist a polynomial-time membership and equivalence query algorithm for exactly learning read-thrice DNF formulas-boolean formulas in disjunctive normal form where each variable appears at most three times. This result adds evidence to the conjecture that DNF is hard to learn in the membership and equivalence query model.
UR - http://www.scopus.com/inward/record.url?scp=84887485075&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84887485075&partnerID=8YFLogxK
U2 - 10.1109/SFCS.1992.267799
DO - 10.1109/SFCS.1992.267799
M3 - Conference contribution
AN - SCOPUS:84887485075
T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
SP - 523
EP - 532
BT - Proceedings - 33rd Annual Symposium on Foundations of Computer Science, FOCS 1992
PB - IEEE Computer Society
T2 - 33rd Annual Symposium on Foundations of Computer Science, FOCS 1992
Y2 - 24 October 1992 through 27 October 1992
ER -