Variants of the majority problem.

DOI10.1016/S0166-218X(03)00186-0zbMATH Open1034.68046MaRDI QIDQ1422403FDOQ1422403

Authors: Martin Aigner 

Publication date: 14 February 2004

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

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

zbMATH Keywords

majority problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites Work

• On computing majority by comparisons
• Search for a majority element
• Determining the majority
• Title not available (Why is that?)
• On a logical problem
• The Average-Case Complexity of Determining the Majority

Cited In (25)

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

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)