Titre : Query Complexity and Mastermind
Exposant : Carola Doerr née Winzen
Résumé : After a short introduction into query complexities, we survey old and
new results for a Mathematician's version of the classic 2-player board
game Mastermind.
For the game with $n$ positions and $k=n$ colors, we show that the
Codebreaker has a winning strategy that uses only $O(n \log\log n)$
guesses for identifying the secret code. This improves the previously
best known bounds of Chv\'atal (Combinatorica, 1983), Goodrich
(Information Processing Letters, 2009), and others, which are all of
order $n \log n$.
We also present a new variant of the Mastermind game - the Hidden
Permutation problem. We present 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.
The result on Mastermind is joint work with Benjamin Doerr (Max Planck
Institute for Informatics), Reto Spoehel (MPI Informatics), and Henning
Thomas (ETH Zuerich), and is to appear at SODA 2013. The result on the
Hidden Permutation problem is joint work with Peyman Afshani (MADALGO
Aarhus), Manindra Agrawal (IIT Kanpur), Benjamin Doerr, Kasper Green
Larsen (MADALGO Aarhus), and Kurt Mehlhorn (MPI Informatics).