TY - GEN

T1 - Hardness of minimizing and learning DNF expressions

AU - Khot, Subhash

AU - Saket, Rishi

N1 - Funding Information:
An earlier version of this article was presented at the Kentucky Foreign Language Conference in April 2002. Thanks are due to Fred Cheyette, Robert Doran, Donald Maddox, and Michel Zink for feedback that aided in the final preparation of this article. This research was supported in part by a grant from the Amherst College research award program.

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 -