Amplification of weak learning under the uniform distribution

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Amplification of weak learning under the uniform distribution

Full text

Pdf (441 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: 347 - 351

Year of Publication: 1993

ISBN:0-89791-611-5

Authors

Dan Boneh
Richard J. Lipton

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): 28, 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.168372 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.

	Fre90	Yoav Freund, Boosting a weak learning algorithm by majority, Proceedings of the third annual workshop on Computational learning theory, p.202-216, August 06-08, 1990, Rochester, New York, United States
	Fre92	Yoav Freund, An improved boosting algorithm and its implications on learning complexity, Proceedings of the fifth annual workshop on Computational learning theory, p.391-398, July 27-29, 1992, Pittsburgh, Pennsylvania, United States [doi>10.1145/130385.130429]
	HR89	Torben Hagerup , C. Rüb, A guided tour of Chernoff bounds, Information Processing Letters, v.33 n.6, p.305-308, February 1990 [doi>10.1016/0020-0190(90)90214-I]
	Kra86	Evangelos Kranakis, Primality and cryptography, John Wiley & Sons, Inc., New York, NY, 1986
	KV89	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]
	Lev87	Leonid A. Levin, One-way functions and Pseudorandom generators, Combinatorica, v.7 n.4, p.357-363, Dec, 1987 [doi>10.1007/BF02579323]
	Man92	Yishay Mansour, An O(nlog log n) learning algorithm for DNF under the uniform distribution, Proceedings of the fifth annual workshop on Computational learning theory, p.53-61, July 27-29, 1992, Pittsburgh, Pennsylvania, United States [doi>10.1145/130385.130391]
	Sch90	Robert E. Schapire, The Strength of Weak Learnability, Machine Learning, v.5 n.2, p.197-227, Jun. 1990 [doi>10.1023/A:1022648800760]
	Val84	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]
	Yao82	A. C. Yao, "Theory and Application of Trapdoors Functions", in 23rd IEEE FOCS, pp. 80- 91, 1982.

CITED BY 5

	Adam R. Klivans , Rocco A. Servedio, Boosting and Hard-Core Set Construction, Machine Learning, v.51 n.3, p.217-238, June 2003
	Adam R. Klivans , Ryan O'Donnell , Rocco A. Servedio, Learning intersections and thresholds of halfspaces, Journal of Computer and System Sciences, v.68 n.4, p.808-840, June 2004
	Luca Trevisan, On uniform amplification of hardness in NP, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Nader H. Bshouty , Elchanan Mossel , Ryan O'Donnell , Rocco A. Servedio, Learning DNF from random walks, Journal of Computer and System Sciences, v.71 n.3, p.250-265, October 2005
	Andrej Bogdanov , Luca Trevisan, Average-case complexity, Foundations and Trends® in Theoretical Computer Science, v.2 n.1, p.1-106, October 2006