Learning Boolean halfspaces with small weights from membership queries

DOI10.1016/j.tcs.2016.07.030zbMath1358.68152OpenAlexW2476599386MaRDI QIDQ329608

Ali Z. Abdi, Nader H. Bshouty, Hasan Abasi

Publication date: 21 October 2016

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

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

zbMATH Keywords

Boolean functionmonotone functionAngluin learninghalfspaceMAT learningmembership query

Mathematics Subject Classification ID

Computational learning theory (68Q32) Formal languages and automata (68Q45)

Cites Work

• On the number of irreducible points in polyhedra
• Learning a hidden graph using \(O(\log n)\)queries per edge
• Reconstructing a Hamiltonian cycle by querying the graph: Application to DNA physical mapping
• Queries and concept learning
• Learning a Hidden Matching
• Combinatorial results on the complexity of teaching and learning
• Learning a Hidden Subgraph
• Threshold Group Testing
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item