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)

• 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
• The Borda majority count
• Majority voting on orders
• Search for a majority element
• The worst-case chip problem
• Majority vote following a debate
• Randomized algorithms for finding a majority element
• 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
• New applications of the incompressibility method. II
• Finding mode using equality comparisons
• 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)