loading...
Learning with Errors in Answers to Membership Queries (Extracted Abstract)
Rome, Italy October 17-October 19
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/FOCS.2004.3745th Annual IEEE Symposium on Foundat ...
 This Article 
 
Buy PURCHASE ARTICLE: $19
PDF
HTML
Buy IEEE Xplore Subscribers
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
ASCII Text
x 
 
Laurence Bisht, Nader H. Bshouty, Lawrance Khoury, "Learning with Errors in Answers to Membership Queries (Extracted Abstract)," Foundations of Computer Science, Annual IEEE Symposium on, pp. 611-620, 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), 2004.
 
 
BibTex
x
 
@article{ 10.1109/FOCS.2004.37,
author = {Laurence Bisht and Nader H. Bshouty and Lawrance Khoury},
title = {Learning with Errors in Answers to Membership Queries (Extracted Abstract)},
journal ={Foundations of Computer Science, Annual IEEE Symposium on},
volume = {0},
year = {2004},
issn = {0272-5428},
pages = {611-620},
doi = {http://doi.ieeecomputersociety.org/10.1109/FOCS.2004.37},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Foundations of Computer Science, Annual IEEE Symposium on
TI - Learning with Errors in Answers to Membership Queries (Extracted Abstract)
SN - 0272-5428
SP611
EP620
A1 - Laurence Bisht,
A1 - Nader H. Bshouty,
A1 - Lawrance Khoury,
PY - 2004
KW - null
VL - 0
JA - Foundations of Computer Science, Annual IEEE Symposium on
ER -
 
Laurence Bisht, Technion
Nader H. Bshouty, Technion
Lawrance Khoury, Technion

We study the learning models defined in [AKST97]: Learning with equivalence and limited membership queries and learning with equivalence and malicious membership queries.

We show that if a class of concepts that is closed under projection is learnable in polynomial time using equivalence and (standard) membership queries then it is learnable in polynomial time in the above models. This closes the open problems in [AKST97].

Our algorithm can also handle errors in the equivalence queries.

Citation:
Laurence Bisht, Nader H. Bshouty, Lawrance Khoury, "Learning with Errors in Answers to Membership Queries (Extracted Abstract)," focs, pp.611-620, 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), 2004
Usage of this product signifies your acceptance of the Terms of Use.