We study the query complexity of determining a hidden permutation. More specifically, we study the problem of learning a secret (z) consisting of a binary string z of length n and a permutation of [n]. The secret must be unveiled by asking queries x01n , and for each query asked, we are returned the score fz(x) defined asfz(x):=maxi[0n]ji:z(j)=x(j);i.e., the length of the longest common prefix of x and z with respect to . 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 (nlogn), which, surprisingly,improves to (nloglogn) 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 (nloglogn) lower bound isbased on a potential function argument, which seems to be uncommon in the querycomplexity literature. We find this potential function techniquea very powerful tool in proving lower bounds for randomized queryschemes and we expect it to find applications in many other querycomplexity problems.