Department of Computer Science | Institute of Theoretical Computer Science | CADMO
Prof. Emo Welzl and Prof. Bernd Gärtner
Mittagsseminar Talk Information |
Date and Time: Thursday, November 21, 2019, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Anders Martinsson
Mastermind is a classical board game in which Codemaker creates a hidden codeword consisting of a sequence of length n where each element can be one of k colors. Codebreaker must then figure out the hidden codeword by making as few queries as possible. For the commercial version, n=4 and k=6, it was shown by Knuth (1977) that Codebreaker can always win in 5 moves. The general version has gained some attention in part due to its connection to the boardgame, and in part due to its connection to classical problems in information theory. In 1983, Chvátal showed surprisingly that a simple random strategy is optimal for Codebreaker whenever k\leq n^{1-\eps}. For larger k, in particular k=n, his approach leaves a gap of \Omega(n) and O(n \log n) for the minimum number of queries. In 2016, it was shown by Doerr, Doerr, Spöhel, Thomas how codebreaker can win in O(n \log \log n) steps. In this talk, I will present recent work showing that the minimum number of queries needed for n=k Mastermind is in fact \Theta(n). This is joint work with Pascal Su.
Upcoming talks | All previous talks | Talks by speaker | Upcoming talks in iCal format (beta version!)
Previous talks by year: 2025 2024 2023 2022 2021 2020 2019 2018 2017 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996
Information for students and suggested topics for student talks
Automatic MiSe System Software Version 1.4803M | admin login