1 Department of Computer Science, Science and Technology, Aarhus University2 Department of Computer Science - Center for Massive Data Algoritmics, Department of Computer Science, Science and Technology, Aarhus University3 Indian Institute of Technology, Kanpur4 Max Planck Institute for Informatics5 Department of Computer Science, Science and Technology, Aarhus University
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 as fz(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 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.
Electronic Colloquium on Computational Complexity, 2012, Issue TR12-087