Being taught can be faster than asking questions

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Being taught can be faster than asking questions

Full text

Pdf (822 KB)

Source

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

Santa Cruz, California, United States

Pages: 144 - 151

Year of Publication: 1995

ISBN:0-89791-723-5

Authors

Ronald L. Rivest	Laboratory for Computer Science, MIT, Cambridge, MA
Yiqun Lisa Yin	RSA Laboratories, 100 Marine Parkway, Redwood City, CA

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGART: ACM Special Interest Group on Artificial Intelligence
University of California : University of California

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 16, Citation Count: 4

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/225298.225315 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	J. Amsterdam. The Valiant Learning Model: Exten- .sions and Assessment. Master thesis, MIT Department of Electrical Engineering and (~omputer Science, January 1988.
	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 , Donna K. Slonim, Randomly Fallible Teachers: Learning Monotone DNF with an Incomplete Membership Oracle, Machine Learning, v.14 n.1, p.7-26, Jan. 1994 [doi>10.1023/A:1022642604085]
	4	A. Blum. Separating distribution-free and mistakebound learning models over the Boolean domain. In Proceedings of the 31st Annual IEEE Symposium on Foundations of Computer Science, volume I, pages 211- 218, 1990.
	5	Avrim Blum , Merrick Furst , Michael Kearns , Richard J. Lipton, Cryptographic primitives based on hard learning problems, Proceedings of the 13th annual international cryptology conference on Advances in cryptology, p.278-291, January 1994, Santa Barbara, California, United States
	6	Manuel Blum , Silvio Micali, How to generate cryptographically strong sequences of pseudo-random bits, SIAM Journal on Computing, v.13 n.4, p.850-864, Nov. 1984 [doi>10.1137/0213053]
	7	Anselm Blumer , A. Ehrenfeucht , David Haussler , Manfred K. Warmuth, Learnability and the Vapnik-Chervonenkis dimension, Journal of the ACM (JACM), v.36 n.4, p.929-965, Oct. 1989 [doi>10.1145/76359.76371]
	8	Sally Ann Goldman , Ronald L. Rivest, Learning binary relations, total orders, and read-once formulas, 1990
	9	Sally A. Goldman , Michael J. Kearns, On the complexity of teaching, Proceedings of the fourth annual workshop on Computational learning theory, p.303-314, August 05-07, 1991, Santa Cruz, California, United States
	10	Sally A. Goldman , H. David Mathias, Teaching a smart learner, Proceedings of the sixth annual conference on Computational learning theory, p.67-76, July 26-28, 1993, Santa Cruz, California, United States [doi>10.1145/168304.168313]
	11	S. (;oldman, R. Rivest, and R. Schapire. Learning binary relations and total orders. In Proceedings of the :~Oth A m~ual IEEE ,5'ympo.s,um o~l l'ou~ldatzona of (;omputer ,5'ezenee, pages 46-51, 1989.
	12	S. (3oldman and R. Slo~m. The power of self-directed learning. Technical Report WIJ(',S-92-49, Washington lIniversity in St. Louis, November 1992.
	13	Oded Goldreich , Shafi Goldwasser , Silvio Micali, How to construct random functions, Journal of the ACM (JACM), v.33 n.4, p.792-807, Oct. 1986 [doi>10.1145/6490.6503]
	14	R. Impagliazzo , L. A. Levin , M. Luby, Pseudo-random generation from one-way functions, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.12-24, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73009]
	15	Jeffrey Jackson , Andrew Tomkins, A computational model of teaching, Proceedings of the fifth annual workshop on Computational learning theory, p.319-326, July 27-29, 1992, Pittsburgh, Pennsylvania, United States [doi>10.1145/130385.130421]
	16	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]
	17	Michael Kharitonov, Cryptographic hardness of distribution-specific learning, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.372-381, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167197]
	18	L A Levin, One-way functions and pseudorandom generators, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.363-365, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22185]
	19	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]
	20	B. K. Natarajan, On learning Boolean functions, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.296-304, January 1987, New York, New York, United States [doi>10.1145/28395.28427]
	21	L. Pitt and M. K. Warmuth. Reductions among prediction problems: On the difficulty of predicting automata (extended abstract). In 3rd IEE~ (:onference on Structure ~n Comple:xzty Theory, pages 60 69, 1988.
	22	S. Salzberg, A. Delcher, D. Heath, and S. Kasif. Learning with a helpful teacher. {n Proceedi~gs of I.}(.7AI-9I, pages 705-711, 1991.
	23	Ayumi Shinohara , Satoru Miyano, Teachability in computational learning, New Generation Computing, v.8 n.4, p.337-347, 1991 [doi>10.1007/BF03037091]
	24	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]
	25	V. N. Vapnik and A. Y. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probabzlity and zts applzeatmna, XVI(2):264-280, 1971.
	26	A. (',. Yao. Theory and applications of trapdoor functions. In Proceedzngs of the 23rd Annual IEEE Symposium on Foundations of Computer Science, pages 80- 91, Chicago, 1982.
	27	Y. L. Yin. On learning r-of-t threshold functions. Unpublished manuscript, 1993.

CITED BY 4

	Marc Fischlin, Cryptographic limitations on parallelizing membership and equivalence queries with applications to random-self-reductions, Theoretical Computer Science, v.268 n.2, p.199-219, 17 October 2001
	Shai Ben-David , Nadav Eiron, Self-Directed Learning and Its Relation to the VC-Dimension and to Teacher-Directed Learning, Machine Learning, v.33 n.1, p.87-104, Oct. 1998
	Reza Ebrahimpour , Ehsanollah Kabir , Mohammad Reza Yousefi, Teacher-directed learning in view-independent face recognition with mixture of experts using overlapping eigenspaces, Computer Vision and Image Understanding, v.111 n.2, p.195-206, August, 2008
	Frank J. Balbach, Measuring teachability using variants of the teaching dimension, Theoretical Computer Science, v.397 n.1-3, p.94-113, May, 2008