{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2021,10,17]],"date-time":"2021-10-17T04:28:13Z","timestamp":1634444893386},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[1994,1,2]]},"abstract":"\n In this paper, we prove the intractability of learning several classes of Boolean functions in the distribution-free model (also called the Probably Approximately Correct or PAC model) of learning from examples. These results are\n representation independent<\/jats:italic>\n , in that they hold regardless of the syntactic form in which the learner chooses to represent its hypotheses.\n <\/jats:p>\n Our methods reduce the problems of cracking a number of well-known public-key cryptosystems to the learning problems. We prove that a polynomial-time learning algorithm for Boolean formulae, deterministic finite automata or constant-depth threshold circuits would have dramatic consequences for cryptography and number theory. In particular, such an algorithm could be used to break the RSA cryptosystem, factor Blum integers (composite numbers equivalent to 3 modulo 4), and detect quadratic residues. The results hold even if the learning algorithm is only required to obtain a slight advantage in prediction over random guessing. The techniques used demonstrate an interesting duality between learning and cryptography.<\/jats:p>\n We also apply our results to obtain strong intractability results for approximating a generalization of graph coloring.<\/jats:p>","DOI":"10.1145\/174644.174647","type":"journal-article","created":{"date-parts":[[2002,7,27]],"date-time":"2002-07-27T11:26:13Z","timestamp":1027769173000},"page":"67-95","source":"Crossref","is-referenced-by-count":266,"title":["Cryptographic limitations on learning Boolean formulae and finite automata"],"prefix":"10.1145","volume":"41","author":[{"given":"Michael","family":"Kearns","sequence":"first","affiliation":[{"name":"AT&T Bell Laboratories, Murray Hill, New Jersey"}]},{"given":"Leslie","family":"Valiant","sequence":"additional","affiliation":[{"name":"Harvard University, Cambridge, Massachusetts"}]}],"member":"320","reference":[{"key":"e_1_2_1_1_1","first-page":"175","volume-title":"IEEE","author":"~ADLEMAN L."},{"key":"e_1_2_1_2_1","unstructured":"~AHO A. HOPCROFr J. AND ULLMAN J. 1974. The Deszgn and Analyszs of Computer Algorithms. ~Addison-Wesley Reading Mass. ~AHO A. HOPCROFr J. AND ULLMAN J. 1974. The Deszgn and Analyszs of Computer Algorithms. ~Addison-Wesley Reading Mass."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217013"},{"key":"e_1_2_1_4_1","unstructured":"~ANGLUIN D. 1982. Lecture notes on the complexity of some problems in number theory. Tech ~Rep. TR-243. Comput. Sci. Dept. Yale Univ. New Haven Conn. ~ANGLUIN D. 1982. Lecture notes on the complexity of some problems in number theory. Tech ~Rep. TR-243. Comput. Sci. Dept. Yale Univ. New Haven Conn."},{"key":"e_1_2_1_5_1","unstructured":"~ANGLUIN D. 1987. Learning regular sets from queries and counterexamples. Inf. Cornpztt. 75 ~87-106. 10.1016\/0890-5401(87)90052-6 ~ANGLUIN D. 1987. Learning regular sets from queries and counterexamples. Inf. Cornpztt. 75 ~87-106. 10.1016\/0890-5401(87)90052-6"},{"key":"e_1_2_1_6_1","unstructured":"~ANGIUIN D. AND KHARITONOV M. 1991. When won't membership queries help'~ In Proceedings ~of the 23rd ACM Symposium on the Theory of Computing {.New Orleans La May 6-8) ACM ~New York pp. 444-454. 10.1145\/103418.103420 ~ANGIUIN D. AND KHARITONOV M. 1991. When won't membership queries help'~ In Proceedings ~of the 23rd ACM Symposium on the Theory of Computing {.New Orleans La May 6-8) ACM ~New York pp. 444-454. 10.1145\/103418.103420"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022821128753"},{"key":"e_1_2_1_8_1","first-page":"I55","article-title":"Fast probabilistic algorithms for Hamdtoman circuits ~and matchings","volume":"18","author":"~ANGLUIN D.","year":"1979","journal-title":"J. Comput. Syst. Scl."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215070"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/73007.73058"},{"key":"e_1_2_1_11_1","first-page":"9","volume-title":"Calif.","author":"~BLUM A.","year":"1988"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/0213053"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(87)90114-1"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/76359.76371"},{"key":"e_1_2_1_15_1","unstructured":"~CHANDRA n. K. STOCKMEYER L. J. AND VISHK1N U. 1984. Constant depth reducibility. SIAM ~J. Comput. I3 2 423-432. ~CHANDRA n. K. STOCKMEYER L. J. AND VISHK1N U. 1984. Constant depth reducibility. SIAM ~J. Comput. I3 2 423-432."},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1214\/aoms\/1177729330","article-title":"A measure of asymptotic etfic~ency for tests of a hypothesis based on the ~sum of observations","volume":"23","author":"~CHERNOFF H.","year":"1952","journal-title":"Ann. Math. Stat."},{"key":"e_1_2_1_17_1","first-page":"644","article-title":"New directions in cryptography","author":"~DIFFIE W.","year":"1976","journal-title":"IEEE Trans. Inf. TheoO, ~22"},{"key":"e_1_2_1_18_1","unstructured":"~GAREY M. AND JOHNSON D. 1979. Computers and intractubihty: A guide to the theory of ~NP-completeness. Freeman. ~GAREY M. AND JOHNSON D. 1979. Computers and intractubihty: A guide to the theory of ~NP-completeness. Freeman."},{"key":"e_1_2_1_19_1","unstructured":"~GOLD E. M. 1978. Complexity of automaton identification from given data. bTf. Cont. 37 ~302-320. ~GOLD E. M. 1978. Complexity of automaton identification from given data. bTf. Cont. 37 ~302-320."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/6490.6503"},{"key":"e_1_2_1_21_1","unstructured":"~HANCOCK T. 1989. On the difficulty of finding small consistent decision trees. Harvard Univer- ~sity unpublished manuscript. ~HANCOCK T. 1989. On the difficulty of finding small consistent decision trees. Harvard Univer- ~sity unpublished manuscript."},{"key":"e_1_2_1_22_1","first-page":"42","volume-title":"Proceedings of the 1988 Workshop on Computational Learning ~Theory. Morgan-Kaufmann, San Mateo, Calif.","author":"~HAUSSLER D.","year":"1988"},{"key":"e_1_2_1_23_1","first-page":"2","volume-title":"Proceedings of the 1988 Workshop on Computa- ~tional Learning Theory. Morgan-Kaufmann, San Mateo, Calif.","author":"~JUDD S.","year":"1984"},{"key":"e_1_2_1_24_1","first-page":"285","volume-title":"ACM","author":"~KEARNS M.","year":"1987"},{"key":"e_1_2_1_25_1","first-page":"57","volume-title":"Proceedings of the 1989 Workshop on Computational Learning ~Theory. Morgan-Kaufmann, San Mateo, Calif.","author":"~KEARNS M.","year":"1989"},{"key":"e_1_2_1_26_1","first-page":"363","volume-title":"Proceedings of the 17th ~ACM Symposium on the Theory of Computing (Providence, R.I., May 6-8), ACM","author":"~LEVIN L. A.","year":"1985"},{"key":"e_1_2_1_27_1","first-page":"359","volume-title":"Proceedings of the 1988 ~Workshop on ComputationalLearning Theory. Morgan-Kaufmann, San Mateo, Calif.","author":"~LI M.","year":"1988"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/48014.63140"},{"key":"e_1_2_1_29_1","first-page":"60","volume-title":"Proceedings of the 3rd IEEE Conference on Stnwture in Complexity ~Theory. IEEE","author":"~PITT L.","year":"1988"},{"key":"e_1_2_1_30_1","first-page":"421","volume-title":"Proceedings of the 21st ACM Symposium on the Theory ~of Computing","author":"~PITT L.","year":"1989"},{"key":"e_1_2_1_31_1","unstructured":"~RAmN M. O. 1979. Digital signatures and public key functions as intractable as factoring. Tech. ~Rep. TM-212. Lab. Comput. Sci. MIT Cambridge Mass. ~RAmN M. O. 1979. Digital signatures and public key functions as intractable as factoring. Tech. ~Rep. TM-212. Lab. Comput. Sci. MIT Cambridge Mass."},{"key":"e_1_2_1_32_1","first-page":"118","volume-title":"Proceedings of the 2nd ~Structure m Complextty Theory Conference.","author":"~RE F, J","year":"1987"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/359340.359342"},{"key":"e_1_2_1_34_1","first-page":"28","volume-title":"Proceedings of the 30th IEEE ~Symposium on the Foundations of Computer Sctence. IEEE","author":"~SCHAP E, R","year":"1989"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1968.1972"},{"key":"e_1_2_1_36_1","unstructured":"~W1GDERSON h. 1983. A new approximate graph coloring algorithm. In Proceedbtgs of the 14th ~ACM Symposium on the Theory of Computing (San Francisco Calif. May 5-7). ACM New ~York pp. 325-329. 10.1145\/800070.802207 ~W1GDERSON h. 1983. A new approximate graph coloring algorithm. In Proceedbtgs of the 14th ~ACM Symposium on the Theory of Computing (San Francisco Calif. May 5-7). ACM New ~York pp. 325-329. 10.1145\/800070.802207"},{"key":"e_1_2_1_37_1","first-page":"80","volume-title":"Proceedings of the 23rd IEEE ~Symposium on the Foundations of Computer Science. IEEE","author":"~YAO A. C.","year":"1982"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/174644.174647","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,21]],"date-time":"2021-02-21T19:46:17Z","timestamp":1613936777000},"score":1,"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,1,2]]},"references-count":37,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1994,1,2]]}},"alternative-id":["10.1145\/174644.174647"],"URL":"http:\/\/dx.doi.org\/10.1145\/174644.174647","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":["Artificial Intelligence","Hardware and Architecture","Information Systems","Control and Systems Engineering","Software"],"published":{"date-parts":[[1994,1,2]]}}}