Tight bounds on plurality

DOI10.1016/j.ipl.2005.06.004zbMath1178.68702OpenAlexW1966180611MaRDI QIDQ1044713

Alan D. Taylor, Nikhil Srivastava

Publication date: 18 December 2009

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2005.06.004

zbMATH Keywords

computational complexityanalysis of algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (2)

Computing majority via multiple queries ⋮ How to play the majority game with a liar

Cites Work

• Determining the majority
• On computing majority by comparisons
• The Average-Case Complexity of Determining the Majority
• Search for a majority element

This page was built for publication: Tight bounds on plurality