# Learning a small disjunction

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

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

• 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$. – seteropere Sep 4 '15 at 7:21
• @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? – D.W. Sep 4 '15 at 15:59
• It seems I made a mistake. sorry. You assume uniform sampling where in teaching dimension examples $(x,f(x))$ are supplied by a teacher. – seteropere Sep 4 '15 at 18:45