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 functionmonotone Boolean functionsPAC learning

Mathematics Subject Classification ID

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

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

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

Cited in

(14)

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

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)