Exact learning of juntas from membership queries

DOI10.1016/j.tcs.2017.12.032zbMath1398.68432arXiv1706.06934OpenAlexW3122980917MaRDI QIDQ1663645

Nader H. Bshouty, Areej Costa

Publication date: 22 August 2018

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

Full work available at URL: https://arxiv.org/abs/1706.06934

zbMATH Keywords

adaptive learningexact learningmembership queriesJuntasrelevant variablesnon-adaptive learning

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05)

Related Items (8)

On a combinatorial framework for fault characterization ⋮ Exact learning from an honest teacher that answers membership queries ⋮ Exact learning of juntas from membership queries ⋮ Asymptotic and constructive methods for covering perfect hash families and covering arrays ⋮ Almost Optimal Testers for Concise Representations. ⋮ Subspace restrictions and affine composition for covering perfect hash families ⋮ Partial covering arrays: algorithms and asymptotics ⋮ Almost optimal distribution-free junta testing

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On parallel attribute-efficient learning.
• Adaptive versus nonadaptive attribute-efficient learning
• Exact learning of juntas from membership queries
• Queries and concept learning
• Families of \(k\)-independent sets
• Non-adaptive Learning of a Hidden Hypergraph
• On Exact Learning Monotone DNF from Membership Queries
• Linear Time Constructions of Some $$d$$-Restriction Problems
• Learning juntas
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• Vector sets for exhaustive testing of logic circuits
• Optimal Two-Stage Algorithms for Group Testing Problems

This page was built for publication: Exact learning of juntas from membership queries