This paper by Michael Kearns and Leslie Valiant presents intractability results for learning several classes of Boolean functions in the distribution-free model, also known as the PAC model. The authors prove that learning these classes is difficult regardless of the syntactic form of the hypotheses, provided they can be evaluated in polynomial time. They demonstrate that a polynomial-time learning algorithm for Boolean formulae, deterministic finite automata, or constant-depth threshold circuits would have significant implications for cryptography and number theory, including the ability to break the RSA cryptosystem, factor Blum integers, and detect quadratic residues. The results hold even if the learning algorithm only needs to achieve a slight advantage over random guessing. The techniques used highlight a duality between learning and cryptography. The paper also applies these results to show strong intractability for approximating a generalization of graph coloring.This paper by Michael Kearns and Leslie Valiant presents intractability results for learning several classes of Boolean functions in the distribution-free model, also known as the PAC model. The authors prove that learning these classes is difficult regardless of the syntactic form of the hypotheses, provided they can be evaluated in polynomial time. They demonstrate that a polynomial-time learning algorithm for Boolean formulae, deterministic finite automata, or constant-depth threshold circuits would have significant implications for cryptography and number theory, including the ability to break the RSA cryptosystem, factor Blum integers, and detect quadratic residues. The results hold even if the learning algorithm only needs to achieve a slight advantage over random guessing. The techniques used highlight a duality between learning and cryptography. The paper also applies these results to show strong intractability for approximating a generalization of graph coloring.