Hardness of minimizing and learning DNF expressions

We study the problem of finding the minimum size DNF formula for a function f : {0, 1}^d → {0,1} given its truth table. We show that unless NP ⊆ DTIME(n^{poly(log n)}), there is no polynomial time algorithm that approximates this problem to within factor d^1-ε where ε > 0 is an arbitrarily small constant. Our result essentially matches the known O(d) approximation for the problem. We also study weak learnability of small size DNF formulas. We show that assuming NP ⊈ RP, for arbitrarily small constant ε > 0 and any fixed positive integer t, a two term DNF cannot be PAC-learnt in polynomial time by a t term DNF to within 1/2 + ε accuracy. Under the same complexity assumption, we show that for arbitrarily small constants μ, ε > 0 and any fixed positive integer t, an AND function (i.e. a single term DNF) cannot be PAC-learnt in polynomial time under adversarial p-noise by a t-CNF to within 1/2 + ε accuracy.