The Average-Case Complexity of Determining the Majority

DOI10.1137/S0097539794275914MaRDI QIDQ4337428zbMATH OpenOpenAlexFDO

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

Publication date 3 August 1997

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0097539794275914

zbMATH Keywords

average case

Mathematics Subject Classification ID

Factorials, binomial coefficients, combinatorial functions (05A10) Radix representation; digital problems (11A63) Searching and sorting (68P10) Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Parallel algorithms in computer science (68W10)

Recommendations

• Determining the majority
• Determining the majority: The biased case
• Analysis of Boyer and Moore's \texttt{MJRTY} algorithm
• On computing majority by comparisons
• Average-case analysis of some plurality algorithms

Cited in

(24)

• Randomized strategies for the plurality problem
• On randomized algorithms for the majority problem
• The worst-case chip problem
• Tight bounds on plurality
• On computing majority by comparisons
• Determining the majority: The biased case
• Variants of the majority problem.
• Finding modes with equality comparisons
• From discrepancy to majority
• New applications of the incompressibility method. II
• Truth tellers and liars with fewer questions
• Analysis of Boyer and Moore's \texttt{MJRTY} algorithm
• Computing majority via multiple queries
• Finding mode using equality comparisons
• Randomized algorithms for the majority problem
• scientific article; zbMATH DE number 6851888 (Why is no real title available?)
• Average-case lower bounds for the plurality problem
• Searching for majority with k-tuple queries
• The plurality problem with three colors and more.
• Search for a majority element
• On approximate majority and probabilistic time
• Determining the majority
• Computing majority with triple queries
• How to play the majority game with a liar

This page was built for publication: The Average-Case Complexity of Determining the Majority

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