ECCC-Report TR12-087https://eccc.weizmann.ac.il/report/2012/087Comments and Revisions published for TR12-087en-usMon, 05 Nov 2012 12:00:53 +0200
Revision 1
| The Query Complexity of Finding a Hidden Permutation |
Peyman Afshani,
Manindra Agrawal,
Doerr Benjamin,
Kasper Green Larsen,
Kurt Mehlhorn,
Winzen Carola
https://eccc.weizmann.ac.il/report/2012/087#revision1We 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.Mon, 05 Nov 2012 12:00:53 +0200https://eccc.weizmann.ac.il/report/2012/087#revision1
Paper TR12-087
| The Deterministic and Randomized Query Complexity of a Simple Guessing Game |
Peyman Afshani,
Manindra Agrawal,
Doerr Benjamin,
Kasper Green Larsen,
Kurt Mehlhorn,
Winzen Carola
https://eccc.weizmann.ac.il/report/2012/087We 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.Sat, 07 Jul 2012 14:16:14 +0300https://eccc.weizmann.ac.il/report/2012/087