On computing majority by comparisons

DOI10.1007/BF01275672MaRDI QIDQ1181015zbMATH OpenFDO

Authors Michael Saks, Michael Werman

Publication date 27 June 1992

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF01275672

zbMATH Keywords

partition

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Partitions of sets (05A18)

Recommendations

• Determining the majority
• The Average-Case Complexity of Determining the Majority
• Determining the majority: The biased case
• Search for a majority element
• Finding an Approximate Maximum

Cites work

• scientific article; zbMATH DE number 3460321 (Why is no real title available?)
• Finding repeated elements
• On recognizing graph properties from adjacency matrices

Cited in

(34)

• Adaptive majority problems for restricted query graphs and for weighted sets
• How to play the majority game with a liar
• Tight bounds on plurality
• Computing majority via multiple queries
• Randomized strategies for the plurality problem
• Randomized algorithms for the majority problem
• The majority game with an arbitrary majority
• Truth tellers and liars with fewer questions
• The plurality problem with three colors and more.
• Determining the majority
• Computing majority with triple queries
• Search for a majority element
• The worst-case chip problem
• Variants of the majority problem.
• Finding a majority ball with majority answers
• A plurality problem with three colors and query size three
• Searching for knights and spies: a majority/minority game
• Finding non-minority balls with majority and plurality queries
• On non-adaptive majority problems of large query size
• Finding modes with equality comparisons
• On randomized algorithms for the majority problem
• New applications of the incompressibility method. II
• Finding mode using equality comparisons
• Adaptive majority problems for restricted query graphs and for weighted sets
• Finding a non-minority ball with majority answers
• A New Lower Bound for the Set-Partitioning Problem
• Searching for majority with k-tuple queries
• Determining the majority: The biased case
• From discrepancy to majority
• Analysis of Boyer and Moore's \texttt{MJRTY} algorithm
• Determining majority in networks with local interactions and very small local memory
• On more variants of the majority problem
• On the decision tree complexity of threshold functions
• Majority problems of large query size

This page was built for publication: On computing majority by comparisons

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