Computational sample complexity

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Computational sample complexity

Full text

Pdf (2.12 MB)

Source

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

Nashville, Tennessee, United States

Pages: 130 - 142

Year of Publication: 1997

ISBN:0-89791-891-6

Authors

Scott Decatur	DIMACS Center, Rutgers University, Piscataway, NJ
Oded Goldreich	Dept. of Computer Science, Weizmann Institute, Israel and LCS, MIT
Dana Ron	Laboratory for Computer Science, MIT, Cambridge, MA

Sponsors

AT&T Labs :
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGART: ACM Special Interest Group on Artificial Intelligence
Vanderbilt University : Vanderbilt University

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 15, Downloads (12 Months): 25, 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/267460.267489 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, 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]
	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	Javed A. Aslam , Scott E. Decatur, On the sample complexity of noise-tolerant learning, Information Processing Letters, v.57 n.4, p.189-195, Feb. 26, 1996 [doi>10.1016/0020-0190(96)00006-3]
	4	E. Berlekamp and L. Welch. Error correction of algebraic block codes. US Patent 4,633,470, 1986.
	5	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]
	6	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]
	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	Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
	9	S. Decatur, 0. Goldreich, and D. Ron. Computational sample complexity. Available from the ECCC at http://wvw.eccc.uni-trier.de/eccc!,1997.
	10	Andrzej Ehrenfeucht , David Haussler, A general lower bound on the number of examples needed for learning, Information and Computation, v.82 n.3, p.247-261, Sep. 1989 [doi>10.1016/0890-5401(89)90002-3]
	11	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]
	12	J. H&tad, R. Impagliazzo, L.A. Levin, and M. Luby. Construction of pseudorandom generator from any one-way function. TO appear in SIAM J. on Computing. Preliminary versions by Impagliazzo et. al. in 21sr STOC (1989) and H&tad in 22nd STOC ( 1990).
	13	J. Justesen. A class of constructive asymptotically good alegbraic codes. IEEE Trans. Inform. Theory, 18:652- 656, 1972.
	14	Michael Kearns , Leslie Valiant, Cryptographic limitations on learning Boolean formulae and finite automata, Journal of the ACM (JACM), v.41 n.1, p.67-95, Jan. 1994 [doi>10.1145/174644.174647]
	15	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]
	16	Philip D. Laird, Learning from good and bad data, Kluwer Academic Publishers, Norwell, MA, 1988
	17	M. Naor , O. Reingold, Synthesizers and their application to the parallel construction of pseudo-random functions, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.170, October 23-25, 1995
	18	Leonard Pitt , Leslie G. Valiant, Computational limitations on learning from examples, Journal of the ACM (JACM), v.35 n.4, p.965-984, Oct. 1988 [doi>10.1145/48014.63140]
	19	Hans Ulrich Simon, General bounds on the number of examples needed for learning probabilistic concepts, Proceedings of the sixth annual conference on Computational learning theory, p.402-411, July 26-28, 1993, Santa Cruz, California, United States [doi>10.1145/168304.168385]
	20	M. Talagrand. Sharper bounds for Gaussian and empirical processes. Ann. Probab., 22( 1):28-76, 1994.
	21	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]
	22	V.N. Vapnik and A.Ya. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theor: Probability Appl., 16(2):264-280, I97 1.
	23	A. D. Wyner. The wire-tap channel. Bell System Technical JourFd,54(8):1355-1387,Oct. 1975.
	24	A. C. Yao. Theory and application of trapdoor functions. In 2x3rd FOCS, pages 80-91, 1982.