@inproceedings{f898c60c4af64805b2f11cd0845d1bcf,
title = "Playing mastermind with constant-size memory",
abstract = "We analyze the classic board game of Mastermind with n holes and a constant number of colors. The classic result of Chv{\'a}tal (Combinatorica 3 (1983), 325-329) states that the codebreaker can find the secret code with Θ(n/logn) 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.",
keywords = "Algorithms, Black-box complexity, Mastermind, Memory-restricted algorithms, Query complexity",
author = "Benjamin Doerr and Carola Winzen",
year = "2012",
month = dec,
day = "1",
doi = "10.4230/LIPIcs.STACS.2012.441",
language = "English",
isbn = "9783939897354",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
pages = "441--452",
booktitle = "29th International Symposium on Theoretical Aspects of Computer Science, STACS 2012",
note = "29th International Symposium on Theoretical Aspects of Computer Science, STACS 2012 ; Conference date: 29-02-2012 Through 03-03-2012",
}