Exact Learning of Juntas from Membership Queries

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 r…

Paper

Similar papers

© 2026 NYSGPT2525 LLC