The Average-Case Complexity of Determining the Majority
From MaRDI portal
Publication:4337428
DOI10.1137/S0097539794275914zbMath0868.68066MaRDI QIDQ4337428
Edward M. Reingold, René Schott, Laurent Alonso
Publication date: 3 August 1997
Published in: SIAM Journal on Computing (Search for Journal in Brave)
68Q25: Analysis of algorithms and problem complexity
68P10: Searching and sorting
05A10: Factorials, binomial coefficients, combinatorial functions
68R05: Combinatorics in computer science
68W10: Parallel algorithms in computer science
11A63: Radix representation; digital problems
Related Items
Searching for majority with k-tuple queries, Search for a majority element, The plurality problem with three colors and more., Computing majority with triple queries, How to play the majority game with a liar, Randomized strategies for the plurality problem, On randomized algorithms for the majority problem, The worst-case chip problem, Tight bounds on plurality, 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
