2
$\begingroup$

Let $s \in \{0,1\}^n$ be a secret bitvector. Define $f(x)$ to be the Hamming distance between $x$ and $s$. Suppose I am given an oracle for $f$, and I want to find $x$. How many queries to the oracle are needed to determine $x$? I want an algorithm that is efficient (running time polynomial in $n$, say). I am fine with average-case complexity (over a uniform distribution on $s$).

Information theoretically, $\Theta(n/\lg n)$ randomly chosen queries $x_i$ should suffice, but I can't think of any efficient algorithm to recover $s$ from the values of $f(x_i)$. Obviously $s$ can be efficiently recovered given $n$ queries or so. How much better can we do?

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.