Finding non-minority balls with majority and plurality queries

Abstract

Given a set of $n$ colored balls, a \textit{majority, non-minority or plurality ball} is one whose color class has size more than $n/2$, at least $n/2$ or larger than any other color class, respectively. We describe linear time algorithms for finding non-minority balls using query sets of size $q$ of the following form: the answer to a majority/plurality query $Q$ is a majority/plurality ball in $Q$ or the statement that there is no such ball in $Q$.