Learning DNF from Random Walks

	This Article
	Subscribers, please Login Purchase article: $19 PDF IEEE Xplore Subscribers RSS feed
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by Nader Bshouty Articles by Elchanan Mossel Articles by Ryan O?Donnell Articles by Rocco A. Servedio

44th Annual IEEE Symposium on Foundations of Computer Science (FOCS'03)

Cambridge, Massachusettes

October 11-October 14

ISBN: 0-7695-2040-5

	ASCII Text	x
	Nader Bshouty, Elchanan Mossel, Ryan O?Donnell, Rocco A. Servedio, "Learning DNF from Random Walks," Foundations of Computer Science, IEEE Annual Symposium on, pp. 189, 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS'03), 2003.

	BibTex	x
	@article{ 10.1109/SFCS.2003.1238193, author = {Nader Bshouty and Elchanan Mossel and Ryan O?Donnell and Rocco A. Servedio}, title = {Learning DNF from Random Walks}, journal ={Foundations of Computer Science, IEEE Annual Symposium on}, volume = {0}, year = {2003}, issn = {0272-5428}, pages = {189}, doi = {http://doi.ieeecomputersociety.org/10.1109/SFCS.2003.1238193}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }

	RefWorks Procite/RefMan/Endnote	x
	TY - CONF JO - Foundations of Computer Science, IEEE Annual Symposium on TI - Learning DNF from Random Walks SN - 0272-5428 SP EP A1 - Nader Bshouty, A1 - Elchanan Mossel, A1 - Ryan O?Donnell, A1 - Rocco A. Servedio, PY - 2003 KW - null VL - 0 JA - Foundations of Computer Science, IEEE Annual Symposium on ER -

Nader Bshouty, Technion

Elchanan Mossel, University of California at Berkeley

Ryan O?Donnell, Institute for Advanced Study

Rocco A. Servedio, Columbia University

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/SFCS.2003.1238193

We consider a model of learning Boolean functions from examples generated by a uniform random walk on {0, 1}ⁿ. We give a polynomial time algorithm for learning decision trees and DNF formulas in this model. This is the first efficient algorithm for learning these classes in a natural passive learning model where the learner has no influence over the choice of examples used for learning.

Citation:

Nader Bshouty, Elchanan Mossel, Ryan O?Donnell, Rocco A. Servedio, "Learning DNF from Random Walks," focs, pp.189, 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS'03), 2003

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.