When: May 2, 2pm

Where: room G2.91b

Abstract

In the majority problem, we are given $n$ balls coloured black or white and we are allowed to query whether two balls have the same colour or not. The goal is to find a ball of majority colour in the minimum number of queries (or deduce that there is no majority). The answer is known to be $n - B(n)$, where $B(n)$ is the number of 1's in the binary representation of $n$. In this talk we we will discuss a randomised version of this problem in which we are allowed to err with probability at most $\varepsilon$. We will provided a randomised algorithm which has expected running time $(2/3 + o(1))n$ and show that this is in fact best possible.