The Taub Faculty of Computer Science Events and Talks

Learning from membership queries has flourished due to its many applications in different fields. Many of the new applications raised new models and new problems and in many of those applications the function being learned can be an arbitrary function that depends on few variables. We call this class of functions $d$-Junta, where $d$ is the number of relevant variables in the function.

In some of the applications non-adaptive algorithms are most desirable, where in others adaptive algorithms with limited number of rounds are also useful.

In all of the applications, one searches for an algorithm that runs in polynomial time and asks as few queries as possible. In some applications asking queries is very expensive, and therefore, even improving the query complexity by a small non-constant factor is interesting.

In this talk we consider 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 we give 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.

This is a joint work with Nader Bshouty.