Almost all monotone Boolean functions are polynomially learnable using membership queries

DOI10.1016/S0020-0190(00)00225-8MaRDI QIDQ1603482zbMATH OpenFDO

Authors R. Smith, I. Shmulevich, A. D. Korshunov, Jaakko Astola

Publication date 14 July 2002

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

Full work available at URL https://doi.org/10.1016/S0020-0190(00)00225-8

zbMATH Keywords

Computational complexityLearningMembership queryMonotone Boolean function

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational learning theory (68Q32)

Recommendations

• Exact learning Boolean functions via the monotone theory
• On learning monotone Boolean functions with irrelevant variables
• Parallel attribute-efficient learning of monotone Boolean functions
• Learning Monotone Decision Trees in Polynomial Time
• Learning Monotone Boolean Functions by Uniformly Distributed Examples

Cites work

• Complexity of identification and dualization of positive Boolean functions
• Efficient read-restricted monotone CNF/DNF dualization by learning with membership queries
• Exact learning Boolean functions via the monotone theory
• scientific article; zbMATH DE number 3825713 (Why is no real title available?)
• Polynomial-Time Recognition of 2-Monotonic Positive Boolean Functions Given by an Oracle
• The Maximum Latency and Identification of Positive Boolean Functions

Cited in

(10)

• Exact learning of linear combinations of monotone terms from function value queries
• Learning of monotone functions with single error correction
• An average study of hypergraphs and their minimal transversals
• On algorithms for construction of all irreducible partial covers
• Exact learning Boolean functions via the monotone theory
• Minimizing the average query complexity of learning monotone Boolean functions
• On learning monotone Boolean functions with irrelevant variables
• Learning k-Term Monotone Boolean Formulae.
• Computational aspects of monotone dualization: a brief survey
• On the complexity of monotone dualization and generating minimal hypergraph transversals

This page was built for publication: Almost all monotone Boolean functions are polynomially learnable using membership queries

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