Parameterized learning complexity

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Parameterized learning complexity

Full text

Pdf (915 KB)

Source

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

Santa Cruz, California, United States

Pages: 51 - 57

Year of Publication: 1993

ISBN:0-89791-611-5

Authors

Rodney G. Downey
Patricia A. Evans
Michael R. Fellows

Sponsors

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): 14, Downloads (12 Months): 31, Citation Count: 1

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	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/168304.168311 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.

	1	Karl R. Abrahamson , Rodney G. Downey , Michael R. Fellows, Fixed-Parameter Intractability II (Extended Abstract), Proceedings of the 10th Annual Symposium on Theoretical Aspects of Computer Science, p.374-385, February 25-27, 1993
	2	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]
	3	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]
	4	Dana Angluin, Queries and Concept Learning, Machine Learning, v.2 n.4, p.319-342, April 1988 [doi>10.1023/A:1022821128753]
	5	Dana Angluin, Negative Results for Equivalence Queries, Machine Learning, v.5 n.2, p.121-150, Jun. 1990 [doi>10.1023/A:1022692615781]
	6	Dana Angluin, Computational learning theory: survey and selected bibliography, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.351-369, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129746]
	7	L. Clark, P. Evans, M. Fellows and W. Wallis. Algorithms for learning and teaching sets of vertices in graphs. University of Victoria Technical Report DCS-212-IR (1993).
	8	R. Downey and M. Fellows. Fixed parameter tractability and completeness. Congr. Num., 87 (1992) 161-187.
	9	R. Downey and M. Fellows. Fixed parameter tractability and completeness I: basic results. To appear.
	10	R. Downey and M. Fellows. Fixed parameter tractability and completeness II: on completeness for W{1}. To appear.
	11	R. Downey and M. Fellows. Fixed parameter intractability (extended abstract). Proceedings of the Seventh Annual IEEE Conference on Structure ~n Complexity Theory (1992), 36-49.
	12	R. Downey and M. Fellows. Fixed parameter tractability and completeness III: some structural aspects of the W-Hierarchy. To appear in: Complexity Theory (Proceedings of the 1992 Dagstuhl Workshop on Structural Complexity), (ed. Ambos- Spies et. al.) Cambridge University Press.
	13	R. Downey and M. Fellows. Parameterized computational feasibility. To appear in: Feasible Mathematics II (ed. Clote and Remmel), Birkhauser, Boston.
	14	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	15	M. Kearns , M. Li , L. Pitt , L. Valiant, On the learnability of Boolean formulae, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.285-295, January 1987, New York, New York, United States [doi>10.1145/28395.28426]
	16	Leonard Pitt , Manfred K. Warmuth, Prediction-preserving reducibility, Journal of Computer and System Sciences, v.41 n.3, p.430-467, Dec. 1990 [doi>10.1016/0022-0000(90)90028-J]
	17	C. H. Papadimitriou and M. Yannakakis. On the complexity of computing the V-C dimension. Manuscript, May 1992.
	18	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]