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

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Searching and sorting (68P10) Factorials, binomial coefficients, combinatorial functions (05A10) Radix representation; digital problems (11A63) 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

(23)

• scientific article; zbMATH DE number 6851888 (Why is no real title available?)
• Search for a majority element
• The worst-case chip problem
• Determining the majority
• Computing majority with triple queries
• Computing majority via multiple queries
• Determining the majority: The biased case
• Truth tellers and liars with fewer questions
• The plurality problem with three colors and more.
• Tight bounds on plurality
• From discrepancy to majority
• Finding modes with equality comparisons
• Average-case lower bounds for the plurality problem
• Randomized strategies for the plurality problem
• Randomized algorithms for the majority problem
• On approximate majority and probabilistic time
• 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
• 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: 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)