Variants of the majority problem.

DOI10.1016/S0166-218X(03)00186-0MaRDI QIDQ1422403zbMATH OpenFDO

Authors Martin Aigner

Publication date 14 February 2004

Published in Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

majority problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• On more variants of the majority problem
• On randomized algorithms for the majority problem
• Majority and plurality problems
• Majority and plurality problems
• Finding a majority ball with majority answers

Cites work

• scientific article; zbMATH DE number 41347 (Why is no real title available?)
• Determining the majority
• On a logical problem
• On computing majority by comparisons
• Search for a majority element
• The Average-Case Complexity of Determining the Majority

Cited in

(25)

• Range Majority in Constant Time and Linear Space
• Adaptive majority problems for restricted query graphs and for weighted sets
• Finding non-minority balls with majority and plurality queries
• Determining the majority
• Computing majority with triple queries
• Computing majority via multiple queries
• The majority game with an arbitrary majority
• Adaptive majority problems for restricted query graphs and for weighted sets
• Truth tellers and liars with fewer questions
• A plurality problem with three colors and query size three
• How to Play the Majority Game with Liars
• Searching for knights and spies: a majority/minority game
• The plurality problem with three colors and more.
• From discrepancy to majority
• Majority problems of large query size
• Randomized strategies for the plurality problem
• On more variants of the majority problem
• Randomized algorithms for the majority problem
• Finding a majority ball with majority answers
• Finding a non-minority ball with majority answers
• Local and global majorities revisited
• On randomized algorithms for the majority problem
• Do local majorities force a global majority?
• How to play the majority game with a liar
• Searching for majority with \(k\)-tuple queries

This page was built for publication: Variants of the majority problem.

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