Campus Event Calendar
Event Entry
New for: D1, D2, D3, D4, D5
What and Who
Still Playing Mastermind
Benjamin Doerr
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1, AG 2, AG 3, AG 4, AG 5, RG1, SWS, MMCI
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Tuesday, 27 March 2012
13:00
30 Minutes
E1 4
024
Saarbrücken
Abstract
We play Mastermind with n positions, n colors and black answer pegs only. In other words, you try to guess a hidden word in {1, ..., n}^n by guessing such words. For each guess, I tell you exactly in how many positions your guess and my hidden secret coincide. The main question is how many guesses you need to find the secret.
Surprisingly, the best known bound is only O(n log(n)), whereas for n^{\eps} \le k \le n^{1-\eps} colors, \Theta(n) guesses are necessary and sufficient.
In this talk, I'll give a good argument why such a gap is natural, and a better one, why not.
This is on-going work with Reto Spoehel, Henning Thomas (ETH) and Carola Winzen.
Contact
Benjamin Doerr
--email hidden
passcode not visible
logged in users only
Tags, Category, Keywords and additional notes
Black board talk
Benjamin Doerr, 03/27/2012 14:43
Benjamin Doerr, 03/22/2012 22:57
Benjamin Doerr, 03/22/2012 18:14
Benjamin Doerr, 03/22/2012 18:13 -- Created document.
Benjamin Doerr, 03/22/2012 22:57
Benjamin Doerr, 03/22/2012 18:14
Benjamin Doerr, 03/22/2012 18:13 -- Created document.