Complexity theoretic limitations on learning DNF's

Abstract

Using the recently developed framework of [Daniely et al, 2014], we show that under a natural assumption on the complexity of refuting random K-SAT formulas, learning DNF formulas is hard. Furthermore, the same assumption implies the hardness of learning intersections of $\omega (\log (n))$ halfspaces, agnostically learning conjunctions, as well as virtually all (distribution free) learning problems that were previously shown hard (under complexity assumptions).

arXiv admin note: substantial text overlap with arXiv:1311.2272

Cited by in corpus (6)

• Subsampled Power Iteration: a Unified Algorithm for Block Models and Planted CSP's
• Sum of squares lower bounds for refuting any CSP
• Agnostic Learning of Disjunctions on Symmetric Distributions
• Implicitly Learning to Reason in First-Order Logic
• A PTAS for Agnostically Learning Halfspaces
• Inapproximability of VC Dimension and Littlestone's Dimension