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 …

We investigate cryptographic lower bounds on the learnability of Boolean formulas and
constant depth circuits on the {niform distribution and other specifi; distributions. We first …

Modern cryptography has had considerable impact on the development of computational
learning theory. Virtually every intractability result in Valiant's model [13](which is …

We study the computational feasibility of learning boolean expressions from examples. Our
goals are to prove results and develop general techniques that shed light on the boundary …

We show that the class of all circuits is exactly learnable in randomized expected polynomial-
time using subset and superset queries. This is a consequence of the following result which …

Efficient distribution-free learning of Boolean formulas from positive and negative examples
is considered. It is shown that classes of formulas that are efficiently learnable from only …

This chapter surveys some recent theoretical results on the efficiency of machine learning
algorithms. The main tool described is the notion of Probably Approximately Correct (PAC) …

Emphasizing issues of computational efficiency, Michael Kearns and Umesh Vazirani
introduce a number of central topics in computational learning theory for researchers and …

We give new algorithms for a variety of randomly-generated instances of computational
problems using a linearization technique that reduces to solving a system of linear …

We present new results, both positive and negative, on the well-studied problem of learning
disjunctive normal form (DNF) expressions. We first prove that an algorithm due to …