Oblivious and adaptive strategies for the majority and plurality problems

DOI10.1007/s00453-007-0060-0zbMath1124.68075OpenAlexW2065801535WikidataQ101131030 ScholiaQ101131030MaRDI QIDQ2384785

Jia Mao, Ronald L. Graham, Fan R. K. Chung, Andrew Chi-Chih Yao

Publication date: 10 October 2007

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-007-0060-0

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Permutations, words, matrices (05A05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Reliability, testing and fault tolerance of networks and computer systems (68M15)

Related Items

Computing majority via multiple queries, From discrepancy to majority, Computing majority with triple queries, How to play the majority game with a liar, A plurality problem with three colors and query size three, Searching for majority with k-tuple queries