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?


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.