Computer Science – Data Structures and Algorithms
Scientific paper
2011-05-09
Computer Science
Data Structures and Algorithms
22 pages, 1 figure, conference version to appear in proceedings of the 17th Annual International Computing and Combinatorics C
Scientific paper
Consider a bin containing $n$ balls colored with two colors. In a $k$-query, $k$ balls are selected by a questioner and the oracle's reply is related (depending on the computation model being considered) to the distribution of colors of the balls in this $k$-tuple; however, the oracle never reveals the colors of the individual balls. Following a number of queries the questioner is said to determine the majority color if it can output a ball of the majority color if it exists, and can prove that there is no majority if it does not exist. We investigate two computation models (depending on the type of replies being allowed). We give algorithms to compute the minimum number of 3-queries which are needed so that the questioner can determine the majority color and provide tight and almost tight upper and lower bounds on the number of queries needed in each case.
Kranakis Evangelos
Marco Gianluca de
Wiener Gábor
No associations
LandOfFree
Computing Majority with Triple Queries does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Computing Majority with Triple Queries, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computing Majority with Triple Queries will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-333745