Finding a majority ball with majority answers

Mate Vizer
MTA Alfred Renyi Institute of Mathematics

Daniel Gerbner
MTA Alfred Renyi Institute of Mathematics

Balazs Keszegh
MTA Alfred Renyi Institute of Mathematics

Balazs Patkos
MTA-ELTE Geometric and Algebraic Combinatorics Research Group

Domotor Palvolgyi
Department of Computer Science, Eotvos Lorand University

Gabor Wiener
Department of Computer Science and Information Theory, Budapest University of Technology and Economics

PDF

Minisymposium: GENERAL SESSION TALKS

Content: Suppose we are given a set of $n$ balls $\{b_1,\ldots,b_n\}$ each colored either red or blue in some way unknown to us. To find out some information about the colors, we can query any triple of balls $\{b_{i_1},b_{i_2},b_{i_3}\}$. As an answer to such a query we obtain (the index of) a {\em majority ball}, that is, a ball whose color is the same as the color of another ball from the triple. Our goal is to find a {\em non-minority ball}, that is, a ball whose color occurs at least $\frac n2$ times among the $n$ balls. We show that the minimum number of queries needed to solve this problem is $\Theta(n)$ in the adaptive case and $\Theta(n^3)$ inthe non-adaptive case. We also consider some related problems.

Back to all abstracts