On computing majority by comparisons
From MaRDI portal
Publication:1181015
DOI10.1007/BF01275672zbMath0739.05006MaRDI QIDQ1181015
Michael E. Saks, Michael Werman
Publication date: 27 June 1992
Published in: Combinatorica (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Partitions of sets (05A18) Combinatorics in computer science (68R05)
Related Items (32)
The majority game with an arbitrary majority ⋮ Searching for knights and spies: a majority/minority game ⋮ Finding a majority ball with majority answers ⋮ Determining the majority: The biased case ⋮ Finding modes with equality comparisons ⋮ Adaptive majority problems for restricted query graphs and for weighted sets ⋮ Variants of the majority problem. ⋮ Analysis of Boyer and Moore's \texttt{MJRTY} algorithm ⋮ Majority problems of large query size ⋮ Computing majority via multiple queries ⋮ New applications of the incompressibility method. II ⋮ Finding a non-minority ball with majority answers ⋮ From discrepancy to majority ⋮ Determining majority in networks with local interactions and very small local memory ⋮ Determining the 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 more variants of the majority problem ⋮ On randomized algorithms for the majority problem ⋮ The worst-case chip problem ⋮ Finding non-minority balls with majority and plurality queries ⋮ Tight bounds on plurality ⋮ Randomized algorithms for the majority problem ⋮ A plurality problem with three colors and query size three ⋮ On the decision tree complexity of threshold functions ⋮ Truth tellers and liars with fewer questions ⋮ Searching for majority with k-tuple queries ⋮ On non-adaptive majority problems of large query size
Cites Work
This page was built for publication: On computing majority by comparisons
