Determining the majority

DOI10.1016/0020-0190(93)90135-VzbMATH Open0780.68051MaRDI QIDQ688232FDOQ688232

Authors: L. Alonso, Edward M. Reingold, R. Schott 

Publication date: 31 January 1994

Published in: Information Processing Letters (Search for Journal in Brave)

Recommendations

• The Average-Case Complexity of Determining the Majority
• Determining the majority: The biased case
• Variants of the majority problem.
• On computing majority by comparisons
• On randomized algorithms for the majority problem

zbMATH Keywords

decision treeslower bound

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05)

Cites Work

• Finding repeated elements
• On computing majority by comparisons
• Mathematics for the Analysis of Algorithms.
• Title not available (Why is that?)

Cited In (29)

• How to play the majority game with a liar
• Tight bounds on plurality
• Randomized strategies for the plurality problem
• The majority game with an arbitrary majority
• Truth tellers and liars with fewer questions
• From discrepancy to majority
• The plurality problem with three colors and more.
• Computing majority with triple queries
• Majority voting on orders
• The Borda majority count
• Search for a majority element
• The worst-case chip problem
• Randomized algorithms for finding a majority element
• Majority vote following a debate
• Variants of the majority problem.
• Finding a majority ball with majority answers
• Searching for knights and spies: a majority/minority game
• Finding modes with equality comparisons
• On randomized algorithms for the majority problem
• A stochastically quasi-optimal search algorithm for the maximum of the simple random walk
• Finding mode using equality comparisons
• New applications of the incompressibility method. II
• Finding a non-minority ball with majority answers
• What majority decisions are possible
• Searching for majority with \(k\)-tuple queries
• Determining the majority: The biased case
• From discrepancy to majority
• Analysis of Boyer and Moore's \texttt{MJRTY} algorithm
• On more variants of the majority problem

This page was built for publication: Determining the majority

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