Revision #1 Authors: Peyman Afshani, Manindra Agrawal, Doerr Benjamin, Kasper Green Larsen, Kurt Mehlhorn, Winzen Carola

Accepted on: 5th November 2012 12:00

Downloads: 4234

Keywords:

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.

TR12-087 Authors: Peyman Afshani, Manindra Agrawal, Doerr Benjamin, Winzen Carola, Kasper Green Larsen, Kurt Mehlhorn

Publication: 7th July 2012 14:16

Downloads: 3729

Keywords:

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.