Learning DNF in time

DOI10.1145/380752.380809MaRDI QIDQ5175978zbMATH OpenOpenAlexFDO

Authors Adam R. Klivans, Rocco A. Servedio

Publication date 27 February 2015

Published in Proceedings of the thirty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/380752.380809

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Computational learning theory (68Q32)

Recommendations

• Learning DNF in time \(2^{\widetilde O(n^{1/3})}\)
• An \(O(n^{\log \log n})\) learning algorithm for DNF under the uniform distribution
• On the learnability of disjunctive normal form formulas
• scientific article; zbMATH DE number 4092808
• Exact learning of DNF formulas using DNF hypotheses

Cites work

• A constant-factor approximation algorithm for the \(k\)-median problem (extended abstract)

Cited in

(18)

• Complexity in the case against accuracy estimation
• Learning DNF in time \(2^{\widetilde O(n^{1/3})}\)
• The complexity of properly learning simple concept classes
• Learning intersections of halfspaces with a margin
• Extremal properties of polynomial threshold functions
• Learning DNF from random walks
• Low correlation noise stability of symmetric sets
• Learning hurdles for sleeping experts
• Toward randomized testing of q-monomials in multivariate polynomials
• On testing monomials in multivariate polynomials
• Quantum machine learning: a classical perspective
• A Bayesian framework for learning rule sets for interpretable classification
• scientific article; zbMATH DE number 7250142 (Why is no real title available?)
• Agnostically learning Boolean functions with finite polynomial representation
• New degree bounds for polynomial threshold functions
• Learning intersections and thresholds of halfspaces
• A unified approach to extract interpretable rules from tree ensembles via integer programming
• On learning embedded midbit functions

This page was built for publication: Learning DNF in time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5175978)