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

I don't know the values of $i_1,\dots,i_k$, but I do know $k,n$. My goal is to recover $i_1,\dots,i_k$ from the value of $f$ on randomly chosen inputs, using as few evaluations of $f$ as possible.

There's a twist. I can choose any efficiently sampleable distribution $D$ on $\{0,1\}^n$ that I want, depending on $k,n$. A referee will pick $f$, randomly sample many values of $x$ from $D$ (iid), and then give me $(x,f(x))$ for each such $x$. Then, my ultimate task is to infer $i_1,\dots,i_k$.

I'm looking for an efficient algorithm to select $D$ and then recover $i_1,\dots,i_k$, given the pairs $(x,f(x))$. How efficiently can this be done? What distribution $D$ is optimal? The most relevant complexity measure is probably the number of pairs needed. Randomized algorithms are OK. I'm particularly interested in the regime where $k \ll n$.

This is a generalization of a prior question of mine, where I showed that if we take $D$ to be the uniform distribution on $\{0,1\}^n$ then $\Theta(2^k \lg n)$ pairs are necessary and sufficient. However, it seems likely that the uniform distribution is not optimal. I suspect we can do better by choosing a distribution $D$ that is biased towards values of $x$ with lower Hamming weight.

On first glance, it feels like maybe we can restrict attention to distributions $D$ that is symmetric (i.e., $x$ and $\pi(x)$ have the same probability, for all permutations $\pi$ on the $n$ bits). For instance, we could consider a distribution $D$ where the bits of $x$ are iid Bernoulli(p), for some parameter $p$. Is this right, and if so, what is the optimal distribution $D$ and how many pairs does this mean we will need?

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

$\endgroup$
1
$\begingroup$

$\Theta((k+1) \lg n)$ pairs are sufficient. I think this is the best that's achievable.

Here's the distribution $D$ that achieves this result. Let $p = 1/(k+1)$ and choose each bit of $x$ from Bernoulli(p) (i.i.d.), i.e., each bit of $x$ is $1$ with probability $p$ and $0$ otherwise.

Call $x$ good if $f(x)=0$. Note that if $x$ is chosen according to $D$, it has probability $(1-p)^k$ of being good. This is $(1-1/(k+1))^k$, which is approximately $e^{-1}$ (using the standard approximation $(1-y)^z = e^{-yz}$). So, $\Pr[f(x)=0] \approx 1/e$, and about a constant fraction of pairs are good.

Now we can take all of the good pairs we have, and look for bit positions that are consistently zero in every good pair. If we have enough good pairs, only correct positions $i_1,\dots,i_k$ should remain. Fix a particular incorrect bit position; it has a probability $p$ of being eliminated by each good pair, so the probability that it survives all the good pairs is $(1-p)^g$, where $g$ is the number of good pairs. Taking $g = -2\lg(n)/\lg(1-p) \approx 2 \lg(n)/p$, we find that the probability of survival for a single incorrect bit position after all $g$ good pairs is $1/n^2$. By a union bound, this means the probability that any of the incorrect bit positions survive is about $1/n$. In other words, if we have $2\lg(n)/p$ good pairs, with overwhelming probability this procedure will succeed in correctly inferring $i_1,\dots,i_k$.

Putting these two together, we need about $2e \lg(n)/p$ pairs. Since $1/p=(k+1)$, this is $\Theta((k+1)\lg n)$.

It's possible to show that this is the best possible value of $p$. Define $f(p) = p (1-p)^k$. Then $$f'(p) = (1-p)^{k-1} (1-(k+1)p),$$ since $f'$ is zero at $p=1/(k+1)$, and one can verify that the maximum value of $f(p)$ on the interval $[0,1]$ is attained at $p=1/(k+1)$. Now the total number of pairs needed by the above procedure is $2 \lg(n)/f(p)$, which is minimal for $p=1/(k+1)$. This justifies the choice of $p$ suggested above.

I'd conjecture that you can't do better than this class of distributions $D$ (where each bit of $x$ is chosen iid Bernoulli). If that is right, then it follows that the result given above is the best possible: $\Theta((k+1)\lg n)$ pairs are necessary and sufficient to solve this problem.

$\endgroup$

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.