Electronic Journal Article
@Article
Zeitschriftenartikel in einem e-Journal



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
Winzen, Carola

dblp
dblp



BibTeX cite key*:

DoerrW12ToCS

Title

Title*:

Playing Mastermind with Constant-Size Memory

Journal

Journal Title*:

Theory of Computing Systems

Journal's URL:

http://www.springer.com/computer/theoretical+computer+science/journal/224

Download URL
for the article:

http://dx.doi.org/10.1007/s00224-012-9438-8

Language:

English

Publisher

Publisher's
Name:

Springer

Publisher's URL:

http://www.springer.com/?SGWID=5-102-0-0-0

Publisher's
Address:

New York, NY

ISSN:

1432-4350

Vol, No, Year, pp.

Volume:

Online First

Number:


Month:


Year*:

2012

Pages:

1-27

Number of VG Pages:


Sequence Number:


DOI:

10.1007/s00224-012-9438-8

Abstract, Links, (C)

Note:

to appear

(LaTeX) Abstract:

We analyze the classic board game of Mastermind with $n$ holes and a
constant number of colors. The classic result of Chv\'atal (Combinatorica 3
(1983), 325-329) states that the codebreaker can find the secret code with
$\Theta(n / \log n)$ questions. We show that this bound remains valid
if the codebreaker may only store a constant number of guesses and
answers. In addition to an intrinsic interest in this question, our
result also disproves a conjecture of Droste, Jansen, and Wegener (Theory
of Computing Systems 39 (2006), 525-544) on the memory-restricted
black-box complexity of the OneMax function class.

URL for the Abstract:


Categories / Keywords:


HyperLinks / References / URLs:


Copyright Message:


Personal Comments:


Download
Access Level:

Internal

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Appearance:

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



BibTeX Entry:

@MISC{DoerrW12ToCS,
AUTHOR = {Doerr, Benjamin and Winzen, Carola},
TITLE = {Playing {Mastermind} with Constant-Size Memory},
JOURNAL = {Theory of Computing Systems},
PUBLISHER = {Springer},
YEAR = {2012},
VOLUME = {Online First},
PAGES = {1--27},
ADDRESS = {New York, NY},
ISBN = {1432-4350},
DOI = {10.1007/s00224-012-9438-8},
NOTE = {to appear},
}


Entry last modified by Anja Becker, 03/13/2013
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 12:41:49 PM
Revisions
6.
5.
4.
3.
2.
Editor(s)
Anja Becker
Anja Becker
Anja Becker
Anja Becker
Anja Becker
Edit Dates
13.03.2013 13:12:14
04.02.2013 14:20:55
04.02.2013 14:20:09
04.02.2013 14:19:52
04.02.2013 14:18:39