Computing majority via multiple queries

DOI10.1016/j.tcs.2014.04.020zbMath1358.05028OpenAlexW2013424608MaRDI QIDQ2453124

Andrzej M. Borzyszkowski

Publication date: 6 June 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2014.04.020

zbMATH Keywords

gamestrategysearchquerymajorityacyclic bipartite graph

Mathematics Subject Classification ID

Applications of graph theory (05C90) Partitions of sets (05A18) Combinatorial games (91A46)

Related Items (5)

Adaptive majority problems for restricted query graphs and for weighted sets ⋮ Majority problems of large query size ⋮ Finding non-minority balls with majority and plurality queries ⋮ A plurality problem with three colors and query size three ⋮ On non-adaptive majority problems of large query size

Cites Work

• Unnamed Item
• The plurality problem with three colors and more.
• Computing majority with triple queries
• How to play the majority game with a liar
• Randomized strategies for the plurality problem
• On randomized algorithms for the majority problem
• Tight bounds on plurality
• On computing majority by comparisons
• Variants of the majority problem.
• Majority and plurality problems
• Oblivious and adaptive strategies for the majority and plurality problems
• Probabilistic strategies for the partition and plurality problems
• Randomized Algorithms for Determining the Majority on Graphs
• The Average-Case Complexity of Determining the Majority
• Determining plurality
• Average-case analysis of some plurality algorithms
• Mathematical Foundations of Computer Science 2003
• Search for a majority element
• Searching games with errors -- fifty years of coping with liars

This page was built for publication: Computing majority via multiple queries