### Abstract

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.

Original language | English (US) |
---|---|

Title of host publication | Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008 |

Pages | 231-240 |

Number of pages | 10 |

DOIs | |

State | Published - 2008 |

Event | 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008 - Philadelphia, PA, United States Duration: Oct 25 2008 → Oct 28 2008 |

### Publication series

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

ISSN (Print) | 0272-5428 |

### Other

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

Country | United States |

City | Philadelphia, PA |

Period | 10/25/08 → 10/28/08 |

### ASJC Scopus subject areas

- Computer Science(all)

## Fingerprint Dive into the research topics of 'Hardness of minimizing and learning DNF expressions'. Together they form a unique fingerprint.

## Cite this

*Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008*(pp. 231-240). [4690957] (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS). https://doi.org/10.1109/FOCS.2008.37