Electronic Proceedings Article
@InProceedings
Internet-Beitrag in Tagungsband, Workshop


Show entries of:

this year (2021) | last year (2020) | two years ago (2019) | Notes URL

Action:

login to update
Options:




Library Locked Library locked




Author, Editor
Author(s):
Doerr, Benjamin
Winzen, Carola		dblp
dblp
Editor(s):
Dürr, Christoph
Wilke, Thomas		dblp
dblp
Not MPII Editor(s):
Dürr, Christoph
Wilke, Thomas

BibTeX cite key*:

DoerrW12STACS

Title, Conference

Title*:

Playing Mastermind with Constant-Size Memory

Booktitle*:

29th International Symposium on Theoretical Aspects of Computer Science : STACS'12

Event Address*:

Paris, France
URL of the conference:

http://stacs2012.lip6.fr/

Event Date*:
(no longer used):


URL for downloading the paper:

http://drops.dagstuhl.de/opus/volltexte/2012/3411/

Event Start Date:

29 February 2012
Event End Date:

3 March 2012

Language:

English
Organization:


Publisher

Publisher's Name:

Schloss Dagstuhl/ Leibniz-Zentrum für Informatik

Publisher's URL:


Address*:

Dagstuhl
Type:


Vol, No, pp., Year

Series:

LIPIcs

Volume:

14
Number:


Month:


Pages:

441-452



Sequence Number:


Year*:

2012
ISBN/ISSN:

978-3-939897-35-4


10.4230/LIPIcs.STACS.2012.441


Abstract, Links, ©

URL for Reference:


Note:


(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:




Tags, Categories, Keywords:

Algorithms, Mastermind, black-box complexity, memory-restricted algorithms, query complexity

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:
@INPROCEEDINGS{DoerrW12STACS,
AUTHOR = {Doerr, Benjamin and Winzen, Carola},
 EDITOR = {D{\"u}rr, Christoph and Wilke, Thomas},
 TITLE = {Playing {Mastermind} with Constant-Size Memory},
 BOOKTITLE = {29th International Symposium on Theoretical Aspects of Computer Science : STACS'12},
 PUBLISHER = {Schloss Dagstuhl/ Leibniz-Zentrum für Informatik},
 YEAR = {2012},
 VOLUME = {14},
 PAGES = {441--452},
 SERIES = {LIPIcs},
 ADDRESS = {Paris, France},
 ISBN = {978-3-939897-35-4},
 DOI = {10.4230/LIPIcs.STACS.2012.441},
}

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:54:27 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:44
30.01.2013 14:00:08
30.01.2013 13:57:38
30.01.2013 13:01:02
01/11/2013 01:39:19 PM