Computing majority via multiple queries

DOI10.1016/J.TCS.2014.04.020zbMATH Open1358.05028OpenAlexW2013424608MaRDI QIDQ2453124FDOQ2453124

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

majoritysearchgamestrategyqueryacyclic bipartite graph

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (6)

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

   Recommendations

• Computing majority with triple queries 👍 👎
• Computing Majority with Triple Queries 👍 👎
• On computing majority by comparisons 👍 👎
• Searching for majority with k-tuple queries 👍 👎
• Answering queries addressed to several databases according to a majority merging approach 👍 👎
• On more variants of the majority problem 👍 👎
• Majority merging by adaptive counting 👍 👎
• The Average-Case Complexity of Determining the Majority 👍 👎
• Finding non-minority balls with majority and plurality queries 👍 👎
• On non-adaptive majority problems of large query size 👍 👎

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2453124)