A simple algorithm for learning O(log n)-term DNF

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A simple algorithm for learning O(log n)-term DNF

Full text

Pdf (253 KB)

Source

Annual Workshop on Computational Learning Theory archive
Proceedings of the ninth annual conference on Computational learning theory table of contents

Desenzano del Garda, Italy

Pages: 266 - 269

Year of Publication: 1996

ISBN:0-89791-811-8

Author

Eyal Kushilevitz

Department of Computer Science, Technion Institute of Technology, Haifa, Israel

Sponsors

Univ degli Studi de Milano : Universite degli Studi de Milano
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGART: ACM Special Interest Group on Artificial Intelligence

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 7, Citation Count: 1

Additional Information:

references cited by index terms collaborative colleagues peer to peer

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/238061.238115 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	AP91	Howard Aizenstein , Leonard Pitt, Exact learning of read-twice DNF formulas (extended abstract), Proceedings of the 32nd annual symposium on Foundations of computer science, p.170-179, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185366]
	AP92	Howard Aizenstein , Leonard Pitt, Exact learning of read-k disjoint DNF and not-so-disjoint DNF, Proceedings of the fifth annual workshop on Computational learning theory, p.71-76, July 27-29, 1992, Pittsburgh, Pennsylvania, United States [doi>10.1145/130385.130393]
	A87	D. Angluin. Learning k-term DNF formulas using queries and counterexamples. Technical Report YALEU/DCS/RR-559, Department of Computer Science. Yale University. August 1987.
	A87b	Dana Angluin, Learning regular sets from queries and counterexamples, Information and Computation, v.75 n.2, p.87-106, November 1, 1987 [doi>10.1016/0890-5401(87)90052-6]
	A88	Dana Angluin, Queries and Concept Learning, Machine Learning, v.2 n.4, p.319-342, April 1988 [doi>10.1023/A:1022821128753]
	BCV96	F. Bergadano. D. Catalano and S. Varricchio. Learning Sat-k-DNF Formulas from .Membership Queries. manuscript.
	BV94	F. Bergadano , S. Varricchio, Learning behaviors of automata from multiplicity and equivalence queries, Proceedings of the second Italian conference on Algorithms and complexity, p.54-62, March 1994, Rome, Italy
	BK+94	Avrim Blum , Roni Khardon , Eyal Kushilevitz , Leonard Pitt , Dan Roth, On learning Read-k-Satisfy-j DNF, Proceedings of the seventh annual conference on Computational learning theory, p.110-117, July 12-15, 1994, New Brunswick, New Jersey, United States [doi>10.1145/180139.181051]
	BR92	Avrim Blum , Steven Rudich, Fast learning of k-term DNF formulas with queries, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.382-389, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129748]
	B93	N. Bshouty, Exact Learning via the Monotone Theory, "Proc. 34th Annu. IEEE Sympos. Found. Comput. Sci.". IEEE Computer Society Press, 1993, pages 302-311.
	B95	Nader H. Bshouty, Simple learning algorithms using divide and conquer, Proceedings of the eighth annual conference on Computational learning theory, p.447-453, July 05-08, 1995, Santa Cruz, California, United States [doi>10.1145/225298.225352]
	Han91	Thomas R. Hancock, Learning 2u DNF formulas and ku decision trees, Proceedings of the fourth annual workshop on Computational learning theory, p.199-212, August 05-07, 1991, Santa Cruz, California, United States
	KV94	Michael J. Kearns , Umesh V. Vazirani, An introduction to computational learning theory, MIT Press, Cambridge, MA, 1994
	RS93	Ronald L. Rivest , Robert E. Schapire, Inference of finite automata using homing sequences, Information and Computation, v.103 n.2, p.299-347, April 1993 [doi>10.1006/inco.1993.1021]
	SS93	Robert E. Schapire , Linda M. Sellie, Learning sparse multivariate polynomials over a field with queries and counterexamples, Proceedings of the sixth annual conference on Computational learning theory, p.17-26, July 26-28, 1993, Santa Cruz, California, United States [doi>10.1145/168304.168307]