On using the Fourier transform to learn disjoint DNF

DOI10.1016/0020-0190(94)90057-4MaRDI QIDQ1318745zbMATH OpenOpenAlexWikidataFDO

Authors Roni Khardon

Publication date 5 April 1994

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(94)90057-4

zbMATH Keywords

Fourier transformmembership queriescomputational learninglearning algorithmDNF

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Orthogonal functions and polynomials, general theory of nontrigonometric harmonic analysis (42C05)

Recommendations

• Weakly learning DNF and characterizing statistical query learning using Fourier analysis
• An \(O(n^{\log \log n})\) learning algorithm for DNF under the uniform distribution
• scientific article; zbMATH DE number 1301800
• On the learnability of disjunctive normal form formulas
• Learning random monotone DNF

Cites work

• Fast learning of \(k\)-term DNF formulas with queries.

Cited in

(7)

• Learning DNF from random walks
• Learning DNF in time \(2^{\widetilde O(n^{1/3})}\)
• scientific article; zbMATH DE number 774007 (Why is no real title available?)
• Weakly learning DNF and characterizing statistical query learning using Fourier analysis
• Learning intersections and thresholds of halfspaces
• On learning monotone DNF under product distributions
• Learning unions of (1)-dimensional rectangles

This page was built for publication: On using the Fourier transform to learn disjoint DNF

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