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

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.

• Thanks. Doesn't your algorithm take $O(k \log n)$ queries? (Same as Yuval's algorithm.) I'm not sure what $O_k(\cdot)$ means, and I'm a bit lost why you mention a dependence on $2^k$.
– D.W.
Sep 12 '13 at 16:39
• The dependence should be at least $2^k$ since for functions of the form $AND(x_1,\dots,x_k)$ you would need $2^k$ queries to distinguish them from the constant function. Also, after we find some influential coordinates, we should try all possible fixes in them in order to find the next bit. That gives us a multiplicative factor of $2^k$. Sep 14 '13 at 17:14
• Ahh, I see, the $2^k$ dependence comes from the problem of finding $x,y$ such that $f(x)\ne f(y)$. If you sample on random inputs, it'll take something like $2^k$ inputs to find such a pair. Thank you.
– D.W.
Sep 14 '13 at 17:19
• @D.W. If I understand Yuvals answer, he does not give an algorithm for general $k$. He gives a lower bound. Sep 15 '13 at 6:28