The Average-Case Complexity of Determining the Majority

DOI10.1137/S0097539794275914zbMath0868.68066OpenAlexW1971578319MaRDI QIDQ4337428

Edward M. Reingold, René Schott, Laurent Alonso

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

Related Items

Determining the majority: The biased case ⋮ Finding modes with equality comparisons ⋮ Variants of the majority problem. ⋮ Analysis of Boyer and Moore's \texttt{MJRTY} algorithm ⋮ Computing majority via multiple queries ⋮ New applications of the incompressibility method. II ⋮ From discrepancy to majority ⋮ Computing majority with triple queries ⋮ How to play the majority game with a liar ⋮ The plurality problem with three colors and more. ⋮ Search for a majority element ⋮ Randomized strategies for the plurality problem ⋮ Finding Mode Using Equality Comparisons ⋮ On randomized algorithms for the majority problem ⋮ The worst-case chip problem ⋮ Tight bounds on plurality ⋮ Randomized algorithms for the majority problem ⋮ Truth tellers and liars with fewer questions ⋮ Searching for majority with k-tuple queries