Learning juntas, with membership queries

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?

Information theory shows that you need at least $\log_2 \binom{n}{k}$ queries. When $k$ is small, this is $\Theta(k\log n)$, which is probably enough. Consider for example the case $k=1$, and suppose for simplicity that $n$ is a power of $2$. By feeding the inputs $x_i = \text{bit $r$ of $i$}$ to $f$ you can recover the index $i_1$. (To determine whether the function is $i_1$ or $\lnot i_1$, feed the all-zero vector to $f$.)

StackExchange Computer Science Q#14206, answer score: 5