On the learnability of discrete distributions

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	Naoki Abe , Manfred K. Warmuth, On the Computational Complexity of Approximating Distributions by Probabilistic Automata, Machine Learning, v.9 n.2-3, p.205-260, July 1992 [doi>10.1007/BF00992677]
	2	Shai Ben-David , Benny Chor , Oded Goldreich , Michael Luby, On the theory of average case complexity, Journal of Computer and System Sciences, v.44 n.2, p.193-219, April 1992 [doi>10.1016/0022-0000(92)90019-F]
	3	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
	4	L Blum , M Blum , M Shub, A simple unpredictable pseudo random number generator, SIAM Journal on Computing, v.15 n.2, p.364-383, May 1986 [doi>10.1137/0215025]
	5	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]
	6	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]
	7	V. Chvatal. A greedy heuristic for the set covering problem. Mathematics o} Operations Research, 4(3):233-235, 1979.
	8	Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
	9	Richard O. Duda and Peter E. Hart. Pattern Classification and Scene Analysis. Wiley, 1973.
	10	Paul Fischer , Hans Ulrich Simon, On learning ring-sum-expansions, SIAM Journal on Computing, v.21 n.1, p.181-192, Feb. 1992 [doi>10.1137/0221014]
	11	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]
	12	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]
	13	Yuri Gurevich, Average case completeness, Journal of Computer and System Sciences, v.42 n.3, p.346-398, June 1991 [doi>10.1016/0022-0000(91)90007-R]
	14	David Haussler, Decision theoretic generalizations of the PAC model for neural net and other learning applications, Information and Computation, v.100 n.1, p.78-150, Sept. 1992 [doi>10.1016/0890-5401(92)90010-D]
	15	David Helmbold , Robert Sloan , Manfred K. Warmuth, Learning integer lattices, SIAM Journal on Computing, v.21 n.2, p.240-266, April 1992 [doi>10.1137/0221019]
	16	Alan Julian Izenman. Recent developments in nonparametric density estimation. Journal of the American Statistical Association, 86(413):205-224, March 1991.
	17	Jeff Kahn, Nathan Linial, and Alex Samorodintsky. Inclusion-exclusion: exact and approximate. Manuscript, 1993.
	18	Michael Kearns, Efficient noise-tolerant learning from statistical queries, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.392-401, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167200]
	19	Michael Kearns , Ming Li, Learning in the presence of malicious errors, SIAM Journal on Computing, v.22 n.4, p.807-837, Aug. 1993 [doi>10.1137/0222052]
	20	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]
	21	Michael J. Kearns , Robert E. Schapire, Efficient distribution-free learning of probabilistic concepts, Journal of Computer and System Sciences, v.48 n.3, p.464-497, June 1994 [doi>10.1016/S0022-0000(05)80062-5]
	22	Robert E. Schapire, The Strength of Weak Learnability, Machine Learning, v.5 n.2, p.197-227, Jun. 1990 [doi>10.1023/A:1022648800760]
	23	L. G. Valiant. The complexity of enumeration and reliability problems. SIAM Journal on Computing, 8(3):410-421,1979.
	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	Vladimir Vapnik, Estimation of Dependences Based on Empirical Data: Springer Series in Statistics (Springer Series in Statistics), Springer-Verlag New York, Inc., Secaucus, NJ, 1982

Collaborative Colleagues:

Michael Kearns: colleagues

Yishay Mansour: colleagues

Dana Ron: colleagues

Ronitt Rubinfeld: colleagues

Robert E. Schapire: colleagues

Linda Sellie: colleagues