Evolvability need not imply learnability

Nisheeth Srivastava

We show that Boolean functions expressible as monotone disjunctive normal forms are PAC-evolvable under a uniform distribution on the Boolean cube if the hypothesis size is allowed…