Determining the majority

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

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

Publication date: 31 January 1994

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

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 (27)

• 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
• 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
• Majority vote following a debate
• Variants of the majority problem.
• Searching for majority with k-tuple queries
• 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
• New applications of the incompressibility method. II
• Finding a non-minority ball with majority answers
• What majority decisions are possible
• 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
• Finding Mode Using Equality Comparisons

   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

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)