On learning width two branching programs (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On learning width two branching programs (extended abstract)

Full text

Pdf (455 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: 224 - 227

Year of Publication: 1996

ISBN:0-89791-811-8

Authors

Nader H. Bshouty	Department of Computer Science, The University of Calgary, 2500 University Drive NW, Calgary, Alberta, Canada T2N 1N4
Christino Tamon	Department of Computer Science, The University of Calgary, 2500 University Drive NW, Calgary, Alberta, Canada T2N 1N4
David K. Wilson	Department of Computer Science, The University of Calgary, 2500 University Drive NW, Calgary, Alberta, Canada T2N 1N4

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): 3, Downloads (12 Months): 12, Citation Count: 4

Additional Information:

references cited by index terms collaborative colleagues

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.238102 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.

	A88	Dana Angluin, Queries and Concept Learning, Machine Learning, v.2 n.4, p.319-342, April 1988 [doi>10.1023/A:1022821128753]
	AK91	Dana Angluin , Michael Kharitonov, When won't membership queries help?, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.444-454, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103420]
	B89	David A. Barrington, Bounded-width polynomial-size branching programs recognize exactly those languages in NC1, Journal of Computer and System Sciences, v.38 n.1, p.150-164, February 1989 [doi>10.1016/0022-0000(89)90037-8]
	BEHW87	Alselm Blumer , Andrzej Ehrenfeucht , David Haussler , Manfred K. Warmuth, Occam's razor, Information Processing Letters, v.24 n.6, p.377-380, 6 April 1987 [doi>10.1016/0020-0190(87)90114-1]
	BDFP86	Allan Borodin , Danny Dolev , Faith E Fich , Wolfgang Paul, Bounds for width two branching programs, SIAM Journal on Computing, v.15 n.2, p.549-560, May 1986 [doi>10.1137/0215040]
	ERR95	Funda Ergün , S. Ravi Kumar , Ronitt Rubinfeld, On learning bounded-width branching programs, Proceedings of the eighth annual conference on Computational learning theory, p.361-368, July 05-08, 1995, Santa Cruz, California, United States [doi>10.1145/225298.225342]
	HSW92	David Helmbold , Robert Sloan , Manfred K. Warmuth, Learning integer lattices, SIAM Journal on Computing, v.21 n.2, p.240-266, April 1992 [doi>10.1137/0221019]
	K90	M. J. Kearns, The computational complexity of machine learning, Harvard University, Cambridge, MA, 1990
	KV89	M. Kearns , L. G. Valiant, Crytographic limitations on learning Boolean formulae and finite automata, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.433-444, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73049]
	L88	Nick Littlestone, Learning Quickly When Irrelevant Attributes Abound: A New Linear-Threshold Algorithm, Machine Learning, v.2 n.4, p.285-318, April 1988 [doi>10.1023/A:1022869011914]
	RW93	Vijay Raghavan , Dawn Wilkins, Learning &mgr;-branching programs with queries, Proceedings of the sixth annual conference on Computational learning theory, p.27-36, July 26-28, 1993, Santa Cruz, California, United States [doi>10.1145/168304.168308]
	R87	Ronald L. Rivest, Learning Decision Lists, Machine Learning, v.2 n.3, p.229-246, November 1987 [doi>10.1023/A:1022607331053]
	v84	L. G. Valiant, A theory of the learnable, Communications of the ACM, v.27 n.11, p.1134-1142, Nov. 1984 [doi>10.1145/1968.1972]

CITED BY 4

	Leslie G. Valiant, Projection learning, Proceedings of the eleventh annual conference on Computational learning theory, p.287-293, July 24-26, 1998, Madison, Wisconsin, United States
	Atsuyoshi Nakamura, An efficient query learning algorithm for ordered binary decision diagrams, Information and Computation, v.201 n.2, p.178-198, September 15, 2005
	Richard Nock , Tapio Elomaa , Matti Kääriäinen, Reduced error pruning of branching programs cannot be approximated to within a logarithmic factor, Information Processing Letters, v.87 n.2, p.73-78, 31 July 2003
	Leslie G. Valiant, Projection Learning, Machine Learning, v.37 n.2, p.115-130, Nov.1.1999