[30] Consider DNF over n variables. A DNF formula f is simple if for each term m of

f, there is a vector vm ∈ {0, 1}n that satisfies m but does not satisfy any other monomials of f even by changing one bit and K(vm) = O(log n). Simple DNFs can contain many highprefix-complexity terms as opposed to O(log n)-DNF. For example, take y ∈ {0, 1}n with K(y) ≥ n − O(1). Then the number of 1s in y is about 1

2n. Construct a term m containing xi if yi = 1, and neither xi nor ¬xi otherwise. Then K(m) ≥ n − O(1) but the vector 1m consisting of all 1s satisfies m and has K(1m) = O(log n). The class of simple DNF is pretty general. Show that it is polynomially learnable under m.