Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:




Library Locked Library locked




Author, Editor

Author(s):

Doerr, Benjamin
Spöhel, Reto
Thomas, Henning
Winzen, Carola

dblp
dblp
dblp
dblp

Not MPG Author(s):

Thomas, Henning

Editor(s):





BibTeX cite key*:

DoerrSTW13

Title, Booktitle

Title*:

Playing Mastermind with many colors

Booktitle*:

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2013)

Event, URLs

URL of the conference:

http://www.siam.org/meetings/da13/

URL for downloading the paper:


Event Address*:

New Orleans, USA

Language:

English

Event Date*
(no longer used):


Organization:

ACM-SIAM

Event Start Date:

5 January 2013

Event End Date:

8 January 2013

Publisher

Name*:

SIAM

URL:

http://www.siam.org/

Address*:

Philadelphia, USA

Type:


Vol, No, Year, pp.

Series:


Volume:


Number:


Month:


Pages:

695-704

Year*:

2013

VG Wort Pages:

38

ISBN/ISSN:

9781627484855

Sequence Number:


DOI:




Note, Abstract, ©


(LaTeX) Abstract:

We analyze the general version of the classic guessing game Mastermind with $n$~positions and $k$~colors. Since the case $k \le n^{1-\eps}$, $\eps>0$ constant, is well understood, we concentrate on larger numbers of colors. For the most prominent case $k = n$, our results imply that Codebreaker can find the secret code with $O(n \log \log n)$ guesses. This bound is valid also when only black answer-pegs are used. It improves the $O(n \log n)$ bound first proven by Chv\'atal (Combinatorica 3 (1983), 325--329). We also show that if both black and white answer-pegs are used, then the $O(n \log\log n)$ bound holds for up to $n^2 \log\log n$ colors. These bounds are almost tight as the known lower bound of $\Omega(n)$ shows. Unlike for $k \le n^{1-\eps}$, simply guessing at random until the secret code is determined is not sufficient. In fact, we show that any non-adaptive strategy needs an expected number of $\Omega(n \log n)$ guesses.


Personal Comments:

VGWort pages by Benjamin

Download
Access Level:

Internal

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Audience:

popular

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{DoerrSTW13,
AUTHOR = {Doerr, Benjamin and Sp{\"o}hel, Reto and Thomas, Henning and Winzen, Carola},
TITLE = {Playing Mastermind with many colors},
BOOKTITLE = {Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2013)},
PUBLISHER = {SIAM},
YEAR = {2013},
ORGANIZATION = {ACM-SIAM},
PAGES = {695--704},
ADDRESS = {New Orleans, USA},
ISBN = {9781627484855},
}


Entry last modified by Benjamin Doerr, 02/17/2014
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
[Library]
Created
12/07/2012 01:06:01 PM
Revisions
5.
4.
3.
2.
1.
Editor(s)
Benjamin Doerr
Benjamin Doerr
Stephanie Müller
Carola Winzen
Carola Winzen
Edit Dates
01/31/2014 12:29:23 AM
01/01/2014 10:56:50 PM
04.02.2013 14:07:32
01/15/2013 11:24:47 AM
01/11/2013 01:37:20 PM