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 -