Almost all monotone Boolean functions are polynomially learnable using membership queries
From MaRDI portal
Publication:1603482
DOI10.1016/S0020-0190(00)00225-8zbMath1032.68089MaRDI QIDQ1603482
Publication date: 14 July 2002
Published in: Information Processing Letters (Search for Journal in Brave)
Computational learning theory (68Q32) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (4)
On algorithms for construction of all irreducible partial covers ⋮ Computational aspects of monotone dualization: a brief survey ⋮ On the complexity of monotone dualization and generating minimal hypergraph transversals ⋮ An average study of hypergraphs and their minimal transversals
Cites Work
- Efficient read-restricted monotone CNF/DNF dualization by learning with membership queries
- Exact learning Boolean functions via the monotone theory
- Complexity of identification and dualization of positive Boolean functions
- Polynomial-Time Recognition of 2-Monotonic Positive Boolean Functions Given by an Oracle
- The Maximum Latency and Identification of Positive Boolean Functions
- Unnamed Item
This page was built for publication: Almost all monotone Boolean functions are polynomially learnable using membership queries
