Determining the majority

DOI10.1016/0020-0190(93)90135-VMaRDI QIDQ688232zbMATH OpenFDO

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

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)

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

Cites work

• scientific article; zbMATH DE number 3573250 (Why is no real title available?)
• Finding repeated elements
• Mathematics for the Analysis of Algorithms.
• On computing majority by comparisons

Cited in

(29)

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

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)