TY - GEN

T1 - Hardness of minimizing and learning DNF expressions

AU - Khot, Subhash

AU - Saket, Rishi

PY - 2008

Y1 - 2008

N2 - 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(npoly(log n)), there is no polynomial time algorithm that approximates this problem to within factor d1-ε 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.

AB - 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(npoly(log n)), there is no polynomial time algorithm that approximates this problem to within factor d1-ε 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.

UR - http://www.scopus.com/inward/record.url?scp=57949086063&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=57949086063&partnerID=8YFLogxK

U2 - 10.1109/FOCS.2008.37

DO - 10.1109/FOCS.2008.37

M3 - Conference contribution

AN - SCOPUS:57949086063

SN - 9780769534367

T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

SP - 231

EP - 240

BT - Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008

T2 - 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008

Y2 - 25 October 2008 through 28 October 2008

ER -