Learning DNF from Random Walks

Cambridge, Massachusettes October 11-October 14

DOI Bookmark:

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

44th Annual IEEE Symposium on Foundat ...

	This Article
	PURCHASE ARTICLE: $19 PDF HTML IEEE Xplore Subscribers
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan/Endnote
	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

	ASCII Text	x
	Nader Bshouty, Elchanan Mossel, Ryan O?Donnell, Rocco A. Servedio, "Learning DNF from Random Walks," Foundations of Computer Science, Annual IEEE 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, Annual IEEE 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, Annual IEEE 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, Annual IEEE 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

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.