On learning monotone Boolean functions under the uniform distribution

DOI10.1007/3-540-36169-3_7MaRDI QIDQ4420740zbMATH OpenFDO

Authors Kazuyuki Amano, A. Maruoka

Publication date 18 August 2003

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2533/25330057.htm

Mathematics Subject Classification ID

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

Recommendations

• On learning monotone Boolean functions under the uniform distribution
• Learning Monotone Decision Trees in Polynomial Time
• On the Fourier spectrum of monotone functions
• Learning Monotone Boolean Functions by Uniformly Distributed Examples
• Boolean functions with low average sensitivity depend on few coordinates

Cited in

(13)

• Lower bound on the correlation between monotone families in the average case
• A sensitivity estimate for Boolean functions
• Non-interactive correlation distillation, inhomogeneous Markov chains, and the reverse Bonami-Beckner inequality
• 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.
• On the noise sensitivity of monotone functions
• KKL, Kruskal-Katona, and monotone nets
• Aspects of complexity of probabilistic learning under monotonicity constraints
• Learning random monotone DNF
• On learning monotone Boolean functions under the uniform distribution

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 Q4420740)