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 -