The junta problem is the following: we have a boolean function $f:\{0,1\}^n \to \{0,1\}$ that actually happens to depend on only $k$ of its input variables. Given the value of $f(x)$ for many random values of $x$, we want to identify the $k$ input variables that $f$ actually depends upon. In other words, secretly $f(x_1,\dots,x_n) = g(x_{i_1},\dots,x_{i_k})$ for some indices $i_1,\dots,i_k$; given many pairs $(x,f(x))$ where each $x$ is random, we want to find the $i_1,\dots,i_k$.
I am interested in a variant of the junta problem, where we are allowed membership queries. In particular, at any point, we can choose a value $x$ and receive the value of $f(x)$. The goal remains the same: We want to learn the junta, i.e., learn the indices $i_1,\dots,i_k$.
How many membership queries are needed, and what is the running time to learn the junta?
There is a simple, straightforward algorithm that uses something like $O(n)$ membership queries (first find $x,y$ such that $f(x)\ne f(y)$, then move from $x$ to $y$ by changing one bit of the input at a time, to identify $x',y'$ such that $f(x')\ne f(y')$ and $x',y'$ differ in a single bit position). But can it be done with many fewer membership queries? For instance, can we learn the junta with, say, $O(\lg n)$ membership queries?