On learning monotone Boolean functions under the uniform distribution

DOI10.1016/J.TCS.2005.10.012MaRDI QIDQ817825zbMATH OpenOpenAlexFDO

Authors Kazuyuki Amano, A. Maruoka

Publication date 20 March 2006

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2005.10.012

zbMATH Keywords

harmonic analysismajority functionPAC learningmonotone Boolean functions

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Computational learning theory (68Q32) Nonnumerical algorithms (68W05) Boolean functions (06E30)

Recommendations

• scientific article; zbMATH DE number 1966606
• Learning Monotone Decision Trees in Polynomial Time
• On the Fourier spectrum of monotone functions
• Learning Monotone Boolean Functions by Uniformly Distributed Examples
• Exact learning Boolean functions via the monotone theory

Cites work

• scientific article; zbMATH DE number 3685495 (Why is no real title available?)
• scientific article; zbMATH DE number 3073200 (Why is no real title available?)
• A new short proof for the Kruskal-Katona theorem
• A simple proof of the Kruskal-Katona theorem
• Inequalities in Fourier analysis
• Learning Boolean formulas
• On the Fourier spectrum of monotone functions

Cited in

(11)

• Approximating the influence of monotone Boolean functions in \(O(\sqrt{n})\) query complexity
• scientific article; zbMATH DE number 1984562 (Why is no real title available?)
• Aspects of complexity of probabilistic learning under monotonicity constraints
• Approximating the influence of monotone Boolean functions in \(O(\sqrt{n})\) query complexity
• Learning of monotone functions with single error correction
• KKL, Kruskal-Katona, and monotone nets
• Learning k-Term Monotone Boolean Formulae.
• Lower bound on the correlation between monotone families in the average case
• Learning Monotone Decision Trees in Polynomial Time
• scientific article; zbMATH DE number 1966606 (Why is no real title available?)
• Exact learning Boolean functions via the monotone theory

This page was built for publication: On learning monotone Boolean functions under the uniform distribution

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