We study the query complexity of determining a hidden permutation. More specifically, we study the problem of learning a secret $(z,\pi)$ consisting of a binary string $z$ of length $n$ and a permutation $\pi$ of $[n]$. The secret must be unveiled by asking queries $x \in \{0,1\}^n$, and for each query asked, we are returned the score $f_{z,\pi}(x)$ defined as
\[ f_{z,\pi}(x):= \max \{ i \in [0..n]\mid \forall j \leq i: z_{\pi(j)} = x_{\pi(j)}\}\,;\]
i.e., the length of the longest common prefix of $x$ and $z$ with respect to $\pi$. The goal is to minimize the number of queries asked.

Our main result are
matching upper and lower bounds for this problem,
both for deterministic and randomized query schemes.
The deterministic query complexity is $\Theta(n \log n)$, which, surprisingly,
improves to $\Theta(n \log \log n)$ in the randomized setting.

For the randomized query complexity, both the upper and lower bound are stronger than what can be achieved by standard arguments like the analysis of random queries or information-theoretic considerations.
Our proof of the $\Omega(n \log \log n)$ lower bound is
based on a potential function argument, which seems to be uncommon in the query
complexity literature. We find this potential function technique
a very powerful tool in proving lower bounds for randomized query
schemes and we expect it to find applications in many other query
complexity problems.

We have significantly improved the presentation of our work.

We study the $\leadingones$ game, a Mastermind-type guessing game first
regarded as a test case in the complexity theory of randomized search
heuristics. The first player, Carole, secretly chooses a string $z \in \{0,1\}^n$ and a
permutation $\pi$ of $[n]$.
The goal of the second player, Paul, is to identify the secret $(z,\pi)$
with a small number of
queries. A query is a string $x \in \{0,1\}^n$, and the score of $x$ is
$ f_{z,\pi}(x):=
\max \{ i \in [0..n]
\mid
\forall j \leq i: z_{\pi(j)} = x_{\pi(j)}\}\,,$
the length of the longest common prefix of $x$ and $z$ with respect to $\pi$.
We are interested in the number of queries needed by Paul to identify the
secret.

By using a relatively straightforward strategy, Paul can identify the secret with
$O(n\log n)$ queries and recently only a modest improvement of this to $O(n\log n /\log\log n)$
was available (Doerr, Winzen, 2012 [DW12]).

In this paper, we completely resolve the problem by offering the following
results. We show that when limited to deterministic strategies, $O(n \log n)$ queries is the best possible.
On the other hand, by using randomization Paul can find the secret code with an expected number of
$O(n\log\log n)$ queries, which we prove is optimal by matching it with a lower bound of the same asymptotic
magnitude. Finally, we prove that a number of problems that are naturally related to our problem
(such as deciding whether a sequence of queries and scores is consistent) can
be solved in polynomial time.