Crytographic limitations on learning Boolean formulae and finite automata

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	L. Adleman, K. Manders, G. Miller. On taking roots in finite fields. Prec. 18th IEEE Syrup. on Foundations of Computer Science, 1977, pp. 175- 178.
	2	D. Aldous. On the Maxkov chain simulation method for uniform combinatorial distributions and simulated annealing. U.C. Berkeley Statistics Department, technical report 60, 1986.
	3	Werner Alexi , Benny Chor , Oded Goldreich , Claus P. Schnorr, RSA and Rabin functions: certain parts are as hard as the whole, SIAM Journal on Computing, v.17 n.2, p.194-209, April 1988 [doi>10.1137/0217013]
	4	D. Angluin. Lecture notes on the complexity of some problems in number theory. Yale University Computer Science Department, technical report TR-243, 1982.
	5	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]
	6	Paul W Beame , Stephen A Cook , H James Hoover, Log depth circuits for division and related problems, SIAM Journal on Computing, v.15 n.4, p.994-1003, Nov. 1986 [doi>10.1137/0215070]
	7	Gyora M. Benedek , Alon Itai, Learnability by fixed distributions, Proceedings of the first annual workshop on Computational learning theory, p.80-90, August 03-05, 1988, MIT, Cambridge, Massachusetts, United States
	8	A. Blum, An O(n^0.4)-approximation algorithm for 3-coloring, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.535-542, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73058]
	9	Avrim Blum , Ronald L. Rivest, Training a 3-node neural network is NP-complete, Proceedings of the first annual workshop on Computational learning theory, p.9-18, August 03-05, 1988, MIT, Cambridge, Massachusetts, United States
	10	A Blumer , A Ehrenfeucht , D Haussler , M Warmuth, Classifying learnable geometric concepts with the Vapnik-Chervonenkis dimension, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.273-282, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12158]
	11	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]
	12	H. Chernoff. A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. Annals of Mathematical Statistics, 23, 1952, pp. 493-509.
	13	A.K. Ohanclra, L.J. Stockmeyer and U. Vishkin. Constant depth reducibility. SIAM J. on Comput(nq 13 (2), 1984 pp. 423-432.
	14	A. Ehrenfeucht, D. Haussler. Personal communication.
	15	A. Ehrenfeucht , David Haussler , Michael Kearns , Leslie Valiant, A general lower bound on the number of examples needed for learning, Proceedings of the first annual workshop on Computational learning theory, p.139-154, August 03-05, 1988, MIT, Cambridge, Massachusetts, United States
	16	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	17	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]
	18	David Haussler , Michael Kearns , Nick Littlestone , Manfred K. Warmuth, Equivalence of models for polynomial learnability, Proceedings of the first annual workshop on Computational learning theory, p.42-55, August 03-05, 1988, MIT, Cambridge, Massachusetts, United States
	19	D. Haussler, N. Littlestone, M. Warmuth. Predicting 0,1-functions on randomly drawn points. Proc. of the B9th IEEE Syrup. on Foundations of Computer Science, 1988, pp. 100-109.
	20	J. Stephen Judd, Learning in neural networks, Proceedings of the first annual workshop on Computational learning theory, p.2-8, August 03-05, 1988, MIT, Cambridge, Massachusetts, United States
	21	M. Kearns , M. Li , L. Pitt , L. Valiant, On the learnability of Boolean formulae, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.285-295, January 1987, New York, New York, United States [doi>10.1145/28395.28426]
	22	Evangelos Kranakis, Primality and cryptography, John Wiley & Sons, Inc., New York, NY, 1986
	23	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]
	24	Ming Li , Umest Vazirani, On the learnability of finite automata, Proceedings of the first annual workshop on Computational learning theory, p.359-370, August 03-05, 1988, MIT, Cambridge, Massachusetts, United States
	25	L. Pitt, M.K. Warmuth. Reductions among prediction problems' on the difficulty of predicting automata. Proc. 3d Conference on Structure in Complexity Theory, 1988, pp. 60-69.
	26	L. Pitt , M. K. Warmuth, The minimum consistent DFA problem cannot be approximated within and polynomial, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.421-432, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73048]
	27	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]
	28	M. O. Rabin, DIGITALIZED SIGNATURES AND PUBLIC-KEY FUNCTIONS AS INTRACTABLE AS FACTORIZATION, Massachusetts Institute of Technology, Cambridge, MA, 1979
	29	J. H. Reif. On threshold circuits and polynomial computation. Proc. 2nd IEEE Conference on Structure in Complexity Theory, 1987.
	30	R. L. Rivest , A. Shamir , L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM, v.21 n.2, p.120-126, Feb. 1978 [doi>10.1145/359340.359342]
	31	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]
	32	L.G. Valiant. Learning disjunctions of conjunctions. Proc. 9th International Joint Conference on Artificial Intelligence, 1985, pp. 560-566.
	33	Avi Wigderson, A new approximate graph coloring algorithm, Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.325-329, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802207]
	34	A.C. Yao. Theory and application of trapdoor functions. Proc. ~3rd IEEE Syrup. on the Foundations of Computer Science, 1982, 80-91.