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)

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)

• On the decision tree complexity of threshold functions
• Search for a majority element
• The worst-case chip problem
• Adaptive majority problems for restricted query graphs and for weighted sets
• Finding non-minority balls with majority and plurality queries
• Determining the majority
• Computing majority with triple queries
• Computing majority via multiple queries
• Determining the majority: The biased case
• The majority game with an arbitrary majority
• Adaptive majority problems for restricted query graphs and for weighted sets
• Truth tellers and liars with fewer questions
• A plurality problem with three colors and query size three
• Searching for knights and spies: a majority/minority game
• The plurality problem with three colors and more.
• Tight bounds on plurality
• From discrepancy to majority
• Finding modes with equality comparisons
• Majority problems of large query size
• Randomized strategies for the plurality problem
• On more variants of the majority problem
• On non-adaptive majority problems of large query size
• Randomized algorithms for the majority problem
• A New Lower Bound for the Set-Partitioning Problem
• Determining majority in networks with local interactions and very small local memory
• Finding a majority ball with majority answers
• Finding a non-minority ball with majority answers
• 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: 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)