On the query complexity of learning

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On the query complexity of learning

Full text

Pdf (883 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: 58 - 66

Year of Publication: 1993

ISBN:0-89791-611-5

Author

Sampath K. Kannan

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): 13, Downloads (12 Months): 25, Citation Count: 5

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.168312 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	Dana Angluin, Queries and Concept Learning, Machine Learning, v.2 n.4, p.319-342, April 1988 [doi>10.1023/A:1022821128753]
	2	Dana Angluin, Negative Results for Equivalence Queries, Machine Learning, v.5 n.2, p.121-150, Jun. 1990 [doi>10.1023/A:1022692615781]
	3	R. Boppana, Amplification of Probabilistic Boolean Formulas, 26th IEEE FOCS, pp. 20-29, (1985).
	4	V. Chvatal, Probabilistic methods in graph theory, Annals of Operations Research 1, pp. 171-182 (1984).
	5	H. Chernoff, A measure of asymptotic efficiency for tests of a hypothesis based on sums of observations, Annals of Math. Stat., 2a pp. 493 -509 (1952).
	6	S. Kannan, On the Query Complexity of Learning and a Technique for Lower Bounds on Monotone Formulae, University of Arizona, TR91-33.
	7	V.M. Khrapchenko, A method of obtaining lower bounds for the complexity rrschemes, Math. Notes Acad. Sci. USSR, 11 pp. 474-479, (1972).
	8	Michael J. Kearns, Computational Complexity of Machine Learning, MIT Press, Cambridge, MA, 1990
	9	P. Raghavan, Lecture Notes on Randomized Algorithms, Research Report, IBM Research Division, RC 15340 (~68237) 1/9/90.
	10	Joel Spencer, Ten Lectures on the Probabilistic Method, Monograph, CBMS-NSF Regional Conference Series in Applied Mathematics, 1987.
	11	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]
	12	L.G. Valiant, Short Monotone Formulae for the Majority Function, Journal of Algorithms, 5, 363 -366 (1984).

CITED BY 5

	Tibor Hegedűs, Generalized teaching dimensions and the query complexity of learning, Proceedings of the eighth annual conference on Computational learning theory, p.108-117, July 05-08, 1995, Santa Cruz, California, United States
	Lisa Hellerstein , Vijay Raghavan , Krishnan Pillaipakkamnatt , Dawn Wilkins, How many queries are needed to learn?, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.190-199, May 29-June 01, 1995, Las Vegas, Nevada, United States
	Nader H. Bshouty , Lisa Hellerstein, Attribute-efficient learning in query and mistake-bound models, Proceedings of the ninth annual conference on Computational learning theory, p.235-243, June 28-July 01, 1996, Desenzano del Garda, Italy
	Lisa Hellerstein , Krishnan Pillaipakkamnatt , Vijay Raghavan , Dawn Wilkins, How many queries are needed to learn?, Journal of the ACM (JACM), v.43 n.5, p.840-862, Sept. 1996
	Nader H. Bshouty , Richard Cleve , Sampath Kannan , Christino Tamon, Oracles and queries that are sufficient for exact learning (extended abstract), Proceedings of the seventh annual conference on Computational learning theory, p.130-139, July 12-15, 1994, New Brunswick, New Jersey, United States