Learning DNF in time
From MaRDI portal
Publication:5175978
DOI10.1145/380752.380809zbMath1323.68328OpenAlexW2017496565MaRDI QIDQ5175978
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
Computational learning theory (68Q32) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (17)
Quantum machine learning: a classical perspective ⋮ Learning intersections and thresholds of halfspaces ⋮ Low correlation noise stability of symmetric sets ⋮ On testing monomials in multivariate polynomials ⋮ Complexity in the case against accuracy estimation ⋮ Approximating multilinear monomial coefficients and maximum multilinear monomials in multivariate polynomials ⋮ New degree bounds for polynomial threshold functions ⋮ The complexity of properly learning simple concept classes ⋮ Learning intersections of halfspaces with a margin ⋮ Extremal properties of polynomial threshold functions ⋮ Unnamed Item ⋮ Learning Hurdles for Sleeping Experts ⋮ Learning DNF from random walks ⋮ Unnamed Item ⋮ Agnostically Learning Boolean Functions with Finite Polynomial Representation ⋮ TOWARD RANDOMIZED TESTING OF q-MONOMIALS IN MULTIVARIATE POLYNOMIALS ⋮ On learning embedded midbit functions
Cites Work
This page was built for publication: Learning DNF in time
