Exact Learning of Juntas from Membership Queries
This work addresses a theoretical problem in computational learning theory, with incremental improvements in query and time complexities for exact learning.
The paper tackles the problem of exactly learning Juntas from membership queries, developing new techniques to improve bounds and algorithms, with some bounds being tight and potentially requiring breakthroughs in combinatorial problems.
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.