Computing majority with triple queries

DOI10.1016/j.tcs.2012.03.039zbMath1253.68170OpenAlexW2007760711MaRDI QIDQ690459

Gábor Wiener, Evangelos Kranakis, Gianluca De Marco

Publication date: 27 November 2012

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

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

zbMATH Keywords

searchballscolorspairing modelqueriescomputation modelsgeneral model

Mathematics Subject Classification ID

Related Items (10)

The majority game with an arbitrary majority ⋮ Finding a majority ball with majority answers ⋮ Adaptive majority problems for restricted query graphs and for weighted sets ⋮ Majority problems of large query size ⋮ Computing majority via multiple queries ⋮ Finding a non-minority ball with majority answers ⋮ From discrepancy to majority ⋮ Finding non-minority balls with majority and plurality queries ⋮ A plurality problem with three colors and query size three ⋮ Searching for majority with k-tuple queries

Cites Work

• Unnamed Item
• Determining the majority
• Randomized strategies for the plurality problem
• On computing majority by comparisons
• Variants of the majority problem.
• Oblivious and adaptive strategies for the majority and plurality problems
• Probabilistic strategies for the partition and plurality problems
• The Average-Case Complexity of Determining the Majority
• Determining plurality
• STACS 2004
• Mathematical Foundations of Computer Science 2003
• Optimization of Reduced Dependencies for Synchronous Sequential Machines
• Search for a majority element

This page was built for publication: Computing majority with triple queries