Thursday 02 May 2019: Identifying 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.
