Hardness of minimizing and learning DNF expressions

Subhash Khot, Rishi Saket

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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(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.

Original languageEnglish (US)
Title of host publicationProceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008
Pages231-240
Number of pages10
DOIs
StatePublished - 2008
Event49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008 - Philadelphia, PA, United States
Duration: Oct 25 2008Oct 28 2008

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
ISSN (Print)0272-5428

Other

Other49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008
CountryUnited States
CityPhiladelphia, PA
Period10/25/0810/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

    Khot, S., & Saket, R. (2008). Hardness of minimizing and learning DNF expressions. In 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