Computing Majority with Triple Queries

Gianluca De Marco, Evangelos Kranakis, Gabor Wiener

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…