Learning DNF in time \(2^{\widetilde O(n^{1/3})}\)
type: Item
instance of: scholarly article
title: Learning DNF in time \(2^{\widetilde O(n^{1/3})}\)
zbMATH Open document ID: 1073.68036
author: Adam R. Klivans
author: Rocco A. Servedio
published in: Journal of Computer and System Sciences
publication date: 2004-11-22T00:00:00Z
Mathematics Subject Classification ID: 68Q32
zbMATH DE Number: 2117375
zbMATH Keywords: Disjunctive Normal Form
zbMATH Keywords: Computational learning theory
zbMATH Keywords: Polynomial threshold function
MaRDI profile type: Publication
full work available at URL: j.jcss.2003.07.007
OpenAlex ID: W1517311456
cites work: Queries and concept learning
cites work: Classification by polynomial surfaces
cites work: The expressive power of voting polynomials
cites work: A lower bound for perceptrons and an oracle separation of the \(PP^{PH}\) hierarchy
cites work: Rank-\(r\) decision trees are a subclass of \(r\)-decision lists
cites work: A polynomial-time algorithm for learning noisy linear threshold functions
cites work: Weakly learning DNF and characterizing statistical query learning using Fourier analysis
cites work: Fast learning of \(k\)-term DNF formulas with queries.
cites work: Learnability and the Vapnik-Chervonenkis dimension
cites work: A subexponential exact learning algorithm for DNF using equivalence queries
cites work: Worst-case analysis of the Perceptron and Exponentiated Update algorithms
cites work: Q5543516
cites work: Learning decision trees from random examples
cites work: A general lower bound on the number of examples needed for learning
cites work: Boosting a weak learning algorithm by majority
cites work: Large margin classification using the perceptron algorithm
cites work: SeparatingPH fromPP by relativization
cites work: Parity, circuits, and the polynomial-time hierarchy
cites work: Majority gates vs. general weighted threshold gates
cites work: An efficient membership-query algorithm for learning DNF with respect to the uniform distribution
cites work: Efficient noise-tolerant learning from statistical queries
cites work: On using the Fourier transform to learn disjoint DNF
cites work: The Perceptron algorithm versus Winnow: linear versus logarithmic mistake bounds when few input variables are relevant
cites work: On learning monotone DNF formulae under uniform distributions
cites work: On learning visual concepts and DNF formulae
cites work: Approximate inclusion-exclusion
cites work: Learning monotone log-term DNF formulas under the uniform distribution
cites work: Q4505382
cites work: A theory of the learnable
cites work: Q4247017
DOI: 10.1016/J.JCSS.2003.07.007
description: scientific article; zbMATH DE number 2117375