Electronic Proceedings Article
@InProceedings
Internet-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
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