Testing problems with sub-learning sample complexity

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Testing problems with sub-learning sample complexity

Full text

Pdf (1.68 MB)

Source

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

Madison, Wisconsin, United States

Pages: 268 - 279

Year of Publication: 1998

ISBN:1-58113-057-0

Authors

Michael Kearns	AT&T Labs Research, 180 Park Avenue, Florham Park, NJ
Dana Ron	Laboratory for Computer Science, MIT, 545 Technology Square, Cambridge, MA

Sponsors

University of Wisconsin : University of Wisconsin
UC @ Santa Cruz : UC @ Santa Cruz
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): 1, Downloads (12 Months): 7, Citation Count: 2

Additional Information:

references cited by index terms collaborative colleagues peer to peer

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/279943.279996 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	M. Bellare , D. Coppersmith , J. Hastad , M. Kiwi , M. Sudan, Linearity testing in characteristic two, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.432, October 23-25, 1995
	2	Manuel Blum , Michael Luby , Ronitt Rubinfeld, Self-testing/correcting with applications to numerical problems, Journal of Computer and System Sciences, v.47 n.3, p.549-595, Dec. 1993 [doi>10.1016/0022-0000(93)90044-W]
	3	O. Goldreich , S. Goldwasser , D. Ron, Property testing and its connection to learning and approximation, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.339, October 14-16, 1996
	4	Oded Goldreich , Dana Ron, Property testing in bounded degree graphs, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.406-415, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258627]
	5	Oded Goldreich , Dana Ron, A sublinear bipartiteness tester for bounded degree graphs, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.289-298, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276767]
	6	S. Goldwasser and S. Micali. Probabilistic encryption. Journal of Computer and System Sciences, 28(2):270- 299, 1984.
	7	Michael Kearns , Ming Li , Leslie Valiant, Learning Boolean formulas, Journal of the ACM (JACM), v.41 n.6, p.1298-1328, Nov. 1994 [doi>10.1145/195613.195656]
	8	Jack Carl Kiefer. Introduction to Statistical Inference. Springer Verlag, 1987.
	9	Sanjeev R. Kulkarni , Ofer Zeitouni, On probably correct classification of concepts, Proceedings of the sixth annual conference on Computational learning theory, p.111-116, July 26-28, 1993, Santa Cruz, California, United States [doi>10.1145/168304.168318]
	10	Ronitt Rubinfeld, On the Robustness of Functional Equations, SIAM Journal on Computing, v.28 n.6, p.1972-1997, Dec. 1999 [doi>10.1137/S0097539796298625]
	11	Ronitt Rubinfeld , Madhu Sudan, Robust Characterizations of Polynomials withApplications to Program Testing, SIAM Journal on Computing, v.25 n.2, p.252-271, February 1996 [doi>10.1137/S0097539793255151]
	12	Kenji Yamanishi, Probably Almost Discriminative Learning, Machine Learning, v.18 n.1, p.23-50, Jan. 1995 [doi>10.1023/A:1022870506888]

CITED BY 2

	Oded Goldreich, Property testing in massive graphs, Handbook of massive data sets, Kluwer Academic Publishers, Norwell, MA, 2002
	Oded Goldreich , Shari Goldwasser , Dana Ron, Property testing and its connection to learning and approximation, Journal of the ACM (JACM), v.45 n.4, p.653-750, July 1998