2
$\begingroup$

I have a boolean function $f: \{0,1\}^n \to \{0,1\}$ that I know takes the form

$$f(x_1,\dots,x_n) = x_{i_1} \lor x_{i_2} \lor \dots \lor x_{i_k},$$

but I don't know the values of $i_1,\dots,i_k$. I am given many pairs $(x,f(x))$ for random values of $x$ (chosen uniformly and independently at random).

I'm looking for an efficient algorithm to recover $i_1,\dots,i_k$, given this information. How efficiently can this be done? How many pairs are needed? Randomized algorithms are OK. I'm particularly interested in the regime where $k \ll n$.

This is similar to the learning juntas problem, but it might be much easier. With the learning juntas problem, we know that $f(x_1,\dots,x_n) = g(x_{i_1},\dots,x_{i_k})$ but neither $i_1,\dots,i_k$ nor $g$ are known. Here, we know $g$ and know that it is a disjunction, so it seems like the problem might be much easier.

I can see an information-theoretic lower bound: $\Omega(k \lg n)$ pairs are needed. There are ${n \choose k}$ possible candidates for $f$, and each pair gives us only one bit of information about $f$, so we need at least $\lg {n \choose k}$ pairs; for small $k$, ${n \choose k} = \Theta(k \lg n)$. How close to this can one get?

This is motivated by an application in inferring input-output relationships in programs (black-box taint analysis).

$\endgroup$
2
$\begingroup$

$\Theta(2^k \lg n)$ queries are necessary and sufficient.

Algorithm

Define $I = \{i_1,\dots,i_k\}$. Our goal is to recover $I$. Given $x$, define $Z(x) = \{i : x_i = 0\}$. For each $x$ where $f(x)=0$, we learn that $Z(x) \subseteq I$. This suggests the following algorithm:

  • Set $J := \{1,2,\dots,n\}$.
  • For each $x$ in the input such that $f(x)=0$, set $J := J \cap Z(x)$.
  • Output $J$.

Analysis: It's guaranteed that this algorithm will output a set $J$ satisfying $I \subseteq J$. Can we ensure that $I=J$? Well, if we have $c \lg n$ values of $x$ where $f(x)=0$, then for any fixed $j \notin I$, $\Pr[j \in J] \le 1/2^{c \lg n} = 1/(2^c n)$; then by a union bound, $\Pr[J \ne I] \le 1/2^c$. So, the probability that this produces the wrong output can be made exponentially small in $c$, as long as we have $c \lg n$ values of $x$ where $f(x)=0$.

Moreover, given $m$ pairs, we expect $m/2^k$ of them to have $f(x)=0$. So, if we have $c \cdot 2^k \lg n$ pairs, we expect $c \lg n$ where $f(x)=0$. Therefore, $O(2^k \lg n)$ pairs suffice to ensure that this algorithm will give the correct answer (except with negligible probability of failure).

Lower bound

This is the best we can do. We can extend the information-theoretic lower bound in the question.

Let's start by showing that $\Omega(2^k)$ pairs are needed. For a random $x$, we have $\Pr[f(x)=0] = 1/2^k$. Therefore, we obviously need $\Omega(2^k)$ pairs to have a good chance of observing at least one pair where $f(x)=0$. With $o(2^k)$ pairs, there's an overwhelming probability that all pairs satisfy $f(x)=1$, in which case we have learned nothing about $f$. So, $\Omega(2^k)$ pairs are needed.

We can improve this lower bound a bit. Call $x$ good if it satisfies $f(x)=0$. Suppose we have to examine $p$ pairs before we see the first good value of $x$. Once we see our first good value of $x$, how many bits of information have we learned about $f$? Only $\lg p$ bits (because one of those $p$ pairs yields 0 and all the rest are 1; there are $p$ ways to select one of them to be 0). It takes about $2^k$ pairs to see the first good value of $x$. So, after observing $2^k$ pairs, we expect to learn about $k$ bits of information about $f$. In general, each good value of $x$ gives us about $k$ bits of information about $f$, and we need to see about $2^k$ pairs per good value obtained. Now as described in the question, we need $\Omega(k \lg n)$ bits to specify $f$ uniquely. Therefore, we need $\Omega(\lg n)$ good values of $x$, so we need $\Omega(2^k \lg n)$ pairs in total.

This gives a lower bound that matches the performance of the algorithm above, to within a constant factor. Therefore, the algorithm above is asymptotically optimal.

$\endgroup$
  • $\begingroup$ Excuse my ignorance here but isn't the Teaching Dimension relevant to your question? I mean showing the TD would give you the minimum number of queries needed to uniquely identify any $f$. $\endgroup$ – seteropere Sep 4 '15 at 7:21
  • $\begingroup$ @seteropere, I confess I'm not familiar with the Teaching Dimension, so I've no clue, but that sure sounds intriguing! Want to try writing an answer? $\endgroup$ – D.W. Sep 4 '15 at 15:59
  • $\begingroup$ It seems I made a mistake. sorry. You assume uniform sampling where in teaching dimension examples $(x,f(x))$ are supplied by a teacher. $\endgroup$ – seteropere Sep 4 '15 at 18:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.