Thursday 02 May 2019Identifying binary strings with noisy oracles

Prof. Jon Rowe - University of Birmingham

IAIS Building/LT2 14:30-15:30

Abstract: In the classic game “Mastermind” a player attempts to determine a hidden sequence of coloured pegs by making guesses, which are scored according to their correctness. Efficient algorithms for this problem are known. For example, when there are just two colours, and the score is given by the Hamming distance to the correct solution, then $\Theta(n/\log n)$ guesses are sufficient. We consider the situation where the score given by the oracle is affected by noise. We present an algorithm which solves this problem more efficiently than previously proposed algorithms, with a run-time of $O(n \log n)$ when the variance of the noise is $O(n)$, and $O(\sigma^2 \log n)$ when the noise variance is larger. We make only minimal assumptions on the noise distribution.

Add to calendar

Add to calendar (.ics)