Learning juntas, with membership queries

Question

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?

Answer 1

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$.)

Answer 2

Lerning juntas from membership queries can be done in $O_k(\log(n))$ queries indeed. According to Yuval's answer, this give a correct dependence of $n$. However, the dependence on $k$ is not tight (it will be something like $2^k$).

The answer to this question is actually written in the Learning juntas by Mossel, O'Donnell and R. Servedio, but I'll spell it out anyway.

Note first that it is enough to find in each step one influential coordinate, since we can then recurse to the $(k-1)$-junta problem, by fixing the bits in the coordinates found so far and considering the function restricted to different possible fixes of these coordinates.

In order to find one influential coordinate in $O(\log(n))$ queries let us simply sample our function $f$ on random inputs, until found $x,y \in \{0,1\}^n$ such that $f(x) \neq f(y)$. (If we find no such inputs, we may guess that the function is constant.) Now given such $x$ and $y$, let us pick at random a point $z$ between $x$ and $y$ at distance $0.5dist(x,y)$ from each of them, and read $f(z)$. If $f(x) \neq f(z)$ then we continue with the pair $x,z$, and otherwise we continue with the pair $y,z$. The process continues for at most $\log(n)$ iterations, until we find two neighboring vertices on which $f$ gives different values. This gives us one influential coordinate.