We describe three applications in computational learning theory of techniques and ideas recently introduced in the study of parameterized computational complexity. (1) Using paratneterized problem reducibilities, we show that P-sized DNF (CNF) formulas can be exactly learned in time polynomial in the number of variables by extended equivalence queries if and only if the dominating sets of a graph can be learned in polynomial time by extended equivalence queries. (That is, leawning by an arbitary hypothesis class. See Angluin [6].) Since learning dominating sets is a special case of learning monotone CNF formulas, this extends to the exact learning model a result of Kearns, li, Pitt and Valiant in the PAC prediction model [15]. We show that Psized DNF (CNF) formulas can be learned exactly in polynomial time by extended equivalence and membership queries if and only there is an algorithm running in time polynomial in n and k to learn the k element dominating sets of an n vertex graph. We also prove related results concerning the problem of learning lthe truth assignments of weight k for DNF (CNF) formulas (that is, assignments that set exactly k variables to true and the rest to false). (2) We describe a number of learning algorithms for both parameterized and unparameterized graphtheoretic learning problems, such as learning the independent sets, vertex covers or dominating sets oif a