Randomized strategies for the plurality problem

DOI10.1016/J.DAM.2008.05.014MaRDI QIDQ1003477zbMATH OpenOpenAlexWikidataFDO

Authors Daniel Král', Jiří Sgall, Tomáš Tichý

Publication date 4 March 2009

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2008.05.014

zbMATH Keywords

concrete complexitymajority gameplurality gamerandomized algorithms

Mathematics Subject Classification ID

2-person games (91A05)

Recommendations

• The plurality problem with three colors and more.
• Probabilistic strategies for the partition and plurality problems
• STACS 2005
• STACS 2004
• A plurality problem with three colors and query size three

Cites work

• A guided tour of Chernoff bounds
• Determining the majority
• scientific article; zbMATH DE number 1339958 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• On computing majority by comparisons
• Probabilistic strategies for the partition and plurality problems
• Randomized Algorithms for Determining the Majority on Graphs
• STACS 2004
• The Average-Case Complexity of Determining the Majority
• The plurality problem with three colors and more.
• The worst-case chip problem
• Variants of the majority problem.

Cited in

(12)

• From discrepancy to majority
• A plurality problem with three colors and query size three
• Oblivious and adaptive strategies for the majority and plurality problems
• Computing majority via multiple queries
• Probabilistic strategies for the partition and plurality problems
• Determining plurality
• Searching for majority with k-tuple queries
• STACS 2004
• scientific article; zbMATH DE number 2202829 (Why is no real title available?)
• STACS 2005
• Computing and Combinatorics
• Computing majority with triple queries

This page was built for publication: Randomized strategies for the plurality problem

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