Exact learning of juntas from membership queries
From MaRDI portal
Publication:1663645
DOI10.1007/978-3-319-46379-7_8zbMATH Open1398.68432arXiv1706.06934OpenAlexW3122980917MaRDI QIDQ1663645FDOQ1663645
Publication date: 22 August 2018
Published in: Theoretical Computer Science, Lecture Notes in Computer Science (Search for Journal in Brave)
Abstract: In this paper, we study adaptive and non-adaptive exact learning of Juntas from membership queries. We use new techniques to find new bounds, narrow some of the gaps between the lower bounds and upper bounds and find new deterministic and randomized algorithms with small query and time complexities. Some of the bounds are tight in the sense that finding better ones either gives a breakthrough result in some long-standing combinatorial open problem or needs a new technique that is beyond the existing ones.
Full work available at URL: https://arxiv.org/abs/1706.06934
Recommendations
Cites Work
- Queries and concept learning
- Families of \(k\)-independent sets
- Learning juntas
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- A fast and simple randomized parallel algorithm for the maximal independent set problem
- Title not available (Why is that?)
- Title not available (Why is that?)
- Optimal Two-Stage Algorithms for Group Testing Problems
- Adaptive versus nonadaptive attribute-efficient learning
- Vector sets for exhaustive testing of logic circuits
- Exact learning of juntas from membership queries
- On parallel attribute-efficient learning.
- Non-adaptive Learning of a Hidden Hypergraph
- On Exact Learning Monotone DNF from Membership Queries
- Linear Time Constructions of Some $$d$$-Restriction Problems
Cited In (11)
- Almost optimal distribution-free junta testing
- Asymptotic and constructive methods for covering perfect hash families and covering arrays
- Parameterized learnability of juntas
- Learning with errors in answers to membership queries
- Exact learning from an honest teacher that answers membership queries
- Subspace restrictions and affine composition for covering perfect hash families
- Exact learning of juntas from membership queries
- Parameterized Learnability of k-Juntas and Related Problems
- Partial covering arrays: algorithms and asymptotics
- Almost Optimal Testers for Concise Representations.
- On a combinatorial framework for fault characterization
This page was built for publication: Exact learning of juntas from membership queries
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1663645)
