Computing majority via multiple queries

DOI10.1016/J.TCS.2014.04.020MaRDI QIDQ2453124zbMATH OpenOpenAlexFDO

Authors 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)

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

Cites work

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

Cited in

(9)

• Adaptive majority problems for restricted query graphs and for weighted sets
• Finding non-minority balls with majority and plurality queries
• Computing majority with triple queries
• Adaptive majority problems for restricted query graphs and for weighted sets
• A plurality problem with three colors and query size three
• Majority problems of large query size
• On non-adaptive majority problems of large query size
• Computing majority with triple queries
• Searching for majority with \(k\)-tuple queries

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)