mlsanityData to 7 Oct 2026

Complexity theoretic limitations on learning DNF's

arXiv 1404.3378 ↗First posted 13 Apr 2014cs.LG cs.CCcited by 21

Not on the map. Why?

Abstract (arXiv)

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 ω(log(n)) halfspaces, agnostically learning conjunctions, as well as virtually all (distribution free) learning problems that were previously shown hard (under complexity assumptions).

Key facts. Cited by 21 papers in the map (data through 7 Oct 2026). First posted on arXiv 13 Apr 2014.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 4; 2022: 5; 2023: 4; 2024: 2; 2025: 5; 2026: 1.

21 papers.

Sort:

By area:

  1. 2022Sub-Task Decomposition Enables Learning in Sequence to Sequence Taskscited by 41
  2. 2022Hardness of Noise-Free Learning for Two-Hidden-Layer Neural Networkscited by 27
  3. 2022A Moment-Matching Approach to Testable Learning and a New Characterization of Rademacher Complexitycited by 27
  4. 2021From Local Pseudorandom Generators to Hardness of Learningcited by 24
  5. 2025A Theory of Learning with Autoregressive Chain of Thoughtcited by 20
  6. 2021Efficient Learning with Arbitrary Covariate Shiftcited by 15
  7. 2023Computational Complexity of Learning Neural Networks: Smoothness and Degeneracycited by 10
  8. 2021Learning to Sample from Censored Markov Random Fieldscited by 6
  9. 2022Minimax Optimality (Probably) Doesn't Imply Distribution Learning for GANscited by 6
  10. 2024Improved Hardness Results for Learning Intersections of Halfspacescited by 6
  11. 2023Distributional PAC-Learning from Nisan's Natural Proofscited by 4
  12. 2026Positive Distribution Shift as a Framework for Understanding Tractable Learningcited by 3
9 more
  1. 2023Most Neural Networks Are Almost Learnablecited by 2
  2. 2025Bias Detection via Maximum Subgroup Discrepancycited by 2
  3. 2025The Probably Approximately Correct Learning Model in Computational Learning Theorycited by 2
  4. 2025Limitations of Membership Queries in Testable Learningcited by 2
  5. 2022Clifford Circuits can be Properly PAC Learned if and only if textsfRP=textsfNPcited by 1
  6. 2025On the Hardness of Learning Regular Expressionscited by 1
  7. 2021Iterative Rule Extension for Logic Analysis of Data: an MILP-based heuristic to derive interpretable binary classification from large datasetscited by 0
  8. 2023Learnability with PAC Semantics for Multi-agent Beliefscited by 0
  9. 2024ExDBN: Learning Dynamic Bayesian Networks using Extended Mixed-Integer Programming Formulationscited by 0